Find maximum of two integers without if-else and comparison

© Parineeth M R

Question 37. Find the maximum of 2 integers without using if-else or any other comparison operator


We can find the maximum of 2 integers without making use of if else or any comparison operator using the function below

C/C++


/*Returns the maximum of x and y without using if-else and comparison*/
int find_max(int x, int y) {
	int difference = x - y;
	int sign_bit = 	(difference >> 31) & 0x1;
	/*
	Sign bit can be 0 or 1
	If sign bit is 0, max = x - (0 * difference) = x
	If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y 
	*/
	int max = x  - (sign_bit * difference);
	return max;
}



Java


/*Returns the maximum of x and y without using if-else and comparison*/
public static int findMax(int x, int y) {
	int difference = x - y;
	int signBit = 	(difference >> 31) & 0x1;
	/*
	Sign bit can be 0 or 1
	If sign bit is 0, max = x - (0 * difference) = x
	If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y 
	*/
	int max = x  - (signBit * difference);
	return max;
}



Python


#Returns the maximum of x and y without using if-else and comparison
# Maximum value of x and y should not exceed 31 bits
def find_max(x, y) :
	difference = x - y
	sign_bit = (difference >> 31) & 0x1
	
	#Sign bit can be 0 or 1
	#If sign bit is 0, max = x - (0 * difference) = x
	#If sign bit is 1, max = x - (1 * (x-y)) = x - x + y = y 
	max_value = x  - (sign_bit * difference)
	return max_value



First we compute the difference between x and y. Next we find the sign bit of the difference. In the 2’s complement notation, the most significant bit indicates the sign of the number. If the sign bit is 0, then the number is positive and if the bit is 1, then the number is negative.

If x >= y, then the difference x – y is positive and so the sign bit of the difference is 0.

If x < y, then the difference x – y is negative and sign bit of the difference is 1.

Then we compute max = x – (sign_bit * difference).

If x >= y, then sign_bit = 0 and max = x – (0 * difference) = x. So we return x as the maximum value

If x < y, then sign_bit = 1 and max = x - (1 * difference) = x - difference = x - (x - y) = y. So we return y as the maximum value

Circular left shift and circular right shift on integer

© Parineeth M R

Question 36. Implement circular shift left and circular shift right on an unsigned integer


Let n be the number of bits to shift. Let m be the total number of bits present in the integer. If we circular shift an integer m times then we get back the original integer. So the actual number of shifts we need to perform is n % m.

The functions for circular shift left (also called left shift rotate) and circular shift right (right shift rotate) are given below

C/C++


/*
input: input value which has to be circularly shifted left
n: number of positions to shift
Return value: result after circularly left shifting input
*/
unsigned int circular_left_shift(unsigned int input, int n)
{
	unsigned int size = sizeof(unsigned int) * 8;
	unsigned int result;
	
	n = n % size;
	result = input << n | input >> (size - n);
	return result;
}


/*
input: input value which has to be circularly shifted right
n: number of positions to shift
Return value: result after circularly right shifting input
*/
unsigned int circular_right_shift(unsigned int input, int n)
{
	unsigned int size = sizeof(int) * 8;
	unsigned int result;

	n = n % size;
	result = input >> n | input << (size - n);
	return result;
}



Java


/*
input: input value which has to be circularly shifted left
n: number of positions to shift
Return value: result after circularly left shifting input
*/
public static int circularLeftShift(int input, int n) {
	int numBitsInInt = 32;
	n = n % numBitsInInt;
	int result = input << n | input >>> (numBitsInInt - n);
	return result;
}


/*
input: input value which has to be circularly shifted right
n: number of positions to shift
Return value: result after circularly right shifting input
*/
public static int circularRightShift(int input, int n) {
	int numBitsInInt = 32;
	n = n % numBitsInInt;
	int result = input >>> n | input << (numBitsInInt - n);
	return result;
}




Python


#value: input value which has to be circularly shifted left
#n: number of positions to shift
#Return value: result after circularly left shifting input value
def circular_left_shift(value, n) :
	num_bits_in_int = 32
	n = n % num_bits_in_int
	mask = (1 << num_bits_in_int) - 1
	result = (value << n) | (value >> (num_bits_in_int - n))
	result = result & mask
	return result


#value: input value which has to be circularly shifted right
#n: number of positions to shift
#Return value: result after circularly right shifting input
def circular_right_shift(value, n) :
	num_bits_in_int = 32
	n = n % num_bits_in_int
	mask = (1 << num_bits_in_int) - 1
	result = (value >> n) | (value << (num_bits_in_int - n))
	result = result & mask
	return result



Copy bits from one integer to another

© Parineeth M R

Question 35. Copy the bits between the specified start bit and end bit positions of one integer into another integer. For instance if source integer is 0xBBB and destination integer is 0xAEC and we copy the bits from 4 to 7 from source to destination, the result is 0xABC


Let the source integer be 0xBBB, destination integer be 0xAEC and we have to copy bits from position 4 to 7. The strategy we use is as follows:

1. Construct a mask (let’s call it ones mask) in which all the bits are initially set to 1. If we need to copy n bits and the total number of bits in the integer is m, then right shift the ones mask by (m-n). So if we need to copy 4 bits between bit 4 and bit 7, and total number of bits in integer is 32, we perform ones_mask >> (32 – 4). So ones_mask will have a value 0xF.

2. Left shift the ones mask to the starting position from where we have to copy the bits. The ones mask will now have 1’s from the start bit position to the end bit position. In this example, starting bit position is 4, so we perform (ones_mask << 4) = (0xF << 4) = 0xF0.

3. Construct a zeroes mask which is the complement of the ones mask. The zeroes mask will have 0’s from the start bit to the end bit. So if ones mask is 0xF0, then zeroes mask will be 0xFFFFFF0F.

4. AND the destination integer with the zeroes mask to clear out the bits in the destination from start bit to end bit. So if destination is 0xAEC, then 0xAEC & 0xFFFFFF0F will give 0xA0C

5. AND the source integer with the ones mask so that only the bits from start and end bit positions remain and the rest of the bits are cleared. If the source integer is 0xBBB, then 0xBBB & 0xF0 will give 0xB0

6. OR the source and destination. So 0xA0C | 0xB0 will give 0xABC

C/C++


/*
dest: destination integer into which the bits have to be copied
src: source integer from which the bits have to be copied 
end_pos: Most Significant bit position upto where the bits should be copied
start_pos: Least Significant bit position from where the bits should be copied
	end_pos should be >= start_pos
Return value: result integer after copying bits from source to destination
*/
unsigned int copy_bits(unsigned int dest, unsigned int src, 
			unsigned int end_pos, unsigned int start_pos)
{
	unsigned int num_bits_to_copy = end_pos - start_pos + 1;
	unsigned int num_bits_in_int = sizeof(unsigned int) * 8;
	unsigned int zeroes_mask;
	unsigned int ones_mask = ~((unsigned int) 0); /*all ones*/

	/*Use the bit-wise right shift operator to remove the excess 1's 
	in the mask*/
	ones_mask = ones_mask >> (num_bits_in_int - num_bits_to_copy);

	/*Left shift the 1's to the starting position. ones_mask will contain 1's
	from start_pos to end_pos*/
	ones_mask = ones_mask << start_pos;

	/*zeroes_mask will contain 0's from start_pos to end_pos*/
	zeroes_mask = ~ones_mask;

	/*clear the bits in destination from start_pos to end_pos*/
	dest = dest & zeroes_mask;

	/*retain the bits in source from start_pos to end_pos and clear the 
	remaining bits*/
	src = src & ones_mask;
	
	/*copy the source bits into the destination*/
	dest = dest | src;
	
	return dest;
}




Java


/*
dest: destination integer into which the bits have to be copied
src: source integer from which the bits have to be copied 
endPos: Most Significant bit position upto where the bits should be copied
startPos: Least Significant bit position from where the bits should be copied
	endPos should be >= startPos
Return value: result integer after copying bits from source to destination
*/
public static int copyBits(int dest, int src,  int endPos,  int startPos) {
	 int numBitsToCopy = endPos - startPos + 1;
	 int numBitsInInt = 32;
	 int onesMask = ~(0); /*Initialize the mask to all 1's*/

	/*Use the bit-wise right shift operator to remove the excess 1's 
	in the mask*/
	onesMask = onesMask >>> (numBitsInInt - numBitsToCopy);

	/*Left shift the 1's to the starting position. onesMask will contain 
	1's from startPos to endPos*/
	onesMask = onesMask << startPos;

	/*zeroesMask will contain 0's from startPos to endPos*/
	int zeroesMask = ~onesMask;

	/*clear the bits in destination from startPos to endPos*/
	dest = dest & zeroesMask;

	/*retain the bits in source from startPos to endPos and clear 
	the remaining bits*/
	src = src & onesMask;

	/*copy the source bits into the destination*/
	dest = dest | src;

	return dest;
}



Python


