Reverse the bits in an integer – The Coding Interview Blog

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