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.
Credits:
Special thanks to for adding this problem and creating all test cases.2. 思路
第一反应是直接用x & (x-1)的循环到x=0来算。第二反应是分字节的查表法。
代码之美的第10章“寻找快速的种群计数”有更深入的讲解，用了其中的最优的方法。按位计算，第一次是奇偶位相加放在每两位的地方。然后每4位的两位两位相加，放在每4位的结果上。知道32位的每16位相加。由于最多只有32个1，也就是只有低位的5bit有效，后面的8、16的不用再移位计算，溢出的高位部分无所谓，最后用&清0即可。
3. 代码
class Solution {public: int hammingWeight(uint32_t n) { n = n - ((n>>1) & 0x55555555); n = (n & 0x33333333) + ((n>>2) & 0x33333333); n = (n + (n>>4)) & 0x0f0f0f0f; n = n + (n>>8); n = n + (n>>16); return n & 0x3f; }};