Manipulating Bits in Java

I was recently reminded of my struggles with counting numbers with a different base than our usual 10. At times, I felt like my Computer Hardware class in college was speaking a different language to me when I needed to convert numbers (which now included letters) into ones and zeroes. Although counting was relatively simple, it was performing math with these numbers that always seemed out of reach.

All of this came back to me as I attempted to solve this LeetCode problem. It tasked me with counting the number of 1's in the bit representation of a decimal number. At first, this seemed simple. Of course, 0 has zero and 1 has one, 2 has one, and 3 has two. However, I couldn't seem to find a pattern as we got into the larger numbers -- the 1's and 0's started to swim in my vision. How could I programmatically predict that 127 has 7 ones, but 128 has just 1?

After trying to figure it out in several ways with division and modulus I ran out of ideas. Peeking through the comments section gave me the answer I needed, bitwise operators! Although I must admit, at first I was apprehensive to dive into the use of these, I am glad that I did. Before I explain how these helped me solve the problem, I want to do a quick overview of each of these operators.

Bitwise OR (|)

Placing this character in between two variables will take the or of the bit representation of either of these numbers. This means that when we are comparing bits if there is a 1 at that position in either number it will return a 1. For example, if we take 4 and 3 in their decimal forms and convert them into binary we get 100 and 011 respectively. Now if we take  4 | 3  we get 7.

Now we need to be careful because it seems that bitwise or is the same thing as an addition (and it often is) however if two-bit representations share the same bit this will produce a carry that will not be resolved by this operator. For example, 1 | 3 is the same as 01 | 11 which equals 11. 11 is still 3 and we did not get 4.

Bitwise AND (&)

Using it in the same way, as a binary operator, we will find that we get the and of the bit representation of two numbers. In other words, when comparing bits it will only return one for a position if the first number and the second number have a 1 at this position. For example, if we take 4 and 3 again, or 100 and 011, we see that 100 & 011 equals 0.

Now, this doesn't seem as immediately useful or comparable to what we are used to, but it can certainly help us. For instance, if we take any number & 1 we can find out if it is even or not.

7 & 1 = 1

134565 & 1 = 1

8 & 1 = 0

Why? Because every odd number has a 1 in the first position of its bit representation and every even number does not. Keep that in mind, because it is very relevant to our LeetCode problem.

Bitwise XOR (^)

XOR or exclusive or returns 1 at each bit level if and only if exactly one bit is a 1. In other words, it returns a 1 only when the bits are different. Using 3 and 4 once more we see that 011 ^ 100 equals 111, or 7.

In this case, it returned the same as the or operation but this only ever happens when there are no matching bits in the entire string of bits.

Bitwise Complement (~)

Unlike the first three, this is a unary operator, or it only takes one argument. This will return the one's complement of the bit representation of a number. for example, ~ 5 can be written as ~ 0101, which equals 1010, or 10.

Bit-Shift Operators (<<, >>, >>>)

Finally, there are three bit-shift operators in Java.

<< is the signed left shift operator which moves all the bits of a number to the left.

>> is the signed right shift operator which moves all the bits of a number to the right.  

>>> is the unsigned right shift operator which replaces the sign bit with a 0.

The cool thing about shift operators is that they effectively multiple or divide by two since we are adding or taking away a digit to a base 2 number. Importantly, when we right shift an odd number we will get the floor of that number divided by two. For example 111 (7) >> 1 equals 11 (3). This is what happens to your remainder when you are doing integer division.

Okay now that we have reminded ourselves of how to manipulate bits in Java, let's see how this helps us in a problem.

public static int[] countBits(int n) {
        
        int[] bitArray = new int[n+1];
        int temp = 0;
        int currentNumber = 0;
        bitArray[0] = 0;
            
        for(int i = 1; i <= n; i++){
            if((i & 1) == 0){
                bitArray[i] = bitArray[i >> 1];
            }else{
                bitArray[i] = bitArray[i - 1] + 1;
            }
        }
        return bitArray;

For this solution, we are creating an array that includes the number of bits at each index up until the max number that was given to us. This is helpful because we can reference the numbers that we have already solved iteratively. If we did not want to create an array we could also solve this recursively.

Our first condition inside the for loop tests is if the number is even. We use our friend the bitwise and operator to perform this check for us! If that number is even we know that it will have the same number of bits as the number that is half of itself. Why? because they are the same bit numbers, the larger just has a trailing zero. We can find out what number of bits that number had by indexing the array at i >> 1. 4, represented as 100, has the same number of bits as 2, represented as 10.

What about odd numbers? Well, odd numbers will always have one more bit than the number that came before because it is the same bit representation, but the least significant bit was incremented by 1.

Although this was a relatively simple application of these bit operators, it was a good reminder to not forget your bit math. This is what is going on behind the scenes of your computer. The circuits that make all computing possible use these very same logic gates.