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).
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; } }; 正文到此结束
热门推荐
相关文章
Loading...
![[HBLOG]公众号](http://www.liuhaihua.cn/img/qrcode_gzh.jpg)
