Reverse bits in number

Question

For example, I have the binary number 1011 which is equal to decimal 11. I want the reverse bit's location such that it become 1101, which is decimal 13. Here is code:

import java.util.*;
public class bits {
    public static void main(String[] args) {
        Scanner scnr=new Scanner(System.in);
        System.out.println("enter x:");
        int x=scnr.nextInt();
        int b=0;
        while (x!=0){
            b|=( x &1);
            x>>=1;
            b<<=1;
        }
        System.out.println(b);
    }
}

But when I enter x 11 then it prints 26. What is the mistake?

a full Integer can be reversed with `Integer.reverse(int i)` - but as it looks like you want to reverse integers with less bits, I leave it as a comment. — Andreas Dolk, Jul 02 '10 at 12:57
looks like the solution is already here: http://stackoverflow.com/questions/746171/best-algorithm-for-bit-reversal-from-msb-lsb-to-lsb-msb-in-c You are missing that there needs to be an extra shift needed at end — AndrewB, Jul 02 '10 at 13:06

score 29 · Accepted Answer · answered Jul 02 '10 at 12:55

29

You are shifting b one time too many. Do the shift first (so that the first time, when b == 0, it has no effect):

while (x!=0){
  b<<=1;
  b|=( x &1);
  x>>=1;
}

answered Jul 02 '10 at 12:55

Thomas

174,939
50
355
478

What if we also want to consider the padding? 1011 is actually 00001011 so the reverse must be 10110000 – Femn Dharamshi Nov 07 '21 at 21:59
Then you can use a `for` loop that does a fixed number of iterations. – Thomas Nov 08 '21 at 12:26
You replied to a 11 year old thread! Damn! Also, yeah I did that! Thank you!! I maintained a count and then did b<<=(8-count) – Femn Dharamshi Nov 09 '21 at 03:37
1

Can't resist that red notification counter ;) – Thomas Nov 09 '21 at 10:56

score 16 · Answer 2 · answered Jul 02 '10 at 12:58

16

Slightly offtopic. There's also the option of the built-in bit reversing features of Java.

See http://java.sun.com/javase/6/docs/api/java/lang/Integer.html#reverse(int)

EDIT: This assumes you're using Java 1.5 or newer.

answered Jul 02 '10 at 12:58

Tansir1

1,789
2
15
28

score 4 · Answer 3 · edited Feb 08 '13 at 08:01

4

Use >>>= instead of >>=
If you want to change method signature to public static byte reverse(byte in) this will not work on negative values because there is implicit cast to int.

edited Feb 08 '13 at 08:01

Ivan Ferić

4,725
11
37
47

answered Feb 08 '13 at 07:41

user2053554

41
2

score 2 · Answer 4 · edited Apr 01 '14 at 19:39

2

The program do not work for input like 1, 2

int reverseBits(int x)
    {
        int b = 0;
        while (x != 0)
        {
            b <<= 1;
            b |= ( x & 1);
            x >>= 1
        }
        return b;
    }

input 1 output 1, should be 8 right? input 2 output 1, should be 4.

edited Apr 01 '14 at 19:39

Amazing User

3,473
10
36
75

answered Apr 01 '14 at 19:14

Lester

21
2

score 2 · Answer 5 · edited Jul 30 '17 at 14:40

Note for beginners: I use hexadecimal (0-9 and A-F) because one hexadecimal digit maps to 4 binary bits perfectly. Instead of writing 1010, I use A (10 decimal). You can tell Java to use hexadecimal (literals) by starting with 0x as in 0x0A.

As stated before, 1 should output 8 (0001 to 1000). So instead of while(x!=0), the code needs to shift the first bit as far as the length of the bits needed in this example it is 4.

for (int i = 0; i < 4; ++i) { // not while (x!=0){
   b<<=1;
   b|=( x &1);
   x>>=1;
}
Hex convert 0-F: 0=0 1=8 2=4 3=C 4=2 5=A 6=6 7=E 8=1 9=9 A=5 B=D C=3 D=B E=7 F=F

Or full 8 bit example:

