Reverse bits of an Integer

In this article, we have explored an efficient algorithm to Reverse bits of an Integer. The challenge is to do this in-place without using auxiliary memory.

Table of contents:

1. Problem statement
2. Algorithm to reverse bits
3. Pseudocode
4. Code
5. Step by Step Explanation
6. Time and Space Complexity

Let us get started with Reverse bits of an Integer.

Problem statement

Given a 32 bit unsigned integer N, we have to reverse bits of a the given 32 bits unsigned integer

**Ex: **

lets N = 255 (0b 00000000000000000000000011111111)

After reversing bits binary form of result will be
(0b 11111111000000000000000000000000)
which is 4278190080 in decimal

Hence, result will be 4278190080

Algorithm to reverse bits

We will solve this using bit manipulation.

Given that N is 32 bit unsigned integer.

First we will initialize unsigned int reverse in which we will store result
and initialize reverse with 0 [reverse=0]

In this method we will compare 0th bit of N and
insert that binary value from 0^th bit of N in 0^th bit of reverse.
Then we will right shift N by 1
and left shift reverse by 1

as the 0^th bit will get stored in 0th bit of reverse and when we right shift N and left shift reverse by 1 and repeat this process the lowest bits of N will get stored in highest bits of reverse

and as the size of int is 32 bit so we will repeat this 32 times

then,

• 0th bit of N will get stored at 31st bit of reverse
• 1st bit of N will get stored at 30th bit of reverse
• 2nd bit of N will get stored at 29th bit of reverse
• 3rd bit of N will get stored at 28th bit of reverse
• same for rest of bits

For repeating we can any of the loop statement

Pseudocode

• Take input N
• Initialize unsigned 32 bit int reverse = 0
• Repeat while loop times
  • if 0th bit of N is 1 then set 0th bit of revsere to 1
  • right shift N by 1
  • left shift reverse by 1
• Print reverse

Code

Following is the implementation in C++:

#include<bits/stdc++.h>
using namespace std;

void solve() {
    uint32_t n, reverse=0; cin>>n; 
    int i=1;
    while(1) {
        reverse |= (n&1);
        if(i==8*sizeof(uint32_t)) break;
        reverse <<= 1; n>>=1;
        i += 1;
    }
    cout<<reverse<<endl;
}
int main(){
    solve();
    return 0;
}

Step by Step Explanation

Lets N = 255

binary representation of N => 00000000000000000000000011111111

initially reverse = 0

binary representation of reverse => 00000000000000000000000000000000

In First Iteration

First we will store 0th bit value of N in 0th bit of reverse

N       => 00000000000000000000000011111111

reverse => 00000000000000000000000000000000

then reverse will be => 00000000000000000000000000000001

and then we will left shift reverse and right shift N by 1
then,

N       => 00000000000000000000000001111111

reverse => 00000000000000000000000000000010

In Second Iteration

First we will store 0th bit value of N in 0th bit of reverse

N       => 00000000000000000000000001111111

reverse => 00000000000000000000000000000010

then reverse will be => 00000000000000000000000000000011

and then we will left shift reverse and right shift N by 1
then,

N       => 00000000000000000000000000111111

reverse => 00000000000000000000000000000110

same process we will repeat 32 times to get our result
and after last iteration we will get

N

• Binary => 00000000000000000000000000000000
• Decimal => 0

reverse

• Binary => 11111111000000000000000000000000
• Decimal = 4278190080

Therefore,
result for N=225 will be 4278190080

Time and Space Complexity

Time complexity

Time Complexity to reverse bits of a number of order O(N) is O(logN) as there are O(logN) bits in a number of order O(N).

Therefore, for Integers of size 32 bits, the Time Complexity is O(32).

• As we are executing loop with 32 iterations

Space complexity

The space complexity is O(1).

• we are creating very few variables ( 1-2 variables )

With this article at OpenGenus, you must have the complete knowledge of reversing bits of an Integer.