欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-12 15:50:20
...

文章目录

题目:二进制中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;
}
  • 运行结果:

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


解法二:(使用二进制和位运算——可能引起死循环)

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

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

  • 代码实现:
#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;
}
  • 运行结果

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

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


解法三:(常规解法)

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

【面试编程题】二进制中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;
}
  • 运行结果:

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

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


解法四:(惊喜解法)

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

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

  • 实现代码:
#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的个数


相关题型

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;
}

运行结果:

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

 

相关标签: 面试编程题