Write a function that takes an unsigned integer and returns the number of ’1′ bits it has (also known as the Hamming weight).
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; } };