Number of Bits Set
Write a function that takes an unsigned integer and return the number of ‘1’ bits it has.
Example 1: Input: 5 Output: 2 Explanation: Integer 2 in binary is "00000000000000000000000000000101" which has a total of two '1' bits. Example 2: Input: 8 Output: 1 Explanation: Integer 4 in binary is "00000000000000000000000000001000" which has a total of one '1' bit.
Notice that for any integer
n, doing a bit-wise AND of
n-1 has the effect of flipping the least-significant 1 bit in
0. For example,
7 & 6 = 6 and
8 & 7 = 0.
Our problem can be solved by turning off
n's set bits one bit at time:
The Hamming distance between two integers is the number of positions at which the corresponding bits are different. We can compute the hamming distance between two integers
y by invoking
count_set_bits(x ^ y).
Brian Kernighan’s Algorithm can also be used to check if a positive number is a power of 2. Notice that a positive integer is a power of
2 if and only if exactly one bit is equals
1 in its binary representation. So to check if positive integer
x is a power of
2, we can simply compare
x & (x-1) with
What about power of 4? An extension to the power of 2 question is checking whether a positive integer is a power 4.
For a positive integer
n to be a power of
4, it’s necessary that
n be a power of
2. What are some other requirements? Let’s write down some positive integers in their binary forms:
2: 10 4: 100 8: 1000 16: 10000 32: 100000 64: 1000000
Notice that in order for
x to be a power of
4, its only set bit should be at the third, fifth or seventh, etc bit counting from the right. How do we check that? By creating a mask
0b01010101010101010101010101010101 which is
0x55555555 in hex: