Reverse all bits in an int and return the int

Question

What integer should be returned when we reverse all bits of integer 1? How do we do that with Java code?

No java built in functions should be used. Shouldn't use String reverse, converting to string etc. Only bitwise operations allowed.

import java.util.*;
import java.lang.*;
import java.io.*;

class BitReverseInt
{
    public static void main (String[] args) throws java.lang.Exception{
        System.out.println(reverser(1));
    }

    public static int reverser(int given){
          int input = given;
          int temp = 0;
          int output = 0;
          while(input > 0){
            output = output << 1;
            temp = input & 1;
            input = input >> 1;
            output = output | temp;
          }

          return output;
    }
}

Answer 1

You can use a do while loop like this:

public static int reverse(int number){
        int reverse = 0;
        int remainder = 0;
        do{
            remainder = number%10;
            reverse = reverse*10 + remainder;
            number = number/10;

        }while(number > 0);

        return reverse;
    }

And for bitwise operation: here it goes:

// value=your integer, numBitsInt=how much bit you will use to reverse 
public static int reverseIntBitwise(int value, int numBitsInt) {

    int i = 0, rev = 0, bit;

    while (i++ < numBitsInt) {

        bit = value & 1;

        value = value >> 1;

        rev = rev ^ bit;

        if (i < numBitsInt)
            rev = rev << 1;
    }
    return rev;
}

Answer 2

Bit reversal can be done by interchanging adjacent single bits, then interchanging adjacent 2-bit fields, then 4-bits, and so on as shown below. These five assignment statements can be executed in any order.

/********************************************************
 * These are the bit masks used in the bit reversal process

   0x55555555 = 01010101010101010101010101010101
   0xAAAAAAAA = 10101010101010101010101010101010
   0x33333333 = 00110011001100110011001100110011
   0xCCCCCCCC = 11001100110011001100110011001100
   0x0F0F0F0F = 00001111000011110000111100001111
   0xF0F0F0F0 = 11110000111100001111000011110000
   0x00FF00FF = 00000000111111110000000011111111
   0xFF00FF00 = 11111111000000001111111100000000
   0x0000FFFF = 00000000000000001111111111111111
   0xFFFF0000 = 11111111111111110000000000000000

 */

    uint x = 23885963;    // 00000001011011000111100010001011

    x = (x & 0x55555555) <<  1 | (x & 0xAAAAAAAA) >>  1; 
    x = (x & 0x33333333) <<  2 | (x & 0xCCCCCCCC) >>  2; 
    x = (x & 0x0F0F0F0F) <<  4 | (x & 0xF0F0F0F0) >>  4; 
    x = (x & 0x00FF00FF) <<  8 | (x & 0xFF00FF00) >>  8; 
    x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;

    // result x == 3508418176   11010001000111100011011010000000

By looking at each intermediary result you can see what is happening.

Hopefully this will give you what you need to sort it out in your head. John Doe's answer consolidates steps 4 and 5 in to a single expression. This will work on most machines.

Answer 3

Here is the actual implementation of Integer.reverse(int).

    public static int reverse(int i) {
    // HD, Figure 7-1
    i = (i & 0x55555555) << 1 | (i >>> 1) & 0x55555555;
    i = (i & 0x33333333) << 2 | (i >>> 2) & 0x33333333;
    i = (i & 0x0f0f0f0f) << 4 | (i >>> 4) & 0x0f0f0f0f;
    i = (i << 24) | ((i & 0xff00) << 8) |
        ((i >>> 8) & 0xff00) | (i >>> 24);
    return i;
}

Answer 4

Well there are multiple ways to reverse the bits of the given number in Java.

First, Java language has inbuild bitwise complement operator(~). So (~number) reverses the bits of number.

Second, one can use the Integer.reverse(number)

Third, if this is a part of test or you just want to play with bits, you can refer the code below.

/*
The logic uses moving bitmask from right to left:

 1. Get the bit of given number, by binary and(&) with bitmask
 2. XOR(^) with the bitmask, so here we reverse the bit.
 3. OR(|) this reversed bit with the result(result has all Zero initially)

This logic is repeated for each 32 bits by moving the mask from right to left, 
one bit at a time using (<<) left shift operator on bitmask.
*/
public class ReverseBits {

    public static int reverseBits(int input) {
        print("Input", input);
        int bitmask = 1;
        int result = 0;
        do {
            //print("Bitmask", bitmask);
            result = result | (bitmask ^ (input & bitmask)) ;
            //print("Result", result);
            bitmask = bitmask << 1;
        } while (bitmask != 0);
        print("Reverse", result);
        return result;
    }

    public static void print(String label, int input) {
        System.out.println(label +"\t:"+Integer.toBinaryString(input));
    }

    public static void main(String[] args) {
        reverseBits(Integer.MIN_VALUE);
        reverseBits(Integer.MAX_VALUE);
        reverseBits(reverseBits(170));
    }
}

Output:

Input   :10000000000000000000000000000000
Reverse :1111111111111111111111111111111
Input   :1111111111111111111111111111111
Reverse :10000000000000000000000000000000
Input   :10101010
Reverse :11111111111111111111111101010101
Input   :11111111111111111111111101010101
Reverse :10101010

Answer 5

return Integer.reverse(given);

Integer.reverse Reference