Reverse Bits

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.

Rules for addition:

This table is known as the truth table. It is used to find the output of binary bitwise operations like addition, subtraction, etc.

• More complex problems related to bitwise operations and binary representations come under bit manipulation which is commonly asked in competitive programming.

But the basics of bit manipulation is how different data structures are represented in binary form.

References