Reverse bits of an integer

Question

I came through an interview question. Reverse bits of a 32 bit unsigned integer. I wrote this code which is completely okay:

uint32_t reverseBits(uint32_t n) {
    for(int i = 0, j = 31; i < j; i++, j--) {
        bool iSet = (bool)(n & (1 << i));
        bool jSet = (bool)(n & (1 << j));
        n &= ~(1 << j);
        n &= ~(1 << i);
        if(iSet) n |= (1 << j);
        if(jSet) n |= (1 << i);
    }
    return n;
}

After this, there was a follow up question - If this function is called many times, how would you optimize it? I can not figure out how the solution should be optimized in that scenario.

Obligatory link to [Bit Twiddling Hacks](https://graphics.stanford.edu/~seander/bithacks.html#BitReverseObvious). — zch, Sep 25 '18 at 21:09
Working code that you think can be made better? This looks like a job for [Coooooooode Review!](https://codereview.stackexchange.com/help/asking) I've linked to the how to ask page because it's worth a read to make sure any posts you make meet their requirements. — user4581301, Sep 25 '18 at 21:19

Mayur · Answer 1 · 2018-09-25T21:21:00.977

5

You can optimize the loop by using a reverse lookup table.
For more detailed information you can follow this URL from which I have taken below code.

// Generate a lookup table for 32bit operating system 
// using macro 
#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 )

// Lookup table that store the reverse of each table
unsigned int lookuptable[256] = { R6(0), R6(2), R6(1), R6(3) };

/* Function to reverse bits of num */
int reverseBits(unsigned int num)
{
    int reverse_num = 0;

     // Reverse and then rearrange 

                   // first chunk of 8 bits from right
     reverse_num = lookuptable[ num & 0xff ]<<24 | 

                   // second chunk of 8 bits from  right 
                   lookuptable[ (num >> 8) & 0xff ]<<16 | 

                   lookuptable[ (num >> 16 )& 0xff ]<< 8 |
                   lookuptable[ (num >>24 ) & 0xff ] ;

    return reverse_num;
}

edited Sep 25 '18 at 21:21

answered Sep 25 '18 at 21:10

Mayur

2,583
16
28

1

You should probably mention the source of this. – m69's been on strike for years Sep 25 '18 at 21:13
Hi @m69 I have added source. – Mayur Sep 25 '18 at 21:16
3

GeeksforGeeks themselves seem to have copied it from the link @zch posted, without mentioning this :-) https://graphics.stanford.edu/~seander/bithacks.html#BitReverseTable – m69's been on strike for years Sep 25 '18 at 21:19
@m69 Thanks for mentioning the real source, I have updated source URL. – Mayur Sep 25 '18 at 21:21
1

@m69 That geeks site does cite the source but only on a [previous post](https://www.geeksforgeeks.org/write-an-efficient-c-program-to-reverse-bits-of-a-number/) on the same subject matter. – Blastfurnace Sep 25 '18 at 21:21
thanks for your answer. I couldn\t understand the creation of lookup table by macro part, not even from geeksforgeeks – Kaidul Sep 25 '18 at 21:22
@Kaidul lookup table stores reverse of every number that is in a range( 0-255) – Mayur Sep 25 '18 at 21:26
but how the macros represent that? – Kaidul Sep 25 '18 at 21:27

Reverse bits of an integer

1 Answers1