Simple arithmetics with bitwise operators in Java

Bitwise operations is one of the fundamental concepts of computer science. While they can be utilised for various scenarios, they are not particularly common in real-world applications. However, understanding bitwise operators can be valuable for interviews and general knowledge purposes.

Like most other languages, Java contains a subset of bitwise operators. The easiest way to get some experience with them is to try and implement basic arithmetic functions on integers using only bitwise operators. In Java, integers are stored in memory as binary values in a fixed number of bits, depending on the integer type. For example, suppose we declare an integer variable num of type byte and assign it the value 5. Java converts the decimal value 5 to its binary representation 101 and stores it in the memory location of size 8 bits reserved for num as 00000101. The actual storage of integers in memory is handled by the computer's processor, which has registers and memory units designed to store and manipulate binary values.

Let’s start by looking into the addition method and how it may be performed on two integers on a bit level. For simplicity, we’ll assume that all of the values are positive, and later in the article, I’ll show how Java deals with negative numbers.

Addition

Before jumping into implementation, let’s discuss how it works on paper. Assume we have two numbers: 5 and 7. Their binary representation would be 101 and 111, respectively.
If we apply school math, adding those two numbers would look like this:

 ------------------------
| carry  | 1 | 1 | 1 | 0 |
 ------------------------
| a      | 0 | 1 | 0 | 1 |
| b      | 0 | 1 | 1 | 1 |
 ------------------------
| result | 1 | 1 | 0 | 0 |
 ------------------------

When we perform this by hand, we are calculating each digit by summing up two operands and carry value. To put it into code, we must split these operations into different steps:

1. Calculate intermediate result ignoring carry value
2. Calculate carry
3. If carry is 0, the intermediate result is the final value, and we should return it
4. If carry is not 0, calculate the result of intermediate result and carry (go to step 1)

If we use this algorithm to calculate 5 + 7, we would get the following results:

carry:  0101 -> 1010 -> 0100 -> 0000
result: 0111 -> 0010 -> 1000 -> 1100

result = 1100 (12)

Let discuss, how do we calculate intermediate result with bitwise operations. To do so, let's create a logical table:

 ----------------
| a | b | result |
 ----------------
| 0 | 0 |   0    |
| 0 | 1 |   1    |
| 1 | 0 |   1    |
| 1 | 1 |   0    |
 ----------------

This is precisely, what bitwise XOR ^ is doing. Thus, the intermediate result of integers a and b would be a ^ b.

Now check how we calculate the carry value.

 ----------------
| a | b | carry  |
 ----------------
| 0 | 0 |   0    |
| 0 | 1 |   0    |
| 1 | 0 |   0    |
| 1 | 1 |   1    |
 ----------------

This is a logical AND. One small caveat here is when we are calculating carry value, we move the result one position to the left. To do this in code, we could use << operator, which does precisely that. The carry result would be (a & b) << 1.

Let’s put all of this into the code:

static int add(int a, int b) {
    int carry = (a & b) << 1;
    int sum = a ^ b;

    while (carry != 0) {
        a = sum;
        b = carry;
        carry = (a & b) << 1;
        sum = a ^ b;
    }
    return sum;
}

A slightly clear rewrite:

static int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}

Substruction

Let’s repeat the process we did for addition method and check if we can come up with similar algorithm for substruction. When substructing two numbers a - b, we’ll assume both are non-negative and a > b. Later we will check if we can drop this condition.

Let’s first review how to do the substruction of numbers 12 and 5:

 ------------------------
| borrow | 1 | 1 | 1 | 0 |
 ------------------------
| a      | 1 | 1 | 0 | 0 |
| b      | 0 | 1 | 0 | 1 |
 ------------------------
| result | 0 | 1 | 1 | 1 |
 ------------------------

The algorithm that we can implement here would look similar to addition:

1. Calculate intermediate result ignoring borrow value
2. Calculate borrow
3. If borrow is 0, return the result
4. If borrow is not 0, calculate the substruction between the borrow and intermediate result (go to step 1)

If we use this algorithm to calculate 12 - 5, we would get the following results:

borrow: 0101 -> 0010 -> 0100 -> 1000 -> 0000
result: 1100 -> 1001 -> 1011 -> 1111 -> 0111

result = 0111 (7)

Now let’s check, what bitwise operators we can use, to implement this logic. For intermediate result, it should correspond to this logical table:

 ----------------
| a | b | result |
 ----------------
| 0 | 0 |   0    |
| 0 | 1 |   1    |
| 1 | 0 |   1    |
| 1 | 1 |   0    |
 ----------------

This is a XOR (^) operator, similar to what we did in addition. For calculating borrow value, it becomes more tricky. The logical table looks like this:

 ----------------
| a | b | borrow |
 ----------------
| 0 | 0 |   0    |
| 0 | 1 |   1    |
| 1 | 0 |   0    |
| 1 | 1 |   0    |
 ----------------

There is no binary operator that would do it out of the box. At the same time, if we invert the first column, we would get the table

 ----------------
| a | b | borrow |
 ----------------
| 1 | 0 |   0    |
| 1 | 1 |   1    |
| 0 | 0 |   0    |
| 0 | 1 |   0    |
 ----------------

This is the logical AND (&) operator. That means that for calculating the borrow value, we need to invert the first operand and then apply logical AND: (~a) & b. Similar to addition, we need to shift the bits to the left: borrow = (~a) & b << 1.

Putting it into the code, we would get:

static int substruct(int a, int b) {
    while (b != 0) {
        int borrow = ((~a) & b) << 1;
        a = a ^ b;
        b = borrow;
    }
    return a;
}

What about negative numbers

Java uses two's complement representation to store signed integers. In the two's complement representation, the leftmost bit (most significant bit) is reserved to represent the sign of the number. If the leftmost bit is 0, the number is positive; if it is 1, the number is negative.

To obtain the two's complement representation of a negative number, we need to follow these steps:

1. Represent the absolute value of the number in binary format (including leading zeros if necessary)
2. Invert all the bits (change 0s to 1s and vice versa)
3. Add 1 to the result from step 2

For example, to obtain the two's complement representation of -3, we can follow these steps:

1. Represent the absolute value of the number 3 in binary format: 00000011
2. Invert all the bits: 11111100
3. Add 1: 11111101 Therefore, the two's complement representation of -3 is 11111101 in binary format.

The advantage of using two's complement representation is that it allows addition and subtraction of signed integers to be performed using the same binary operations as for unsigned integers. That means, that the code that we wrote above, would work just fine with negative numbers as well

Let’s check, how negative numbers would work for our addition algorithm by summing 5 and -3:

result: 00000101 -> 11111000 -> 11110010 -> 11100010 -> 
carry:  11111101 -> 00001010 -> 00010000 -> 00100000 -> 

-> 11000010 -> 10000010 -> 00000010
-> 01000000 -> 10000000 -> 00000000

result -> 10 (2)

Let’s check the same for substruction, for example 5 - (-3)

result: 00000101 -> 11111000 -> 00001000
borrow: 11111101 -> 11110000 -> 00000000

result -> 1000 (8)

As you can see, despite a non-obvious approach for representing negative numbers, it significantly simplifies arithmetics.

Comments

[Tammy W]

Useful information. Much appreciated!