reverse a number's bits

Question

Here is a C++ class for revering bits from LeetCode discuss. https://leetcode.com/discuss/29324/c-solution-9ms-without-loop-without-calculation For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as 00111001011110000010100101000000).

Is there anyone can explain it? Thank you so very much!!

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        struct bs
        {
            unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
            unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
            unsigned int _08:1; unsigned int _09:1; unsigned int _10:1; unsigned int _11:1;
            unsigned int _12:1; unsigned int _13:1; unsigned int _14:1; unsigned int _15:1;
            unsigned int _16:1; unsigned int _17:1; unsigned int _18:1; unsigned int _19:1;
            unsigned int _20:1; unsigned int _21:1; unsigned int _22:1; unsigned int _23:1;
            unsigned int _24:1; unsigned int _25:1; unsigned int _26:1; unsigned int _27:1;
            unsigned int _28:1; unsigned int _29:1; unsigned int _30:1; unsigned int _31:1;
        } *b = (bs*)&n, 
        c = 
        {
              b->_31, b->_30, b->_29, b->_28
            , b->_27, b->_26, b->_25, b->_24
            , b->_23, b->_22, b->_21, b->_20
            , b->_19, b->_18, b->_17, b->_16
            , b->_15, b->_14, b->_13, b->_12
            , b->_11, b->_10, b->_09, b->_08
            , b->_07, b->_06, b->_05, b->_04
            , b->_03, b->_02, b->_01, b->_00
        };

        return *(unsigned int *)&c;
    }
};

Answer 1

Consider casting as providing a different layout stencil on memory.

Using this stencil picture, the code is a layout of a stencil of 32-bits on an unsigned integer memory location.

So instead of treating the memory as a uint32_t, it is treating the memory as 32 bits.

A pointer to the 32-bit structure is created.

The pointer is assigned to the same memory location as the uint32_t variable.

The pointer will allow different treatment of the memory location.

A temporary variable, of 32-bits (using the structure), is created. The variable is initialized using an initialization list.
The bit fields in the initialization list are from the original variable, listed in reverse order.

So, in the list:

  new bit 0 <-- old bit 31  
  new bit 1 <-- old bit 30  

The foundation of this approach relies on initialization lists. The author is letting the compiler reverse the bits.

Answer 2

First of all, the posted code has a small bug. The line

return *(unsigned int *)&c;

will not return an accurate number if sizeof(unsigned int) is not equal to sizeof(uint32_t).

That line should be

return *(uint32_t*)&c;

Coming to the question of how it works, I will try to explain it with a smaller type, an uint8_t.

The function

uint8_t reverseBits(uint8_t n) {
    struct bs
    {
        unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
        unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
    } *b = (bs*)&n, 
    c = 
    {
          b->_07, b->_06, b->_05, b->_04
        , b->_03, b->_02, b->_01, b->_00
    };

    return *(uint8_t *)&c;
}

uses a local struct. The local struct is defined as:

    struct bs
    {
        unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
        unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
    };

That struct has eight members. Each member of the struct is a bitfield of width 1. The space required for an object of type bs is 8 bits.

If you separate the definition of the struct and the variables of that type, the function will be:

uint8_t reverseBits(uint8_t n) {
    struct bs
    {
        unsigned int _00:1; unsigned int _01:1; unsigned int _02:1; unsigned int _03:1;
        unsigned int _04:1; unsigned int _05:1; unsigned int _06:1; unsigned int _07:1;
    };

    bs *b = (bs*)&n;
    bs c =
    {
         b->_07, b->_06, b->_05, b->_04
       , b->_03, b->_02, b->_01, b->_00
    };

    return *(uint8_t *)&c;
}

Now, lets' say the input to the function is 0xB7, which is 1011 0111 in binary. The line

    bs *b = (bs*)&n;

says:

1. Take the address of n ( &n )
2. Treat it like it is a pointer of type bs* ( (bs*)&n )
3. Assign the pointer to a variable. (bs *b =)

By doing that, we are able to pick each bit of n and get their values by using the members of b. At the end of that line,

The value of b->_00 is 1
The value of b->_01 is 0
The value of b->_02 is 1
The value of b->_03 is 1
The value of b->_04 is 0
The value of b->_05 is 1
The value of b->_06 is 1
The value of b->_07 is 1

The statement

    bs c =
    {
         b->_07, b->_06, b->_05, b->_04
       , b->_03, b->_02, b->_01, b->_00
    };

simply creates c such that the bits of c are reversed from the bits of *b.

The line

    return *(uint8_t *)&c;

says:

1. Take the address of c., whose value is the bit pattern 1110 1101.
2. Treat it like it is a pointer of type uint8_t*.
3. Dereference the pointer and return the resulting uint8_t

That returns an uint8_t whose value is bitwise reversed from the input argument.

Answer 3

The solution uses brute force to revert the bits. It declares a bitfield structure (that's when the members are followed by :1) with 32 bit fields of one bit each. The 32 bit input is then seen as such structure, by casting the address of the input to a pointer to the structure. Then c is declared as a variable of that type which is initialized by reverting the order of the bits. Finally, the bitfield represented by c is reinterpreted as an integer and you're done.

The assembler is not very interesting, as the gcc explorer shows: https://goo.gl/KYHDY6

Answer 4

It doesn't convert per see, but it just looks at the same memory address differently. It uses the value of the int n, but gets a pointer to that address, typecasts the pointer, and that way, you can interpret the number as a struct of 32 individual bits. So through this struct b you have access to the individual bits of the number.

Then, of a new struct c, each bit is bluntly set by putting bit 31 of the number in bit 0 of the output struct c, bit 30 in bit 1, etcetera.

After that, the value at the memory location of the struct is returned.

Answer 5

This isn't exactly obfuscated but a comment or two would assist the innocent. The key is in the middle of the variable declarations, and the first step is to recognize that there is only one line of 'code' here, everything else is variable declarations and initialization.

Between declaration and initialization we find:

} *b = (bs*)&n,
c =
{

This declares a variable 'b' which is a pointer (*) to a struct "bs" just defined. It then casts the address of function argument 'n', a unit_32_t, to the type pointer-to-bs, and assigns it to 'b', effectively creating a union of uint_32_t and the bit array bs. A second variable, an actual struct bs, named "c", is then declared, and it is initialized through the pointer 'b'. b->_31 initializes c._00, and so on. So after "b" and "c" are created, in that order, there's nothing left to do but return the value of "c".

The author of the code, and the compiler, know that after a struct definition ends, variables of that type or related to that type can be created, before ";", and that's why @Thomas Matthews closes with, "The author is letting the compiler reverse the bits."