public static byte reverse(byte x) {
    byte b = 0;
    for (int i = 0; i < 8; ++i) {
        b<<=1;
        b|=( x &1);
        x>>=1;
      }
    return b;
}
public static void main(String args[]) {
    byte[] nums = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 
            (byte) 0xAA, (byte) 0xFE, (byte) 0xFF };
    for (byte b : nums) {
        System.out.printf("%02X=%02X ", b, reverse(b));
    }
    System.out.println();
}

Output:

00=00 01=80 02=40 03=C0 04=20 05=A0 06=60 07=E0 08=10
09=90 0A=50 0B=D0 0C=30 0D=B0 0E=70 0F=F0 10=08 11=88 AA=55 FE=7F FF=FF

Rahul · Answer 6 · 2015-03-10T13:31:22.470

1

while(x!=0){
    b<<=1;
    b|=(x&1);
    x>>=1;
}

edited Mar 10 '15 at 13:31

answered Mar 08 '15 at 14:42

Rahul

21
4

score 1 · Answer 7 · answered Jul 02 '10 at 12:56

1

b is shifted left once too often. I expect input 1 to result in output 2. Move the Shift two lines up.

answered Jul 02 '10 at 12:56

Peter G.

14,786
7
57
75

score 1 · Answer 8 · answered Jul 02 '10 at 12:58

1

you shifted b once too many. try shifting b to the left before doing the |=:

    while (x!=0){
           b<<=1;
           b|=( x &1);
           x>>=1;

         }
   System.out.println(b);

answered Jul 02 '10 at 12:58

maranas

1,396
1
12
21

score 1 · Answer 9 · answered Jul 02 '10 at 12:59

1

You're left shifting b one time more than required. Add b >>= 1 after your while loop.

answered Jul 02 '10 at 12:59

Praetorian

106,671
19
240
328

score 0 · Answer 10 · answered May 07 '13 at 03:08

0

It is safe to use the unsigned right shift operator (>>>) in the while loop to obviate the danger of running into an infinite loop for -ve numbers.

while (x!=0){
  b<<=1;
  b|=( x &1);
  x>>>=1;
}

answered May 07 '13 at 03:08

Murali Mohan

709
9
4

score 0 · Answer 11 · answered Jul 02 '10 at 13:00

0

The result is twice as much as expected so the last left shift operation (one left shift doubles the value) is too much.

answered Jul 02 '10 at 13:00

Andreas Dolk

113,398
19
180
268

score 0 · Answer 12 · edited May 23 '17 at 12:26

My new java code reverse bits in an integer using java with powerful bit manipulation. It is working with positive, negative and zero values. Hope it helps.

public static int  reverseDigits(int num) throws Exception {
        if (num == 0) {         
            return Integer.MAX_VALUE | Integer.MIN_VALUE;
        }

        int count = Integer.SIZE * 8 - 1;
        int  reversed = num;        
        boolean positive = true;

        if (num < 0) {
            positive = false;
        }

        if (positive) num >>= 1;

        while(num != 0) {

            reversed <<= 1; 
            reversed |= (num & 1);          

            num >>>= 1;
            count--;            
        }

        if (positive) reversed <<= count;
        return reversed;
    }

You can represent bits in integer with my other bit manipulation code in java what print zeroes on the left: https://stackoverflow.com/a/39056535/6738542

Because Integer.toBinaryString() will hide the zeroes on the left.

Metal |,,|

much nicer if you use this line: boolean positive = (num < 0) ? false : true; and forget the next if statement. — Róbert Kovács, Aug 21 '16 at 00:00
"throws Exception" is not important, I used it only for other tests. — Róbert Kovács, Aug 21 '16 at 00:09

score 0 · Answer 13 · answered Mar 15 '22 at 01:53

//    i/p=3 
//    o/p=3221225472
// Clearly observe the 1L while doing the left shift, if ignored it will fail to return the expected output dur to mismatch in bit size.

    public static long reverse(long n) {
        long rev = 0;
        for(int i = 31; i >=0; i--){
            if((n & 1<<i) != 0){
                rev = rev | 1L<<(31-i);
            }
        }
        return rev;
    }

Reverse bits in number

13 Answers13

Linked