Get this book -> Problems on Array: For Interviews and Competitive Programming

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.