Python: Bitwise Magic

In this post, let’s have a look at bitwise XOR, bitwise AND and a program that calculates number of 1’s in a given integer’s binary form.

Here’s XOR ^ and AND & operations table:

1. bitwise XOR will return 0 if inputs are same, else it’ll return 1
2. bitwise AND will return 1 if both inputs are 1

Now look at the magic in the code below. To be specific, check out the highlighted line:

def count_ones(z):
 
	count = 0
 
	while z:
		print(z, bin(z))
		count += 1
		z = z & (z-1)
 
	return count
 
print('The number of 1s in 5: ', count_ones(5))
print()
print('The number of 1s in 28: ', count_ones(28))
 
#output
 
# 5 0b101
# 4 0b100
# The number of 1s in 5:  2
 
# 28 0b11100
# 24 0b11000
# 16 0b10000
# The number of 1s in 28:  3

The code above takes an integer, finds out how many 1s are there in its binary form and returns the number of 1s.

This is done using z = z & (z-1) which basically removes the rightmost one from the integer’s binary form.

For example, 28 can be written as 11100. It turns into 11000 in the first pass. 10000 in the second and 00000 in the third pass. Then the loop stops to return the count which is 3.

This can be very useful in calculating hamming distance. What is hamming distance you say? Here’s a quote from Wikipedia:

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

For example, the hamming distance between 1 and 4 is 2:

The simple logic to calculate this is to use bitwise XOR there. In this case 1 ^ 4 will return 5 which is 101 in binary. It has 2 ones in it.

How do we find these 2 ones in there using code? We combine bitwise XOR with bitwise AND as follows:

def hamming(x,y):
 
	count = 0
	z = x ^ y
 
	while z:
		print(z, bin(z))
		count += 1
		z = z & (z-1)
 
 
	return count
 
print(hamming(1,4))
 
#output
# 5 0b101
# 4 0b100
# 2

This is pretty cool right? That’s all I have in this post. See you tomorrow with another interesting CS concept. Thanks for reading!