剑指Offer-二进制中1的个数

2017/3/12 posted in  算法-数据结构  

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

思路

  • 方案一:

    将(n&1)可以知道n的最后一位是不是1,然后依次将n不断向右移1位,直到n为0。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0){
            if( (n & 1) == 1){
                count++;
            }
            /*
            *注意,这里是>>>
            *>>为最高位填补符号位,负数会发生错误
            *>>>为最高位填写0
            */
            n = n >>> 1;
        }
        return count;
    }
}
  • 方案二:

    将一个整数减一,都是把最右边的1变成0,如果它的右边还有0的话,所有的0都变成1,而它的左边的所有位都保持不变。若我们将n和n-1做与运算,相当于把它最右边的1变成0。那么,一个整数的二进制表示中有多少个1,就可以进行多少次这样的操作。

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