×

Search anything:

# Reverse bits of an Integer

#### Algorithms List of Mathematical Algorithms

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.

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 0th bit of N in 0th bit of reverse.
Then we will right shift `N` by 1
and left shift `reverse` by 1

as the 0th 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.

#### Vikram Shishupalsingh Bais

Vikram Shishupalsingh Bais is an Open source enthusiast, competitive programmer skilled in programming languages C++, Python, Java, C. He has been an Intern at OpenGenus.

Reverse bits of an Integer