September 02, 2017
Java enables you to manipulate integers on a bit level, that means operating on specific bits, which represent an integer number. In some cases, it can be really handy.
You are no doubt familiar with arithmetic operators such as + - * / or %. You also know for sure logical operators such as & or |. Turns out there is another, a slightly less known set of operators, which manipulate numbers on bit level. Internally, every number is stored in a binary format - that is 0 and 1.
These operators can be performed on integer types and its variants - that is
This fancy name basically means bit negation. It takes every single bit of the number and flips its value. That is - 0 becomes 1 and vice versa. Unary means that it needs just one operand. The operator is ~ and it is just placed before the number:
For example, let's use ~42:
Unlike bitwise complement operator, other bitwise operators need two operands.
A & B means that all the bits of both numbers are compared one by one and the resulting number is calculated based on values of the bits from numbers A and B. Bitwise AND is similar to logical AND in a sense that it results in 1 only when the two compared bits are both equal to 1. Otherwise, it results in 0.
For example: 0110 & 1100 would result in 0100 as the second bit from the left is the only one where both operands contain 1.
Bitwise OR results in 1 when at least one of the compared bits is 1 (or both), otherwise it results in 0.
Exclusive OR (XOR) results in 1 only if both the compared bits have a different value, otherwise, it results in 0.
Below is a table showing a comparison of results of all the bitwise operators mentioned above based on different values of the compared bits (A and B).
|A||B||A & B||A | B||A ^ B|
Signed Left Shift takes two operands. It takes the bit pattern of the first operand and shifts it to the left by the number of places given by the second operand. For example 5 << 3: What happens in this case - Every bit in the binary representation of the integer 5 is shifted by 3 positions to the left. All the places on the left are padded by zeros. That is:
00000000 00000000 00000000 00000101
00000000 00000000 00000000 00101000
You can note that the integer result of 5 << 3 is 40. That shows that shifting a number by one is equivalent to multiplying it by 2, or more generally left shifting a number by n positions is equivalent to multiplication by 2^n^.
There are several additional interesting aspects to this:
There are actually two types of right shift. Signed and unsigned. The difference is how they treat negative numbers. To understand the difference, it is necessary to know how negative numbers are represented in Java. Binary representation on its own does not provide information whether the number is negative. There needs to be a special rule to define how to represent negative numbers in binary. There are several approaches to this problem.
One solution is that the leftmost (Most Significant) bit is a sign bit. That means that its value indicates whether the number is positive or negative. This has, however, some disadvantages such as that there are two ways of representing zero.
Java uses another approach, which is called two's complement. Negative numbers are representing by negating (flipping) all the bits and then adding 1. Still, if the leftmost bit is 0, the number is positive. Otherwise, it is negative.
Signed right shift moves all the bits by given number of positions to the right. However, it preserves the sign. Positive numbers remain positive and negative ones remain negative. Similar to left shift, the right shift of n positions is equivalent to division by 2^n^. Or division by 2^n^ -1 in case of odd numbers.
Unlike signed shift, the unsigned one does not take sign bits into consideration, it just shifts all the bits to the right and pads the result with zeros from the left. That means that for negative numbers, the result is always positive. Signed and unsigned right shifts have the same result for positive numbers.
Bit manipulation can be very handy in some cases and is really efficient. Increased performance, however, comes at its cost. The readability suffers a lot at it can be really puzzling for somebody who is not familiar with the bit manipulation concept. If the scenario you are using is not performance-critical, you may want to consider, whether the tradeoff of performance for readability is really worth it and maybe rewrite your solution in a more readable way. Don't use bit manipulation everywhere possible just because you learned a cool new concept.