Given a non-negative integer n. The problem is to reverse the bits of n and print the number obtained after reversing the bits. Note that the actual binary representation of the number is being considered for reversing the bits, no leadings 0’s are being considered.
Examples :
Input : 11
Output : 13
Explanation: (11)10 = (1011)2.
After reversing the bits we get:
(1101)2 = (13)10.Input : 10
Output : 5
Explanation : (10)10 = (1010)2.
After reversing the bits we get:
(0101)2 = (101)2
= (5)10.
In this approach, one by one bit in the binary representation of n is being obtained with the help of bitwise right shift operation and they are being accumulated in rev with the help of bitwise left shift operation.
Algorithm:
C++
// C++ implementation to reverse bits of a number#include <bits/stdc++.h>using namespace std;// function to reverse bits of a numberunsigned int reverseBits(unsigned int n){ unsigned int rev = 0; // traversing bits of 'n' from the right while (n > 0) { // bitwise left shift // 'rev' by 1 rev <<= 1; // if current bit is '1' if (n & 1 == 1) rev ^= 1; // bitwise right shift // 'n' by 1 n >>= 1; } // required number return rev;}// Driver program to test aboveint main(){ unsigned int n = 11; cout << reverseBits(n); return 0;} |
C
// C implementation to reverse bits of a number#include <stdio.h>// function to reverse bits of a numberunsigned int reverseBits(unsigned int n){ unsigned int rev = 0; // traversing bits of 'n' from the right while (n > 0) { // bitwise left shift 'rev' by 1 rev <<= 1; // if current bit is '1' if (n & 1 == 1) rev ^= 1; // bitwise right shift 'n' by 1 n >>= 1; } // required number return rev;}// Driver program to test aboveint main(){ unsigned int n = 11; printf("%u", reverseBits(n)); return 0;}// This code is contributed by Sania Kumari Gupta// (kriSania804) |
Java
import java.io.*;// Java implementation to// reverse bits of a numberclass GFG { // function to reverse bits of a number public static int reverseBits(int n) { int rev = 0; // traversing bits of 'n' // from the right while (n > 0) { // bitwise left shift // 'rev' by 1 rev <<= 1; // if current bit is '1' if ((int)(n & 1) == 1) rev ^= 1; // bitwise right shift //'n' by 1 n >>= 1; } // required number return rev; } // Driver code public static void main(String[] args) { int n = 11; System.out.println(reverseBits(n)); }}// This code is contributed// by prerna saini. |
Python3
# Python 3 implementation to# reverse bits of a number# function to reverse# bits of a numberdef reverseBits(n): rev = 0 # traversing bits of 'n' from the right while (n > 0): # bitwise left shift 'rev' by 1 rev = rev << 1 # if current bit is '1' if (n & 1 == 1): rev = rev ^ 1 # bitwise right shift 'n' by 1 n = n >> 1 # required number return rev# Driver coden = 11print(reverseBits(n))# This code is contributed# by Nikita Tiwari. |
C#
// C# implementation to// reverse bits of a numberusing System;class GFG { // function to reverse bits of a number public static int reverseBits(int n) { int rev = 0; // traversing bits of 'n' // from the right while (n > 0) { // bitwise left shift // 'rev' by 1 rev <<= 1; // if current bit is '1' if ((int)(n & 1) == 1) rev ^= 1; // bitwise right shift //'n' by 1 n >>= 1; } // required number return rev; } // Driver code public static void Main() { int n = 11; Console.WriteLine(reverseBits(n)); }}// This code is contributed// by vt_m. |
PHP
<?php// PHP implementation to reverse // bits of a number// function to reverse // bits of a numberfunction reverseBits($n){ $rev = 0; // traversing bits of 'n' // from the right while ($n > 0) { // bitwise left shift // 'rev' by 1 $rev <<= 1; // if current bit is '1' if ($n & 1 == 1) $rev ^= 1; // bitwise right shift // 'n' by 1 $n >>= 1; } // required number return $rev;}// Driver code$n = 11;echo reverseBits($n);// This code is contributed by mits ?> |
Javascript
<script>// JavaScript program to // reverse bits of a number // function to reverse bits of a number function reverseBits(n) { let rev = 0; // traversing bits of 'n' // from the right while (n > 0) { // bitwise left shift // 'rev' by 1 rev <<= 1; // if current bit is '1' if ((n & 1) == 1) rev ^= 1; // bitwise right shift //'n' by 1 n >>= 1; } // required number return rev; }// Driver code let n = 11; document.write(reverseBits(n));</script> |
13
Time Complexity: O(num), where num is the number of bits in the binary representation of n.
Space Complexity: O(1)
How about considering even the leading zero bits for the reversal?
Another twist to this problem is to reverse all 4 bytes of an integer value. For e.g. if the number is 11 (0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1) then its reverse will be -805306368 (1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0).
C++
#include <iostream>#include <vector>using namespace std;// helper method to show actual bitsvoid showBits(int n) { vector<int> bits; for(int i = 0; i < sizeof(int) * 8; i++) { if((n & 1) > 0) bits.push_back(1); else bits.push_back(0); n = n >> 1; } for(int i = bits.size()-1; i >= 0; i--) { cout << bits[i] << ","; }}int reverseBits(int n) { int newN = 0; for(int i = 0; i < sizeof(int) * 8; i++) { newN = newN << 1; if((n & 1) > 0) { newN = newN ^ 1; } n = n >> 1; } return newN;}int main() { int num = 11; // just to show full bit sequence showBits(num); int ret = reverseBits(num); cout << "\nreverse of number " << num << " is=" << ret << endl; showBits(ret); cout << "\n"; num = -10; // just to show full bit sequence showBits(num); ret = reverseBits(num); cout << "\nreverse of number " << num << " is=" << ret << endl; showBits(ret); return 0;}// This code is contributed by Shivhack999 |
Java
/*package whatever //do not write package name here */import java.io.*;import java.util.List;import java.util.ArrayList;class ReverseBits190 { public static void main (String[] args) { int num = 11; showBits(num); // just to show full bit sequence int ret = reverseBits(num); System.out.println("\nreverse of number " + num + " is=" + ret); showBits(ret); System.out.println("\n"); num = -10; showBits(num); // just to show full bit sequence ret = reverseBits(num); System.out.println("\nreverse of number " + num + " is=" + ret); showBits(ret); } static int reverseBits(int n) { int newN = 0; for(int i = 0; i < Integer.SIZE; i++) { newN = newN << 1; if((n & 1) > 0) { newN = newN ^ 1; } n = n >> 1; } return newN; } // helper method to show actual bits static void showBits(int n) { List<Integer> l = new ArrayList<>(); for(int i = 0; i< Integer.SIZE; i++) { if((n & 1) > 0) l.add(1); else l.add(0); n = n >> 1; } for(int i = l.size()-1; i >= 0; i--) { System.out.print(l.get(i) + ","); } }} |
C#
using System;using System.Collections.Generic;public class MainClass { public static void Main() { int num = 11; // just to show full bit sequence ShowBits(num); int ret = ReverseBits(num); Console.WriteLine("\nreverse of number " + num + " is=" + ret); ShowBits(ret); Console.WriteLine("\n"); num = -10; // just to show full bit sequence ShowBits(num); ret = ReverseBits(num); Console.WriteLine("\nreverse of number " + num + " is=" + ret); ShowBits(ret); } // helper method to show actual bits public static void ShowBits(int n) { List<int> bits = new List<int>(); for(int i = 0; i < sizeof(int) * 8; i++) { if((n & 1) > 0) bits.Add(1); else bits.Add(0); n = n >> 1; } for(int i = bits.Count-1; i >= 0; i--) { Console.Write(bits[i] + ","); } } public static int ReverseBits(int n) { int newN = 0; for(int i = 0; i < sizeof(int) * 8; i++) { newN = newN << 1; if((n & 1) > 0) { newN = newN ^ 1; } n = n >> 1; } return newN; }}// This code is contributed by shivregkec |
Python3
def show_bits(n): bits = [] for i in range(32): if n & 1: bits.append(1) else: bits.append(0) n >>= 1 bits.reverse() print(bits)def reverse_bits(n): new_n = 0 for i in range(32): new_n <<= 1 if n & 1: new_n ^= 1 n >>= 1 return new_nnum = 11# just to show full bit sequenceshow_bits(num)ret = reverse_bits(num)print("reverse of number", num, "is=", ret)show_bits(ret)print()num = -10# just to show full bit sequenceshow_bits(num)ret = reverse_bits(num)print("reverse of number", num, "is=", ret)show_bits(ret) |
Javascript
// helper function to show actual bitsfunction showBits(n) {let bits = [];for (let i = 0; i < 32; i++) {if (n & 1) {bits.push(1);} else {bits.push(0);}n >>= 1;}bits.reverse();console.log(bits);}function reverseBits(n) {let newN = 0;for (let i = 0; i < 32; i++) {newN <<= 1;if (n & 1) {newN ^= 1;}n >>= 1;}return newN;}let num = 11;// just to show full bit sequenceshowBits(num);let ret = reverseBits(num);console.log('reverse of number ${num} is= ${ret}');showBits(ret);console.log();num = -10;// just to show full bit sequenceshowBits(num);ret = reverseBits(num);console.log('reverse of number ${num} is= ${ret}');showBits(ret); |
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,1, reverse of number 11 is=-805306368 1,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,0, reverse of number -10 is=1879048191 0,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
Contributed by Nikhil.
*************************************************************************************************************************
Another way using c++
Note: All 32bits are reversed, All leading 0’s are being considered using c++.
Examples :
Input : 4
Output : 536870912
Explanation: (4)10 = (00000000000000000000000000000100)2
After reversing the binary form we get:
(00100000000000000000000000000000)2 = (536870912)10Input : 7
Output : 3758096384
Explanation:
(7)10 = (00000000000000000000000000000111)2
After reversing the binary form we get:
(11100000000000000000000000000000)2 = (3758096384)10
Here first we will convert the number into binary form in a reverse way and every bit of binary number gets converted into decimal form and added to the previous one.
For input (5)10 binary form is (00000000000000000000000000000101)2
After reversing (10100000000000000000000000000000)2
and its decimal form is (2684354560)10
The first bit of reversed binary form is 1 if we count from left to right, which means this bit is set, to find this bit we use the logic to convert a decimal numbers into binary.
Let k be a variable that stores this bit and “i = 0” be the variable of loop and increased by 1 in every iteration to find bits, and “j” be a variable that is used to convert it again in decimal whose initial value is 31 and decreased by 1 in every iteration
k = (n>>i)&1 where i = 0 and j =31
k = (5>>0) & 1 = 1 since this bit is set then it takes part in converting in the decimal form again, and it will be dn = dn + 2^31 where dn is new decimal form which is initially 0 and dn is added with all set bits
The second bit is 0.
k = (n>>i)&1 where i = 1 and j =30
k = (5>>1) & 1 = 0 since this bit is not set then it does not takes part in converting into decimal form
The third bit is 1
k = (n>>i)&1 where i = 2 and j =29
k = (5>>2)&1 = 1 since this bit is set then it takes part in converting in the decimal form again, and it will be new decimal form then dn = dn + 2^29
The fourth bit is 0
k = (n>>i)&1 where i = 3 and j =28
k = (5>>3)&1 = 0 since this bit is not set then it does not takes part in converting in decimal form.
and so on… for every set bit dn is updated until it founds all 32 bits and will be the required answer.
C++
#include <bits/stdc++.h>using namespace std;// function to reverse and convert in decimallong long reversedBitsNum(long long n){ long long dn = 0; // variable for new decimal number int j = 30; // initial value of j // loop to find the reversede binary bit for (int i = 0; i < 32; ++i) { int k = (n >> i) & 1; // k will be the required bit if (k) { // if bit is set then only convert in // decimal if (j == -1) { // since if j = -1 then left // shift operator will not work dn = abs(dn) + pow(2, 0); } else { dn = abs(dn) + (2 << j); // here left shift operator // calculates 2 to power j // for making code efficient } } j--; // j is decreased in each iteration } return abs(dn);}int main(){ long long n = 4; cout<<"Decimal number after reversing all 32 bits is : "<<reversedBitsNum(n); return 0;} |
Java
public class Main { // function to reverse and convert in decimal public static long reversedBitsNum(long n) { long dn = 0; // variable for new decimal number int j = 30; // initial value of j // loop to find the reversed binary bit for (int i = 0; i < 32; i++) { int k = (int)((n >> i) & 1); // k will be the required bit if (k != 0) { // if bit is set then only convert in decimal if (j == -1) { // since if j = -1 then left shift operator will not work dn = Math.abs(dn) + (long)Math.pow(2, 0); } else { dn = Math.abs(dn) + (2 << j); // here left shift operator calculates 2 to power j for making code efficient } } j--; // j is decreased in each iteration } return Math.abs(dn); } public static void main(String[] args) { long n = 4; System.out.println("Decimal number after reversing all 32 bits is : " + reversedBitsNum(n)); }}// This code is contributed by shivhack999 |
Python3
# python code implementation for the above approach# function to reverse and convert in decimaldef reversedBitsNum(n): dn = 0 # variable for new decimal number j = 30 # initial value of j # loop to find the reversed binary bit for i in range(32): k = (n >> i) & 1 # k will be the required bit if k != 0: # if bit is set then only convert in # decimal if j == -1: # since if j = -1 then left # shift operator will not work dn = abs(dn) + pow(2, 0) else: dn = abs(dn) + (2 << j) # here left shift operator # calculates 2 to power j # for making code efficient j = j - 1 # j is decreased in each iteration return abs(dn)n = 4print("Decimal number after reversing all 32 bits is : ", reversedBitsNum(n))# This code is contributed by Nidhi goel. |
C#
using System;public class GFG{ // function to reverse and convert in decimal public static long reversedBitsNum(long n) { long dn = 0; // variable for new decimal number int j = 30; // initial value of j // loop to find the reversed binary bit for (int i = 0; i < 32; ++i) { int k = (int)((n >> i) & 1); // k will be the required bit if (k != 0) { // if bit is set then only convert // in decimal if (j == -1) { // since if j = -1 then left // shift operator will not work dn = Math.Abs(dn) + (long)Math.Pow(2, 0); } else { dn = Math.Abs(dn) + (2 << j); // here left shift // operator calculates 2 // to power j for making // code efficient } } j--; // j is decreased in each iteration } return Math.Abs(dn); } static public void Main() { long n = 4; Console.WriteLine( "Decimal number after reversing all 32 bits is : " + reversedBitsNum(n)); }}// This code is contributed by akashish__ |
Javascript
// function to reverse and convert in decimalfunction reversedBitsNum(n) { let dn = 0; // variable for new decimal number let j = 30; // initial value of j // loop to find the reversede binary bit for (let i = 0; i < 32; ++i) { let k = (n >> i) & 1; // k will be the required bit if (k) { // if bit is set then only convert in // decimal if (j == -1) { // since if j = -1 then left // shift operator will not work dn = Math.abs(dn) + Math.pow(2, 0); } else { dn = Math.abs(dn) + (2 << j); // here left shift operator // calculates 2 to power j // for making code efficient } } j--; // j is decreased in each iteration } return Math.abs(dn);}let n = 4;console.log( "Decimal number after reversing all 32 bits is : " + reversedBitsNum(n));// This code is contributed by akashish__ |
Decimal number after reversing all 32 bits is : 536870912
In the above program, we use abs(dn) everywhere because when it calculates 2^31 since there can be only 32 bits it gives the negative value of the same magnitude, to correct this we return the absolute value of dn.
Contributed by Shivam Verma(coder_shiv)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
