Bitwise and bit-shift operations

As you probably know, in most cases, computer numbers are represented in binary format. In this format, each digit of a number can be represented as either 0 or 1. For example, the decimal value 15 is 1111 in binary format. We’ve already learned how to convert integer numbers to binary and perform some arithmetic operations with binary numbers. Now let’s learn how else you can work with binary numbers!

Java provides several operators for manipulating individual bits of integer numbers. They perform fast and simple operations and are directly supported by the processor. They are particularly important in lower-level programming such as device drivers, low-level graphics, network communication, encryption, and compression. In this topic, we are going to focus on bitwise and bitshift operators, which, used together with zero-testing, can efficiently perform various arithmetic and logical operations.

Bitwise operators

There are four bitwise operators, each of which goes through all bits of an operand (the number on which the operation is done) one by one (bitwise) and produces a new number as a result.

• ~ (bitwise NOT, inversion, complement) is a unary operator that inverses the bits of the number in binary format, transforming every 0 into 1 and every 1 into 0. It also changes the sign bit of the value.
• | (bitwise OR) is a binary operator that returns 1 if at least one operand digit is 1, otherwise, it returns 0.
• & (bitwise AND) is a binary operator that returns 1 if both operand digits are 1, otherwise, the result is 0.
• ^ (bitwise XOR) is a binary operator that returns 1 if exactly one operand is 1, otherwise, it returns 0.

The listed operators can be applied to integer and boolean operands. If both operands are integer, bitwise operations will be performed. If both operands are booleans, they will undergo corresponding logical operations (except ~).

To see how these operators work, let’s assume we have two integer numbers: 15 and 10. The first number’s binary representation is 1111, the second one is 1010.

int first = 15;  // binary format 1111
int second = 10; // binary format 1010

int bitwiseAnd = first & second; // 1111 & 1010 = 1010, the result is 10
int bitwiseOr = first | second;  // 1111 | 1010 = 1111, the result is 15
int bitwiseXor = first ^ second; // 1111 ^ 1010 = 0101, the result is 5 

Now that you’ve got the principle, we will demonstrate how to apply them in practice in next topics, as well as in our projects.

Bit-shift operators

In addition to bitwise operators, Java also provides bit-shift operators that can be used to move bits of an integer number from one position to another.

There are three bit-shift operators:

• << is a signed bit-shift operator that shifts a bit pattern to the left by the distance specified in the right operand. It fills the empty position with zeros.
• >> is a signed bit-shift operator that shifts a bit pattern to the right by the distance specified in the right operand. It fills the empty position with the values of the sign bit.
• >>> is an unsigned bit-shift operator that shifts a bit pattern to the right by the distance specified in the right operand. It is almost the same as >>, but the shifted values are filled up with zeros. The result of the >>> operator is always positive.

The following example illustrates how to perform fast multiplication and division by two using bit-shift operators.

int val = 25;   // binary: 0001 1001, decimal: 25

val = val << 1; // binary: 0011 0010, decimal: 50
val = val << 2; // binary: 1100 1000, decimal: 200

int anotherVal = 14;   // binary: 1110, decimal: 14
anotherVal = anotherVal >> 1; // binary: 0111, decimal: 7

As you can see, the result of the left-shift operator is equivalent to the product of multiplication by two, and the result of the right-shift operator is equivalent to that of a division by two. To summarize, when we use signed bit-shift operators we perform the multiplication or division of the left operand by two depending on the right operand.

int newVal = 25;

newVal = newVal << 1; // 25 * 2^1 = 50
newVal = newVal << 3; // 50 * 2^3 = 400
newVal = newVal >> 2; // 400 / 2^2 = 100

Another example is the calculation of the midpoint of an integer positive interval.

int left = 10;
int right = 20;

int mid = left + right >> 1; // this is 15!

Of course, this magic produces the same result as (left + right) / 2, but the bit-shift version is often considered a faster way to obtain it. Some algorithms in the Java standard library use this approach.

Unlike the signed right shift (>>), the unsigned >>> does not consider sign bits: instead, it just shifts all the bits to the right and pads the result with zeros from the left. It means that for negative numbers the result is always positive. For positive numbers, signed and unsigned right shifts have the same result.

Precedence of bitwise and bit-shift operations

Similar to arithmetic operators, bitwise and bit-shift operators have so-called precedence that determines the order of performing and grouping operations in the expression. Operations with higher precedence are performed before those with lower precedence. In the table below you will find all the operators we’ve discussed so far ordered by their precedence in descending order.

When the operators have equal precedence, another rule is applied. It is called associativity and it determines whether the evaluation should be performed from left to right or vice versa.

All the operators we have considered are evaluated from left to right, the way you are used to.

This means that for the two expressions first | second & third and(first | second) & third the operations will be executed in a different order and hence results may vary. If you go back to the left + right >> 1 example in the previous section, you can see that there we don’t have to use brackets like in the (left + right) / 2 expression because addition has higher precedence than all bit-shift operations. Remember these priorities when you combine arithmetic operators with bit operations.

Conclusion

In this topic, we’ve learned how to perform some operations on the bits of integer numbers and how they correspond to some arithmetic operations. Bitwise operators process bits one by one according to the logical operations, while bit-shift ones allow us to move the whole bit pattern left or right. The theory may seem a bit complicated, however, it is essential to understand the basics to apply them in practice, as we will learn further on.