剑指offer—二进制数中的1的个数 解答

剑指offer—二进制数中的1的个数

题目描述

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

思路

依次无符号右移判断最右位是否为1,为1累加,当右移至0后结束循环

代码

需要循环二进制位数

public class Solution {
    public int NumberOf1(int n) {
        int m = 0;
        /*计算机负数存储的是补码
        if(n<0){
            n = ~n + 1;
        }*/
        while(n!=0){
            if((n&1)!=0){
                m++;
            }
            n = n>>>1;
        }
        return m;
    }
}

只需要循环1的个数次循环

优化后方法:一个数减去1的话,它的最后一个二进制1位将由1变为0,它后面的数本来都为0,将由0全部变为1,相当于最后一个1位到最后的二进制取反了,再把它与上自己原来的值(减一之前)则就是把从最后一个1位到最后全变为0,此时最后一个1位将为原数倒数第二个1位

例子:

10110

减一后:

10101

与上10110后:

10100

循环遍历次数就是1的个数

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