## Question

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.

## Solution

### right-shift counting

The simplest technique is right-shift the number 32 times, counting the number of times you right-shift a one bit off.

A similar alternative checks each bit of the number from right to left.

### bit manipulation trick

In my interview at Microsoft, I composed essentially `hammingWeight_B()`, which impressed the interviewer well enough. But then he showed me a different technique, which I have to admit is pretty clever. It begins with the observation that, when you subtract a number by 1, all of the lowest bits change up to and including the lowest 1 bit; but the rest of the bits stay the same. So if I do a bitwise AND of n with n − 1, essentially I will remove the last one bit from n.

Once we observe this, we have only to write code that counts how many times we can remove the final bit in this way before we reach a number with no 1 bits at all (i.e., 0).

### more better bit trick

Much later, I heard of yet another technique, which is yet more clever.

`hammingWeight_D()`主要是采用分治的思想，通过0x55555555（0x01010101010101010101010101010101），统计相邻两位的‘1’的个数，也就是`ret = (num & 0x55555555) + ((num >> 1) & 0x55555555);`

ret = 0x50005308（01010000000000000101001100001000）

01010000000000000101001100001000 0x50005308 原数
01010000000000000101001000000100 0x50005204 第一次运算后
00100000000000000010001000000001 0x20002201 第二次运算后
00000010000000000000010000000001 0x2000401 第三次运算后
00000000000000100000000000000101 0x20005 第四次运算后
00000000000000000000000000000111 0x7 第五次运算后