#dest: destination integer into which the bits have to be copied
#src: source integer from which the bits have to be copied 
#end_pos: Most Significant bit position upto where the bits should be copied
#start_pos: Least Significant bit position from where the bits should be copied
#	end_pos should be >= start_pos
#Return value: result integer after copying bits from source to destination
def copy_bits(dest,  src,  end_pos,  start_pos) :
	num_bits_to_copy = end_pos - start_pos + 1
	num_bits_in_int = 32
	ones_mask = (1 << 32) - 1

	#Use the bit-wise right shift operator to remove the excess 1's 
	#in the mask
	ones_mask = ones_mask >> (num_bits_in_int - num_bits_to_copy)

	#Left shift the 1's to the starting position. ones_mask will contain 1's
	#from start_pos to end_pos
	ones_mask = ones_mask << start_pos

	#zeroes_mask will contain 0's from start_pos to end_pos
	zeroes_mask = ~ones_mask

	#clear the bits in destination from start_pos to end_pos
	dest = dest & zeroes_mask

	#retain the bits in source from start_pos to end_pos and 
	#clear the remaining bits
	src = src & ones_mask

	#copy the source bits into the destination
	dest = dest | src

	return dest



Compute parity bit

© Parineeth M R

Question 34. Given an integer, compute the parity bit for the integer


There are two types of parity bit schemes

1. Even parity: if the total number of 1’s is odd, then the parity bit will be 1 to make the total number of 1’s (including the parity bit) even

2. Odd parity: if the total number of 1’s is even, then the parity bit will be 1 to make the total number of 1’s (including the parity bit) odd.

We will implement an even parity scheme here. We count the number of 1’s in the integer using the scheme described in problem 29

C/C++


/*
x: input integer
Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
*/
unsigned int compute_parity(unsigned int x) 
{
	/*for each bit set to 1 in x, toggle the parity bit*/
	unsigned int parity = 0;
	while (x != 0) {
		parity = parity ^ 1;
		x = x & (x - 1);
	}

	return parity;
}



Java


/*
x: input integer
Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
*/
public static int computeParity( int x) {
	/*for each bit set to 1 in x, toggle the parity bit*/
	int parity = 0;
	while (x != 0) {
		parity = parity ^ 1;
		x = x & (x - 1);
	}

	return parity;
}



Python


#x: input integer
#Return value: parity bit, 1 if there are odd number of 1's, 0 otherwise
def compute_parity(x):
	#for each bit set to 1 in x, toggle the parity bit
	parity = 0
	while (x):
		parity = parity ^ 1
		x = x & (x - 1)

	return parity



Swap bits in an integer

© Parineeth M R

Question 33. Given an integer, swap the bit at position 1 with the bit at position 2


We first extract the bits at position 1 and position 2. We then have to swap the two bits only if the two bits are different. The code for swapping the bits is given below

C/C++


/*
x: integer in which the bits should be swapped
pos1: position of first bit to be swapped
pos2: position of the second bit to be swapped
*/
unsigned int swap_bits(unsigned int x, int pos1, int pos2) 
{
	/*get the bits at position pos1 and pos2*/
	int bit1 = (x >> pos1) & 1;
	int bit2 = (x >> pos2) & 1;

	/*swap the bits if the bits are different*/
	if (bit1 != bit2) {
		x = write_bit(x, bit1, pos2);
		x = write_bit(x, bit2, pos1);
	}

	return x;
}

/*writes the bit_value (0/1) into position pos in x and returns the result*/
unsigned int write_bit(unsigned int x, int bit_value, int pos) 
{
	unsigned int mask = 1 << pos;
	if (bit_value)
		x = x | mask;
	else
		x = x & ~mask;

	return x;
}




Java


/*
x: integer in which the bits should be swapped
pos1: position of first bit to be swapped
pos2: position of the second bit to be swapped
*/
public static int swapBits(int x, int pos1, int pos2) {
	/*get the bits at position pos1 and pos2*/
	int bit1 = (x >> pos1) & 1;
	int bit2 = (x >> pos2) & 1;

	/*swap the bits*/
	if (bit1 != bit2) {
		x = writeBit(x, bit1, pos2);
		x = writeBit(x, bit2, pos1);
	}

	return x;
}

 
/*writes the bitValue (0/1) into position pos in x and returns the result*/
public static int writeBit( int x, int bitValue, int pos)  {
	int mask = 1 << pos;
	if (bitValue == 1)
		x = x | mask;
	else
		x = x & ~mask;

	return x;
}



Python


#writes the bit_value (0/1) into position pos in x and returns the result
def write_bit(x, bit_value, pos):
	mask = 1 << pos
	if (bit_value == 1):
		x = x | mask
	else:
		x = x & ~mask

	return x

#x: integer in which the bits should be swapped
#pos1: position of first bit to be swapped
#pos2: position of the second bit to be swapped
def swap_bits(x, pos1, pos2):
	#get the bits at position pos1 and pos2
	bit1 = (x >> pos1) & 1
	bit2 = (x >> pos2) & 1

	#swap the bits
	if (bit1 != bit2) :
		x = write_bit(x, bit1, pos2)
		x = write_bit(x, bit2, pos1)

	return x




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     



