Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

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:

- Problem statement
- Algorithm to reverse bits
- Pseudocode
- Code
- Step by Step Explanation
- 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.