Reverse Bits of an integer using lookup table

Given an integer, reverse its bits using binary operators and lookup table in O(1) time.


 

For example, 1691315356 in binary is 01100100110011110110110010011100. On reversing its bits, we get 00111001001101101111001100100110
 

We have discussed two solutions to reverse bits of a number in previous post. Both have worst case time complexity of O(log(n)). In this post, a O(1) time solution is discussed.
 

The idea is to use a lookup table to return reverse of a number in constant time. An integer in C/C++ usually takes 4 bytes for storage. That means maximum number it can store is 232 – 1. A lookup table for all 232 – 1 integers will be infeasible (Not to forget, we have negative numbers too). The trick is to create an 8-bit (1 byte) version of the table, then iterate over each byte in the integer to be checked and summing the results of the table lookup.

1 byte with all its bits set is 255 in decimal (11111111 in binary) and all bits unset is 0 in decimal (00000000 in binary). So lookup table should be of size 256 (0-255).
 

In the solution below, we’re using the macros to generate the lookup table. The lookup table will be generated at compile time by preprocessor. The first and last few numbers of the sequence will be
{ 0, 128, 64, 192, 32, 160, . . . , 95, 223, 63, 191, 127, 255 } as

0 reverse is 0
1 reverse is 128
2 reverse is 64
3 reverse is 192
4 reverse is 32
5 reverse is 160

..
250 reverse is 95
251 reverse is 223
252 reverse is 63
253 reverse is 191
254 reverse is 127
255 reverse is 255

 

Consider binary number 01100100110011110110110010011100, the process can be summarized as ‘Split, Reverse and Rearrange’ –

1. Split the integer into 8-bit chunks

01100100 | 11001111 | 01101100 | 10011100

 

2. Reverse the chunks using lookup table

lookup[10011100] = 00111001
lookup[01101100] = 00110110
lookup[11001111] = 11110011
lookup[01100100] = 00100110

00100110 | 11110011 | 00110110 | 00111001

 

3. Rearrange chunks

00111001 | 00110110 | 11110011 | 00100110

 

In the C++ solution below, Split, Reverse and Rearrange happens in single expression for each chunk.

 

Download   Run Code

Output:

1691315356 in binary is 01100100110011110110110010011100
On reversing bits 00111001001101101111001100100110

 

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
Sort by:   newest | oldest | most voted
yesyesyes
Guest
yesyesyes

Splitting the 32 bits integer into 32 1 bits chunks makes the lookup table a lot smaller and is still O(1) (assuming we only handle 32 bit integers, but you assumed that above as well) or am I being a smartass here?

wpDiscuz