Reverse the bits in an integer

© Parineeth M R

Question 31. Reverse the bits in an integer


We can reverse the bits in an integer one bit at a time. However there is a faster technique. To reverse the bits in an integer efficiently, a lookup table is pre-computed to give the reverse values for every byte. This lookup table is then referred to for performing the reversal of the integer. The code for this is given below

C/C++


/*
input_value: the integer that has to be reversed
reverse_table: lookup table that has the reversed values for every byte.
	Example - reverse_table[0x1] = 0x80, since reverse of 00000001 is 1000000
Return value: integer that is the reverse of the input integer
*/
unsigned int reverse_integer(unsigned int input_value, 
				unsigned char reverse_table[])
{
	unsigned int result = 0;
	int i = 0;
	int num_bytes = sizeof(int);

	for (i = 0; i < num_bytes; ++i) {
		/*Get the least significant byte from the input*/
		int cur_byte_value = input_value & 0xFF;

		/*Left shift the result by 8 and append the reverse of the 
		LS byte of input*/
		result = (result << 8) | reverse_table[cur_byte_value];

		/*Right shift out the least significant byte from the input*/
		input_value = input_value >> 8;
	}
	return result;
}




Java


/*
inputValue: the integer that has to be reversed
reverseTable: lookup table that has the reversed values for every byte.
	 Example - reverseTable[0x1] = 0x80, since reverse of 00000001 is 1000000
Return value: integer that is the reverse of the input integer
*/
public static int reverseInteger( int inputValue,  char[] reverseTable) {
	int result = 0;
	int i = 0;
	int numBytes = 4;

	for (i = 0; i < numBytes; ++i) {
		/*Get the least significant byte from the input*/
		int curByteValue = inputValue & 0xFF;

		/*Left shift the result by 8 and append the reverse of the 
		LS byte of input*/
		result = (result << 8) | reverseTable[curByteValue];

		/*Right shift out the least significant byte from the input*/
		inputValue = inputValue >> 8;
	}

	return result;
}




Python


#input_value: the integer that has to be reversed
#reverse_table: lookup table that has the reversed values for every byte.
#	Example: reverse_table[0x1] = 0x80, since reverse of 00000001 is 1000000
#Return value:  integer that is the reverse of the input integer
def reverse_integer(input_value,  reverse_table) :
	result = 0
	num_bytes = 4
	for  i in range(0, num_bytes):
		#Get the least significant byte from the input
		cur_byte_value = input_value & 0xFF
		
		#Left shift the result by 8 and append the reverse of the 
		#least significant byte of input		
		result = (result << 8) | reverse_table[cur_byte_value]

		#Right shift out the least significant byte from the input
		input_value = input_value >> 8
	
	return result



Find if an integer is a power of 2

© Parineeth M R

Question 30. Find if an integer is a power of 2 using bit wise operators


The condition (x & (x-1) == 0) checks if an integer is a power of 2 or not. From the previous question, we know that x & (x-1) will reset the first bit that has a value of 1 from the right to 0. If x is a power of 2, then only one of the bits will be set to 1 and all the remaining bits will be set to 0 (for instance, 8 is a power of 2 and 8 in binary is 1000). So x & (x-1) will reset the only bit that has a value of 1 resulting in 0.

x & (x-1) == 0 however incorrectly indicates that 0 is also a power of 2, since (0 & (0 – 1) ) = (0 & 0xffffffff) = 0. Since 0 is not a power of 2, we modify the condition as shown below

C/C++


(x != 0) && (x & (x-1) == 0)


Java


(x != 0) && ((x & (x-1)) == 0)


Python


(x != 0) and ((x & (x-1)) == 0)


Efficiently count the number of bits set in an integer

© Parineeth M R

Question 29. Efficiently count the number of bits set in an integer


One way to find the number of bits set in an integer is to check each bit. However there is a faster method to count the number of bits set using the function below

C/C++


unsigned int count_num_bits_set(unsigned int n)
{
	unsigned int count = 0;
	
	while (n) {
		n &= n - 1;
		count++;
	}

	return count;
}



Java


public static int countNumBitsSet(int n) {
	int count = 0;

	while (n != 0) {
		n &= n - 1;
		count++;
	}

	return count;
}



Python


#Returns the number of bits set to 1 in n
def count_num_bits_set(n) :
	count = 0

	while (n != 0) :
		n &= n - 1
		count += 1
	
	return count



The following code works because each time we perform the operation n &= n – 1, the first bit that has a value of 1 from the right (from the least significant bit) is reset to 0.

For instance if n = 1100, then

So 1100 is converted to 1000 where in the first bit that has a value of 1 from the right in 1100 is now reset to 0.