原题
LintCode 365. Count 1 in Binary
Description
Count how many 1 in binary representation of a 32-bit integer.
Example
Given 32, return 1
Given 5, return 2
Given 1023, return 10
通常解法
不停地将这个数右移，当最后一位为1的时候计数+1，直到这个数变为0。
但是因为C++中没有无符号右移，所以在面对负数的时候，上述算法就不管用了。
可以将负数取反，计算0的个数即可。
int countOnes(int num) {
bool negative = false;
if (num < 0) {
num = ~num;
negative = true;
}
int count = 0;
while (num) {
if (num & 1) count++;
num >>= 1;
}
if (negative) return 32 - count;
return count;
}
a & (a - 1)
网上查找更好解法的时候，发现了一个神奇的方法
int countOnes(int num) {
int count = 0;
while (num != 0) {
num = num & (num - 1);
count++;
}
return count;
}
那么这个a & (a - 1)到底干了什么？
举个例子 36
# 36
00100100
# 36-1
00100011
可以发现，每次减1操作，都会从二进制数的最后一个1处借位，使之变为0，之后的所有位变为1。
此时 将两者按位与
# 36 & (36 - 1)
00100000
因为被借位以及之后的所有位都发生了改变，结果均为0
最终的结果是：将二进制数中的最后一个1替换为0
