输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
如 9 1001 则输出2
思路
这是一个考察二进制和位运算的面试题 先复习下位运算
几个用法-华仔要长胖
根据: 取指定位上的数字，如取得数字 1010 1010 的最后四位：1010 1010 & 0000 1111 = 0000 101
方法一
判断整数二进制表示中最右边的一位是不是1,接着把输入的整数右移一位,这样右边第二位就变成了右边第一位,
再继续判断,直到最后二进制数等于0.
public static int NumberOf(int n) {
int count = 0;
while (n != 0) {
// n&0001 取右边第一位的二进制值
if ((n & 1) != 0) {
count++;
}
n = n >> 1;
}
return count;
}
但是这样会有一个问题就是,当我们判断负数的时候,因为符号位为1，
当我们右移的时候,左边填充的将是1，这个时候，将可能陷入死循环.
方法二
为了避免死循环,我们可以不右移输入的数字N,首先把n和1做运算,判断n的最低位是不是1(0001).
接着把1左移一位得到2(0010)再和N做&运算.
public static int NumberOf02(int n) {
int count = 0;
int flag = 1;
while (flag != 0) {
if ((flag & n) != 0) {
count++;
}
flag = flag << 1;
}
return count;
}
方法三
- 如果一个整数不等于0，那么该整数的二进制表示中至少有一位是0。
- 假设最后一位不是0，那么减去1，最后一位变成0而其他所有位都保持不变，也就是最后一位相当于做了取反操作，由1变成了0.
- 假设最后一位是0，如果该整数的二进制表示中最右边的1位于第m位，那么减去1时，第m位由1变成0，而第m位之后的所有0都变成1，整数中第m位之前的所有位都保持不变。
- 把一个整数和它减去1的结果做位与运算，相当于把它最右边的1变成0。
- 所以，这种方法，只要这个整数有几个1，就做几次这样的操作。
如:
输入:9(1001)
//第一次循环
9-1=8(1000)
9(1001)&8(1000)=8(1000)
//第二次循环
8-1=7(0111)
8(1000)&7(0111)=0
public static int NumberOf03(int n) {
int count = 0;
while (n != 0) {
count++;
n = (n - 1) & n;
}
return count;
}