# Reverse Bits

Difficulty Level Easy
Bit Bit Manipulation BitsViews 2027

Reverse bits of a given 32 bits unsigned integer.

## Example

Input

43261596  (00000010100101000001111010011100)

Output

964176192 (00111001011110000010100101000000)

A 32-bit unsigned integer refers to a nonnegative number which can be represented with a string of 32 characters where each character can be either ‘0’ or ‘1’.

## Algorithm

1. for i in range 0 to 15
• If the ith bit from the beginning and from the end is not the same then flip it.
2. Print the number in binary.

## Explanation

1. We swap the bits only when they are different because swapping the bits when they are the same does not change our final answer.
2. To swap two different bits, we flip the individual’s bits by using the XOR operator. ## Implementation

### C++ Program for Reverse Bits

```#include <bits/stdc++.h>
using namespace std;
void Reverse(uint32_t n)
{
for (int i = 0; i < 16; i++)
{
bool temp = (n & (1 << i));
bool temp1 = (n & (1 << (31 - i)));
if (temp1 != temp)
{
n ^= (1 << i);
n ^= (1 << (31 - i));
}
}
for (int i = 31; i >= 0; i--)
{
bool temp = (n & (1 << i));
cout << temp;
}
cout << endl;
}
int main()
{
uint32_t n;
cin >> n;
Reverse(n);
return 0;
}
```
`43261596`
`00111001011110000010100101000000`

### JAVA Program for Reverse Bits

```import java.util.*;

public class Main
{
public static void Reverse(int n)
{
for (int i = 0; i < 16; i++)
{
int temp = (n & (1 << i));
temp = temp==0? 0: 1;
int temp1 = (n & (1 << (31 - i)));
temp1 = temp1==0? 0: 1;
if (temp1 != temp)
{
n ^= (1 << i);
n ^= (1 << (31 - i));
}
}
for (int i = 31; i >= 0; i--)
{
int temp = (n & (1 << i));
temp = temp==0? 0: 1;
System.out.print(temp);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner( System.in ) ;
int n=sc.nextInt();
Reverse(n);
}
}

```
`3456785`
`10001000111111010010110000000000`

## Complexity Analysis for reverse bits

### Time complexity

We traverse only on 16 bits so time complexity is O(16) which is basically O(1).

### Space complexity

It is also O(1) as we only took 2 extra bool type variable.

## Variation of reverse bits

• In this question, we were asked to reverse bits of the given unsigned integer, but the same question can be modified as find the complement of the given unsigned integer.

Now, what is the complement of a given number?

`A number obtained by toggling the state of each binary character in the given binary representation of integer is known as the complement of that number.`

Hence to do that we can simply change all 0’s to 1 and all 1’s to 0 in the given binary string.

### Example

If the given number is 20, then it’s binary representation will be 10100

Hence it’s complement will be 01011.

### Implementation

```#include<bits/stdc++.h>
using namespace std;
int main(){
int n = 20;
string ans;
while(n){
if(n%2==0){
ans = '1'+ans;
}
else{
ans = '0'+ans;
}
n/=2;
}
cout<<"Complement of the given number is: "<<ans;
}```
`Complement of the given number is: 01011`
• Many questions can be framed on the binary representation of integers like the addition of two binary strings. To solve such kind of questions one should know about the rules of binary addition. 