xiaomi

个人博客

小米的个人博客,欢迎交流


每天一道剑指offer:二进制中1的个数


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


思路

-> 从右至左依次计算1的个数
-> 不能用n&1,n»1直接查询
-> 因为负数是用补码表示,负数补码最高位为1
右移操作会高位补1,如此负数中1的个数就是无穷大

  • 解法1:
    与运算的数1左移:
    n & 1
    n & 10
    n & 100
    n & 1000
    依次计算每一位是否是1,解决了补码高位补1的问题

  • 解法2: n = n & (n-1) 直到 n==0,统计一共循环的次数


代码

  • 解法 2
    public int NumberOf1(int n) {    
        int count = 0;    
        while (n != 0) {        
            n = n & (n - 1);        
            count++;    
        }    
        return count;
    }