1. Overview
Sometimes we need to test whether a binary digit in a number is set or not. This may be because we’re using numbers as a set of flags, where each digit represents a particular boolean value.
In this tutorial, we’ll explore different ways to get a bit at a specific position from integral values, such as byte, short, char, int, and long.
2. Testing a Specific Bit
One of the most common situations is that we want to test a specific bit of an integral value with a bitmask.
For example, let’s check whether the third bit is set in a byte value:
byte val1 = 0b0110_0100;
byte mask = 0b0000_0100;
boolean isSet1 = (val1 & mask) > 0;
assertTrue(isSet1);
Here the binary number 01100100 is tested to see if the third bit – 00000100 is set by using bitwise AND. The result is greater than zero, so it is. We can also test if it’s not set:
byte val2 = 0b0110_0010;
boolean isSet2 = (val2 & mask) > 0;
assertFalse(isSet2);
This example is based on the byte numeric type, and we can easily extend it to short, char, int, and long values.
In this solution, we’ve hard-coded the bitmask. What if we wanted to generalize the solution to check any bit in our number?
3. Using Shift Operator
Before starting, let’s first define the index range of the bit positions in a 32-bit int. The leftmost bit has an index of 31, and the rightmost bit has an index of 0. This is because our numbers run from the most significant to the least significant digits. For example, if we used 64-bit long numbers, the leftmost bit would be 63.
3.1. Left Shift a Mask
We can generate a bitmask by taking the value 1 and moving it to the correct position by using the left shift operator:
int val = 0b0110_0100;
int pos = 2;
int mask = 1 << pos;
boolean isSet = (val & mask) > 0;
assertTrue(isSet);
Here we have set pos to 2, though it could be any valid bit position in our number. Then, we use the left shift operator (<<) to generate our bitmask. Finally, we do a bitwise AND (&) operation between the val and the mask.
If the result is greater than zero, it means the target bit is set.
3.2. Left Shift the Value
In addition, there’s another way of solving this problem.
Instead of constructing a bitmask, we can use the left shift operator on the value we’re testing. Rather than filter the value with a bitmask, we can shift its contents so that the interesting bit is in the leftmost position.
Then all we need to do is check if the leftmost bit is set. As a signed integer is represented as two’s complement, we can test whether the leading digit is a one by testing if the resulting bit shifted number is negative.
int val = 0b0110_0100;
int pos = 2;
boolean isSet = ((val << (31 - pos)) < 0);
assertTrue(isSet);
In the above, the pos is 2, and the leftmost position is 31, so we use 31 to subtract pos, which equals 29. Then, we left-shift the original value 29-bit positions and get a new value. In this new value, the interesting bit is at the leftmost position. Finally, we check whether the new value is less than zero or not.
3.3. Right Shift the Value
Similarly, we can use the right shift operator to test a bit of an integral value. After moving the target bit of an integral value to the rightmost position and using a bitmask of 1, we can check if the result equals one:
int val = 0b0110_0100;
int pos = 2;
boolean isSet = ((val >> pos) & 1) == 1;
assertTrue(isSet);
4. Optimising the Bitwise Solution
In cases where we might be performing these calculations a lot, we may wish to optimize our solution to use the least number of CPU instructions.
Let’s look at a rewrite of the left shift solution, which might help us achieve this. It’s based on the assumption that bitwise operations are usually faster than arithmetic operations:
boolean isSet = ((val << (~pos & 31)) < 0);
We should note that the core idea has not changed. Just the writing of the code is subtlely different: we use (~pos & 31) to substitute the previous (31-pos) expression.
Why do these two expressions have the same effects? We can deduct this process:
(31 - pos) = (31 - pos) & 31
= (31 + (-pos)) & 31
= (31 & 31) + ((-pos) & 31)
= (31 & 31) + ((~pos + 1) & 31)
= (31 & 31) + (~pos & 31) + (1 & 31)
= ((31 + 1) & 31) + (~pos & 31)
= (32 & 31) + (~pos & 31)
= 0 + (~pos & 31)
= (~pos & 31)
At the beginning of this section, we mentioned the leftmost position is 31 and the rightmost position is 0, so (31 – pos) should be a positive number or zero. If we do a bitwise AND (&) operation between (31 – pos) and 31, the result remains the same. Then, we do it step by step. Finally, we get the (~pos & 31) expression.
In this process, one more thing needs explanation: how does the (-pos) transform into (~pos + 1)? To get the two’s complement negative notation of an integer, we can do a bitwise COMPLEMENT (~) operation, then add one to the result.
One step further, we can make the code a little more concise:
boolean isSet = ((val << ~pos) < 0);
In the above, we have left out bitwise AND (&) and 31. That’s because the JVM will do the job for us. An int value has 32-bit, and the JVM ensures that its valid shift range should be between 0 and 31. Similarly, a long value has 64-bit, and the JVM also makes sure its valid shift range should be between 0 and 63.
5. Using BigInteger
While the above binary math is the most computationally efficient for the built-in numeric types, we may need to check bits on numbers with more than 64 bits or may wish to have easier-to-read code.
The BigInteger class can solve both these problems. It supports very large numbers with huge numbers of bits and provides a testBit method too:
int val = 0b0110_0100;
int pos = 2;
boolean isSet = BigInteger.valueOf(val).testBit(pos);
assertTrue(isSet);
6. Conclusion
In this tutorial, we took a look at some common approaches to getting a bit at a certain position from integral values.
As usual, the source code for this tutorial can be found over on GitHub.