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 2^{32} – 1. A lookup table for all 2^{32} – 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
#include <iostream> #include <bitset> using namespace std; // macros to generate the lookup table (at compile-time) #define R2(n) n, n + 2*64, n + 1*64, n + 3*64 #define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16) #define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 ) #define REVERSE_BITS R6(0), R6(2), R6(1), R6(3) // lookup-table to store the reverse of each index of the table // The macro REVERSE_BITS generates the table unsigned int lookup[256] = { REVERSE_BITS }; // Function to reverse bits of n int reverseBits(int n) { // print lookup table (reverse of integer i) /* for (int i = 0; i < 256; i++) cout << i << " reverse is " << (int)lookup[i] << "\n"; */ // assuming 32-bit(4 byte) integer, break the integer into 8-bit chunks // Note mask used 0xff is 11111111 in binary // Split, Reverse and Rearrange each chunk int reverse = lookup[n & 0xff] << 24 | // consider first 8 bits lookup[(n >> 8) & 0xff] << 16 | // consider next 8 bits lookup[(n >> 16) & 0xff] << 8 | // consider next 8 bits lookup[(n >> 24) & 0xff]; // consider last 8 bits return reverse; } // Reverse Bits of an integer using lookup table int main() { int n = 1691315356; cout << n << " in binary is " << bitset<32>(n) << endl; cout << "On reversing bits " << bitset<32>(reverseBits(n)) << endl; } |

`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

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?

Please explain how the preprocessprocessor macros work with an example its not clear by looking at it.