Find the number of bits that are different between the two integers

© Parineeth M R

Question 32. Given two integers, find the number of bits that are different between the two integers


Consider the integers 2 (0010 in binary) and 9 (1001). Three bits are different and one bit is identical. To efficiently find the number of bits that are different, we do the following

1. XOR the two integers.

2. In the result of the XOR, if the bit is 1, then the two integers are different at this bit position. So the number of 1’s present in the result gives the number of different bits between the two integers. For counting the number of 1’s in the result, we make use of the technique we described in problem 29

C/C++


/*
a, b: the two input integers
Return value: Number of bits that have different values in a and b
*/
unsigned int count_different_bits(unsigned int a, unsigned int b)
{
	unsigned int c = a ^ b; 
	unsigned int count = 0;

	/*Since c = a xor b, the positions where a and b are different will 
	be set to 1 in c. So by counting the number 1's in c, we will get the 
	number of bits that are different between a and b*/
	while (c != 0) {
		count++;
		c = c & (c - 1);
	}

	return count;
}



Java


/*
a, b: the two input integers
Return value: Number of bits that have different values in a and b
*/
public static int countDifferentBits( int a,  int b) {
	 int c = a ^ b;
	 int count = 0;

	/*Since c = a xor b, the positions where a and b are different will 
	be set to 1 in c. So by counting the number 1's in c, we will get the
	number of bits that are different between a and b*/
	while (c != 0) {
		count++;
		c = c & (c - 1);
	}

	return count;
} 



Python


#a, b: the two input integers
#Return value: Number of bits that have different values in a and b
def count_different_bits( a,  b) :
	c = a ^ b
	count = 0

	#Since c = a xor b, the positions where a and b are different will 
	#be set to 1 in c. So by counting the number of 1's in c, we will get the
	#number of bits that are different between a and b
	while (c != 0) :
		count += 1
		c = c & (c - 1)
	
	return count