© 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