【面试题】剑指offer10--求一个数的二进制数中的1的个数

àì夳堔傛蜴生んèń 2022-06-14 08:21 130阅读 0赞

求一个数二进制数中的个数

第一种方法：模除法

代码如下：

//Q:请实现一个函数，输入一个整数，输出该数二进制中的
    //1的个数。例如：把9表示成二进制是1001，有2位是1.因此，如果输入是9
    //改函数输出2。
    #include<iostream>
    using namespace std;
    
    int TheNumOf1(int num)//统计二进制中1的个数
    {
    	int count = 0;
    	while (num)
    	{
    		if (num % 2 == 1)
    		{
    			count++;
    		}
    		num = num / 2;
    	}
    	return count;
    }
    int main()
    {
    	int num = 0; 
    	int ret = 0;
    	cout << "请输入一个数字：";
    	cin >> num;
    	ret = TheNumOf1(num);
    	cout << num << "的二进制数中的1的个数为：" << ret << endl;
    	system("pause");
    	return 0;
    }

第二种方法：第一种方法的优化，解决传入的数字是负数的问题

//Q:请实现一个函数，输入一个整数，输出该数二进制中的
    //1的个数。例如：把9表示成二进制是1001，有2位是1.因此，如果输入是9
    //改函数输出2。
    #include<iostream>
    using namespace std;
    int TheNumOf1(unsigned int num)
    {
    	int count = 0;
    	while (num)
    	{
    		if (num % 2 == 1)
    		{
    			count++;
    		}
    		num = num / 2;
    	}
    	return count;
    }
    int main()
    {
    	int num = 0; 
    	int ret = 0;
    	cout << "请输入一个数字：";
    	cin >> num;
    	ret = TheNumOf1(num);
    	cout << num << "的二进制数中的1的个数为：" << ret << endl;
    	system("pause");
    	return 0;
    }

第三种方法：对前两种方法的优化，为了解决没一个数字都是32位的比特位，使用下面的方法：

//Q:请实现一个函数，输入一个整数，输出该数二进制中的
    //1的个数。例如：把9表示成二进制是1001，有2位是1.因此，如果输入是9
    //改函数输出2。
    #include<iostream>
    using namespace std;
    int TheNumOf1(unsigned int num)
    {
    	int count = 0;
    	for (int i = 1; i < 32; i++)
    	{
    		if (num % 2 == 1)
    		{
    			count++;
    		}
    		num = num / 2;
    	}
    	return count;
    }
    int main()
    {
    	int num = 0; 
    	int ret = 0;
    	cout << "请输入一个数字：";
    	cin >> num;
    	ret = TheNumOf1(num);
    	cout << num << "的二进制数中的1的个数为：" << ret << endl;
    	system("pause");
    	return 0;
    }

第四种方法：使用按位与的方法，可以更快的运行程序

//Q:请实现一个函数，输入一个整数，输出该数二进制中的
    //1的个数。例如：把9表示成二进制是1001，有2位是1.因此，如果输入是9
    //改函数输出2。
    #include<iostream>
    using namespace std;
    int TheNumOf1(unsigned int num)
    {
    	int count = 0;
    	while (num)
    	{
    		num = num&(num - 1);
    		count++;
    	}
    	return count;
    }
    
    int main()
    {
    	int num = 0; 
    	int ret = 0;
    	cout << "请输入一个数字：";
    	cin >> num;
    	ret = TheNumOf1(num);
    	cout << num << "的二进制数中的1的个数为：" << ret << endl;
    	system("pause");
    	return 0;
    }

使用这几种方法都可以求解出一个数二进制数中的1的个数