LeetCode Number of 1 Bits

1.题目

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

For example, the 32-bit integer ’11′ has binary representation 00000000000000000000000000001011, so the function should return 3.

2.解决方案1

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count = 0;

    while (n)
    {
        ++ count;
        n = (n - 1) & n;
    }

    return count;
    }
};

比如容易想到的解决方案是下面这个，每次往右移动一位，判断最后一位是不是1，但这样会有点慢，32位就要移动32次。上面的方法巧妙的使用了(n-1) & n，这个有什么用？我们来看下具体的例子：

假设n＝ 1111000111000 那 n-1 = 1111000110111, (n-1) & n = 1111000110000，刚好把最后一个1给干掉了。也就是说， (n-1)&n 刚好会从最后一位开始，每次会干掉一个1.这样速度就比下面的快了。有几个1，执行几次。

class Solution {
public:
    int hammingWeight(uint32_t n) {
       int count = 0;
    while(n)
    {
        if(n & 1)
            count ++;

        n = n >> 1;
    }

    return count;
    }
};

http://www.waitingfy.com/archives/1642

数据结构 & 算法 | RSS 2.0 |