Number of Bits Set
Problem
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.
Brian Kernighan’s Algorithm
Notice that for any integer n, doing a bit-wise AND of n and n-1 has the effect of flipping the least-significant 1 bit in n to 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:
def count_set_bits(x):
count = 0
while x:
x &= x - 1
count += 1
return count
Hamming Distance
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 x and y by invoking count_set_bits(x ^ y).
Power of 2
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 0:
def is_power_of_2(x):
"""Checks whether a positive integer is a power of 2."""
return x & (x-1) == 0
Power of 4
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:
def is_power_of_4(x):
"""Checks whether a positive integer is a power of 4."""
mask = 0x55555555
return is_power_of_2(x) and (x & mask)