Simple arithmetics with bitwise operators in Java
Tags: java, beginners
Published: 2023-03-05 15:17:55

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.