Count how many 1 in binary representation of a 32-bit integer.
Given 32, return 1
Given 5, return 2
Given 1023, return 9
If the integer is n bits with m 1 bits. Can you do it in O(m) time?
We can use Kernighan’s bit counting algorithm, which works as follows.
- The expression
num & (num - 1)removes a 1 bit from the num
- Using this fact, we can use the expression in a loop and check for
num == 0
A Java implementation of the algorithm is below.