【剑指Offer】二进制中1的个数

【题目】

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

【思路】

两种方法。

【代码】

• 方法一

对于正数，处理方法很简单，一边和‘1’做与运算并计数，一边右移，直到正数变为0。

对于负数，我们知道在C++中是以补码的形式存储，比如-7 在计算机中表达为：11111111 11111111 11111111 11111001。这里要注意，负数右移是在最高位补‘1’，所以如果和正数一样处理，就会发生无限循环。

这时可以换个思路，不是让原整数n右移，而是单独设置一个数a（初始值为1）左移并和n做与运算，如果结果为a，说明n的该位为1。因为二进制表示为32位，所以a左移32次即可。

class Solution {
public:
	int  NumberOf1(int n) {
		int count = 0;
		int a = 1;
		int k = 1;
		if (n >= 0) {  // 处理正数和0
			while (n != 0) {
				if (n & 1) {
					count++;
				}
				n >>= 1;
			}
		}
		else {  // 处理负数
			while (k != 33) {
				if ((n & a) == a) {
					count++;
				}
				a <<= 1;
				k++;
			}
		}
		return count;
	}
};

• 方法二

把一个整数 （无论正负或0）减去1，再和原整数做与运算，会把该整数最右边的一个1变为0。

例如：1100减1后变为1011，二者进行与操作后，得到1000，原整数最后边的1变为了0，而前面的位都不变。

因此可以设置循环，重复该操作，直到该整数变为0。

class Solution {
public:
	int  NumberOf1(int n) {
		int count = 0;
		while (n) {
			n = (n - 1)&n;
			count++;
		}
		return count;
	}
};