题目描述

输入一个整数 n 输出该数32位二进制表示中1的个数。其中负数用补码表示。

数据范围- 2^{31} <= n <= 2^{31}-1−231<=n<=231−1

即范围为:-2147483648<= n <= 2147483647−2147483648<=n<=2147483647

示例1

输入

10

复制

返回值

2

复制

说明

十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010其中有两个1。       

示例2

输入

-1

复制

返回值

32

复制

说明

负数使用补码表示 -1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111其中32个1    

思路

思路一可以采用模二取余求1的个数

思路二采用按位与的格式来建立二进制对比后输出如果一个数转化为二进制后对应的将最后一位与1相与再根据用将该数循环右移和1按位与之后最后统计1个数即可

具体实现

//写C语言情况下的运算
//根据模二取余的方法
//计算1的个数
#include<stdio.h>
#include<windows.h>

//设计函数把整数转换为二进制并输出1的个数
int count_one_bits(unsigned int value){
 int count = 0;
  //输入1的个数  
  while (value){
   if (value%2 == 1){
    count++;
   }
   value /= 2;
 }
 return count;
}


int main(){
 //数据测试   
 int value=18;
 int count = count_one_bits(value);
 printf("%d\n", count);
 system("pause");
 return 0;
}

//方案二采用按位与的格式来建立二进制对比后输出
//如果一个数转化为二进制后对应的将最后一位与1相与
//再根据用将该数循环右移和1按位与之后最后统计1个数即可

int main() {
	int n = 0;
	//输入数据测试
    scanf("%d", &n);
	int ret = NumberOf(n);
	printf("%d的二进制中1的个数为%d\n", n, ret);
	return 0;
}

//按位与后循环右移
//当输入数据为正整数是直接运行即可
int NumberOf(int n){
	int count = 0;
	if (n >= 0){
		while (n)
		{
			if (n % 2 != 0){
				count++;
			}
			n /= 2;
		}
	}
    //如果输入数据为负整数则按位取反后再模2
    //统计1的个数最后输出结果
	else{
		n = ~n;
		while (n)
		{
			if (n % 2 != 0)
			{
				count++;
			}
			n /= 2;
		}
		count = 32 - count;
	}
	return count;
}

时间复杂度

对于方案一采用模2除法n次所以时间复杂度为O(n),空间复杂度为O(1)

对于方案二采用按位与之后循环右移遍历一次数据即可所以时间复杂度为O(n),空间复杂度为O(1)

小结

在C语言中由于int为所占空间4B即32个比特位因此如果输入为-1的时候为了整体确定1的个数在计算机中数据都是按补码形式保存的因此输出的-1所占的1的个数应该为32个而不是2两个因此在计算的时候一定要考虑整数的所有部分通过这些来整体考虑数据结果最后给出算法的输出确保通过所有测试用例在判断1的个数的时候可以采用移位相与的方法也可以采用模2取余的方法也可以采用按位下放的方法来解决问题采用不同的原理可以从不同的角度解决问题从而使算法的时间复杂度降低加快算法输出速度也是让我们看到更多的角度来针对具体问题具体分析因此多角度分析全面考虑对于学习编程以及代码完整性具有良好的借鉴意义。