Fast(3ms) and easy-understand solution in C/C++

• My solution is not very good. However it is quite easy to understand. No magics and no tricks.

Process

Suppose we will reverse a bit space named `s`,

1. allocate an empty space(0) named `z`, and an space whose highest bit is 1 named `i`.

2. check if the lowest(last) bit of `s` is 1,

``````if (s & 1) { }
``````

if true, then do Bitwise OR:

``````z |= i;
``````
3. Right shift `z` and `i` and do step 2 until z is empty space(zero).

Illustration

Here I will use a byte to illustrate it.

z = 0000-0000
i = 1000-0000

Suppose s = 0000-1001

After each step:

1. z = 1000-0000
i = 0100-0000
s = 0000-0100

2. z = 1000-0000
i = 0010-0000
s = 0000-0010

3. z = 1000-0000
i = 0001-0000
s = 0000-0001

4. z = 1001-0000
i = 0000-1000
s = 0000-0000
s is zero, stop the loop.

Code sample

``````
uint32_t reverseBits(uint32_t s) {
uint32_t z = 0,  i = 1 << 31;

while ( s ) {
if (s & 1) z |= i;
s >>= 1;
i >>= 1;
}

return i;
}
``````

Analysis

Time Complexity(N bits): O(N). With average O(N/2), worst O(N).
Space Complexity: O(2N).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.