191-位1的个数

LeetCode 191. Number of 1 Bits

LeetCode-191

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Example 1:

Input: n = 00000000000000000000000000001011
Output: 3

method 1: 直观方法

每次取n的最低位，如果是1，计数器就加1
然后n右移一位，因为无符号数右移是逻辑右移，最高位补0，所以n最终会变成0

int hammingWeight(uint32_t n) {
    int cnt = 0;
    while (n) {
        cnt += n & 1;
        n >>= 1;
    }
    return cnt;
}

method 2: 位运算

lowBit函数返回二进制最低位的1和后面的0，比如1100返回100
1100返回100，做差得1000，ans=1
1000返回1000，做差得0，ans=2，结束

uint32_t lowBit(uint32_t x) {
    return x & (-x);
}

int hammingWeight(uint32_t n) {
    int cnt = 0;
    while (n) {
        n -= lowBit(n);
        cnt++;
    }
    return cnt;
}

也可以用n & (n - 1)，同样也是消掉最后一个1，1100 & 1011 = 1000

int hammingWeight(uint32_t n) {
    int cnt = 0;
    while (n) {
        n = n & (n - 1);
        cnt++;
    }
    return cnt;
}