《剑指offer》 二进制中1的个数

时间:2024-10-06 20:36:51

本题来自《剑指offer》 二进制中1的个数

题目:

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

思路:

  两种思路:

  第一种:对n进行左移,检测最后一位是否为1,但考虑负数,一直左移会陷入到死循环中。

  第二种:对n的每一位进行检测,采用滑标flag,左移,int会是32位,所以会最多移动32次。

C++ code1:(第二种思路)

class Solution {
public:
int NumberOf1(int n) { //最多可以移动32次,
int count=;
unsigned int flag = ; //无符号的整形数据【0,655**】
while(flag){ //flag左移直到,为0时候便结束
if (flag&n){ //和n相与,如果为1就累计
count += ;
}
flag = flag << ; //flag左移[0000-31-00001]
}
return count;
}
};

C++ Code2:

class Solution {
public:
int NumberOf1(int n) { //最多可以移动32次,
int count=;
while(n){ //flag左移直到,为0时候便结束
count ++;
        n = (n-1)&n;
}
return count;
}
};

总结:

  检测是否为1,采用与1相与的操作。考虑正数和负数和0做测试集。