Confused About Bit Shifting (Counting Bits in Byte)

Question

I'm trying to count the number of set bits in a byte but I appear to be running into some issues I can't find answers to.

My code currently looks like

   public static int numBits(byte input){
       int count = 0;
       while (input != 0){
           if ((input & 1)==1){
               count++;
           }
           input >>= 1;
       }
       return count;
   }

It appeared to work fine until I tried x = -1.

This ended up creating an infinite loop as value 1 bits were being inserted. So I stumbled upon

Java: right shift on negative number

which to my interpretation meant I should use input >>>= 1; but this still led to an infinite loop.

So I tried to figure out what was going on by trying

byte x = -1;
System.out.println(x >>> 1);
System.out.println(x >> 1);

which lead to

2147483647
-1

leaving me more confused. Where did the number 2147483647 come from and where might I be making a logic mistake?

You should go read about [Two's complement](http://en.wikipedia.org/wiki/Two's_complement) representation of signed numbers in binary. If you understand how negative numbers are represented, and the difference between arithmetic/logical shifts, all of that will make perfect sense. — DaoWen, Sep 13 '13 at 03:16
Here's how you do it: http://www.google.com/patents/US6516330 — Hot Licks, Sep 13 '13 at 04:33

Mark Elliot · Accepted Answer · 2013-09-13T03:30:41.547

The >>> operator means shift to the right, but do not sign-extend.

Your trial is pretty close, but you're not actually modifying x, so you can do:

int x = -1;
x = x >>> 1;
System.out.println(x);
x = x >> 1; // highest bit = 0 now
System.out.println(x);

Which will yield

2147483647
1073741823

Notice that I'm using int rather than byte here, since the result of bit shifts coerces the input to at least be integer sized.

Interestingly, when you run:

byte input = -1;
input = (byte) (input >>> 1);

The result is still -1. This is because of the type coercion happening with this operator mentioned above. To prevent this from affecting you, you can mask the bits of input to make sure you only take the first 8:

byte input = -1;
input = (byte) ((input & 0xFF) >>> 1);

Putting this together, if you were to run:

byte input = -1;
input = (byte) ((input & 0xFF) >>> 1);
System.out.println(input);
input = (byte) ((input & 0xFF) >> 1);
System.out.println(input);

You get the expected results:

127
63

score 3 · Answer 2 · answered Sep 13 '13 at 03:23

This is all being caused by the way signed integers are stored as binary values. The way the highest bit of the number determines the sign (sort of—zero makes things weird), and the sign was being preserved with the arithmetic shift. Your print statements are giving weird results because the results are being promoted to int values instead of bytes.

If you want a really simple fix for this, you can just use an int to store your value, but make sure to mask off everything but the lowest-order byte:

public static int numBits(byte inByte){
   int count = 0;
   int input = inByte & 0xFF;
   while (input != 0){
       if ((input & 1)==1){
           count++;
       }
       input >>= 1;
   }
   return count;
}

Like I said in my comment above, you should really read about Two's complement representation of signed numbers in binary. If you understand how negative numbers are represented, and the difference between arithmetic/logical shifts, all of that will make perfect sense.

score 1 · Answer 3 · answered Sep 13 '13 at 07:32

You might find how the JVM actually does it is interesting. Note: there is only 8 bits so you don't really need a loop.

public static int bitCount(int i) {
    // HD, Figure 5-2
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

NOTE: On the x86/x64, the JVM replaces this with an intrinsic. i.e. it uses a single machine code instruction. If you copy this method and compare it will calling the original it is 3x slower as the JVM only replaces a hard coded list of methods, so it will replace Integer.bitCOunt, but not a copy.

In short, use the built in method instead of re-inventing it.

Confused About Bit Shifting (Counting Bits in Byte)

3 Answers3