【面试编程题】二进制中1的个数

文章目录

题目：二进制中1的个数

解法一：（短除法——可能引起死循环）

解法二：（使用二进制和位运算——可能引起死循环）

解法三：（常规解法）

解法四：（惊喜解法）

相关题型

---

题目：二进制中1的个数

题目：实现一个函数，输入一个整数，输出该数二进制表示中1的个数。例如：若输入9，该数的二进制为1001，所以输出2.

---

解法一：（短除法——可能引起死循环）

• 思路1：可以将该问题转换为十进制数转二进制表示问题，即对数字进行除2操作，如果余数是1，计数+1，直到数字为1.（这是十进制转二进制的短除法的算法）
• 代码实现：

#include <iostream>
using namespace std;

/*二进制表示1的个数统计*/
int Number_Ofone(int n) {
	int count = 0;
	while (n) {
		if (n % 2 == 1) {
			count++;
		}
		n /= 2;
	}
	return count;
}

/*10进制转二进制*/
int DtoB(int n, int num[32]) {
	int count = 0;
	while (n) {
		num[count++] = n % 2;
		n /= 2;
	}
	return count;
}

int main() {
	int num,count=0;
	int a[32] = { 0 };
	cin >> num;
	int k=DtoB(num, a);
	count = Number_Ofone(num);
	for (int i = k - 1; i >= 0; i--) {
		cout << a[i];
	}
	cout << endl;
	cout << count << endl;
}

• 运行结果：

---

解法二：（使用二进制和位运算——可能引起死循环）

• 思路2：先判断整数二进制最右边是否为1，是则计数加一；接下来将整数二进制向右移动一位，此时原来处于从右边数起的第二位变为最右边，再判断是否为1；这样重复判断，直到整个数变为0时。
• 案例解析如下：

• 代码实现：

#include <iostream>
using namespace std;

int Number_Ofone_2(int n) {
	int count = 0;
	while (n) {
		if (n&1) {
			count++;
		}
		n >>=1;
	}
	return count;
}

int main() {
	int num;
	cin >> num;
	cout << Number_Ofone_2(num) << endl;
}

• 运行结果：

 

上述的解法一和解法二类似，相比而言，位运算的效率要比四则运算的要高很多。但是这两种思路都缺陷，它们没有考虑到负整数的情况，例如：当输入数字为0X8000 0000时，当把负数0X8000 0000右移一位，并不是把最高位的1移到第二位变成0X4000 0000，而是0XC000 0000。因为移位前是一个负数，要保证移位后仍是一个负数，因此一位后的最高位会设为1。如果一直做右移操作，最终数字会变为0XFFFF FFFF而陷入死循环。

---

解法三：（常规解法）

• 思路：为了避免死循环，应该避免移动输入的数字n。首先把n和1做与运算，判断n的最低位是否为1，接下来将1左移，再与n作与运算，判断n的次低位是否为1，这样重复判断，直至超出表示范围。
• 实例解析如下：

• 代码实现： 

#include <iostream>
using namespace std;

int Number_Ofone_3(int n) {
	int count = 0;
	int flag = 1;
	while (flag) {
		if (n & flag) {
			count++;
		}
		flag <<= 1;
	}
	return count;
}

int main() {
	//int num;
	//cin >> num;
	cout << "十进制" << "——" << "二进制1的个数" << endl;
	cout <<11<<"——"<<Number_Ofone_3(11) << endl;
	cout << 0 << "——" << Number_Ofone_3(0) << endl;
	cout << -1 << "——" << Number_Ofone_3(-1) << endl;
}

• 运行结果：

这个解法，循环的次数等于整数二进制的位数，32位的整数需要循环32次。

---

解法四：（惊喜解法）

• 思路：解法三虽然可以满足要求，但是循环次数比较多，效率上有所欠缺。把一个整数减去1和原整数做与运算就可以把整数最右边的一个1变为0.这样原来整数二进制中有多少个1，就进行几次操作把整数变为0.
• 实例分析如下：

• 实现代码：

#include <iostream>
using namespace std;

int Number_Ofone_4(int n) {
	int count = 0;
	while (n) {
		count++;
		n &= (n - 1);
	}
	return count;
}

int main() {
	cout << "十进制" << "——" << "二进制1的个数" << endl;
	cout << 11 << "——" << Number_Ofone_4(11) << endl;
	cout << 0 << "——" << Number_Ofone_4(0) << endl;
	cout << -1 << "——" << Number_Ofone_4(-1) << endl;
}

运行结果：

---

相关题型

1.用一条语句判断一个整数是不是2的整数次方。

答案：if(n&(n-1)==0)

 解析：根据上述解法四提供给我们的思路，举一反三，一个整数如果是2的整数次方，那么它的二进制有且只有一位是1，那么整数n&(n-1)就将整数的唯一一个1变为了0，所以得到上述答案。

2.输入两个整数m和n，计算需要改变m的二进制几位才能得到n。比如10的二进制为1010,13的二进制1101，需要改变三位才能将10变成13.

思路：先进行异或运算（异或运算相同取0不同取1的法则）得出结果，只要再统计结果中1的个数就能知道两个数的不同位数。

代码实现：

#include <iostream>
using namespace std;

int  Chang_num(int m, int n) {
	int count = 0;
	int tmp = m ^ n;
	while (tmp) {
		count++;
		tmp &= (tmp - 1);
	}
	return count;
}

int main() {
	int m, n;
	cin >> m >> n;
	cout << "m=" << m << ",n=" << n << endl;
	cout << "m转为n需要改变的位数为：" << Chang_num(m, n) << endl;
}

运行结果：