Bitwise & Bitshift in Java
Tags: codenewbie, java, beginners, binary
Published: 2021-04-07 09:56:46

In programming we use control flow statements to change the execution of our code. If *this* then *that*, sort of thing. I'm sure we all know the standard keywords, `if`, `else`, `else if`. When we use `if` or `else if` we put a condition in the parenthesis, which will return a boolean, essentially a yes do this, or a no skip this bit of code and move on. 

Here's a (simple) example -
```
if (1 < 2) {
    System.out.println("One is less than two, well played.");
} else {
    System.out.println("Why am I here? No one listens to me.");
}
```
##Conditional, Relational, Equality Operators
In the snippet of code above you can see the **less than** operator `<` evaluating the two operands. 

> An operand is a object which the operator provides a function
> on. In our example above, `1 < 2`, 1 and 2 would be operands.

Other operators we know and love are -
###Relatioinal
- `<=` less than or equal to
- `>` greater than, `>=` greater than or equal to

###Equality
- `==` equal to
- `!=` not equal to

###Conditional
- `||` or
- `&&` and

The last two are interesting, have you ever seen them on their own, like `|` or `&`? Well these are the bitwise version of those conditional operators, bitwise **or** and bitwise **and**. The difference being conditional operators work by evaluating two boolean values, while bitwise operators can evaluate two booleans, or two integer types (whole numbers) by evaluating the binary representation. Lets explore them in more depth.

> Integral types in Java are `byte`, `short`, `int`, `long` and 
> `char`

##Bitwise Operators
Firstly lets have a little look at what an integer looks like in binary. We can use the handy static method `Integer.toBinaryString(int)` and output to console.
```
int twenty = 20;
System.out.println(Integer.toBinaryString(twenty)); // 10100

// the bits are one in position 2^2 (which equals 4) and 2^4 (16)
// 10100
// ^ ^ 
// 16 + 4 = 20
```
> Important note: `Integer.toBinaryString()` does not return 
> extra leading zeroes. An `int` is 32 bits, but only the largest
> bit of the value to smallest bit is shown in the returned 
> string. 

---
### `|` inclusive OR

The inclusive **or** operator will check the binary digits of two integer types, one column at a time, if either is binary 1, then the result is binary 1. Here's an example -

```
int five = 5;  // 0101
int nine = 9;  // 1001
System.out.println(Integer.toBinaryString(five | nine)); // 1101
```

What is happening here? Lets break it down - 
```
// each bit in each column is compared, from left to right -
// 0 or 1, 1 or 0, 0 or 0 and finally 1 or 1

// 0101
// 1001
// ----
// 1101 == decimal 13
```

So you could say when a smaller integer is being compared with a bitwise **or** statement with a larger integer, the result will always at least the value of the bigger number.
***
### `&` AND

The **and** operator will only result in binary one when both bits are binary one. 

```
int three = 3; // 011
int five = 5; //  101
System.out.println(Integer.toBinaryString(three & five)); // 1 

// from right to left, 0 & 1 = 0, 1 & 0 = 0, 1 & 1 = 1
// 011
// 101
// ---
// 001
```

We can use `&` to discover whether a number is odd or even. As 
the only odd digit in a binary pattern is {% katex inline %}2^0{% endkatex %} , the rightmost bit, we can 
use a bit mask to return the first bit, 1 or 0, odd or even, when comparing a number.

```
int nine = 9; // 1001
int six = 6; //  0110
//                  ^ rightmost bit
int bitMask = 1; // 0001
System.out.println(1 == (six & bitMask) ? "Odd" : "Even"); // Odd
System.out.println(1 == (nine & bitMask) ? "Odd" : "Even");// Even
```

> A bitmask is a binary pattern which will allow us to use bitwise
> operators to choose which bits of another pattern to operate on

A common way to check if a number is odd or even is using the modulus operator `%`, which will return the remainder between two numbers. When using modulus 2, any even number will return zero, any odd number one.

```
System.out.println(11 % 2); // 1, we know it's odd
System.out.println(10 % 2); // 0, we know it's even
```
---
### `^` exclusive or XOR

When evaluating two bits it will return 1 only when a single operand is 1. 
```
int five = 5; // 101
int six = 6; // 110
System.out.println(Integer.toBinaryString(five ^ six)); // 11
// 101 
// 110 
// ----
// 011, decimal 3
```
---
### `~` unary complement / NOT

Inverts all binary one bits to zero, and all binary zero bits to one. In essence `NOT 1 == 0`, `NOT 0 == 1`.
```
int five = 5; // 101b
System.out.println(~five); //  
// 101
// --- NOT
// 11111111111111111111111111111010 == -6
```
Hold on, why is `~5`, `101` in binary, inverted with a bitwise NOT `~`, *not* `010`, i.e. decimal 2? Well, computers use binary to represent numbers, both positive *and* negative. One way to represent negative numbers is a numbering scheme called **twos complement**. What this means is the leftmost bit in a binary pattern, or the most significant bit (as it's the largest number), is used to signify whether the number is positive or negative, `1` is for a negative number, `0`positive. As we are using a integer primitive with our bitwise NOT here, an int is 32 bit, or 4 bytes, in size. As mentioned earlier, the method `Integer.toBinaryString()` omits preceeding zeroes in a pattern by default, but the rest of the int is infact filled with zeroes to the MSB on the left. 

So, all those zeroes have now been inverted to ones, but how does that calculate to negative six? Binary is a summation of all bit values which are 1.
```
// 0111
// ^^^^
// ||||_ 2^0 == 1
// |||_ 2^1 == 2
// ||_ 2^2 == 4
// |_ 2^3 == 8
// 
// So summing the bits which are 1 gives us, 4 + 2 + 1 == 7
```
As the MSB is negative if it is 1, and remember our NOT operator inverted it to 1, that value is our base value before we sum the rest of the binary digits from left to right.

Lets do a example with a smaller integer type, `byte` which is 8 bits or, not surprisingly, one byte.
```
byte five = 5;
// 0x00FF is a bitmask in hexadecimal, it means we only see 8 
// bits, representing our byte primitive
System.out.println(Integer.toBinaryString(0x00FF & ~five));
// 11111010
// ||||| |
// ||||| |_ 2^1 == 2
// ||||| 
// |||||_ 2^3 == 8
// ||||_ 2^4 == 16
// |||_ 2^5 == 32
// ||_ 2^6 == 64 
// |_ -2^7 == -128 (Most significant bit)

// Doing the sum;
// -256 + 64 + 32 + 16 + 8 + 2 == -6
```

I hope that helps you understand quickly how we got to negative six as our bitwise NOT result, but do please check [this BBC guide on twos complement](https://www.bbc.co.uk/bitesize/guides/zjfgjxs/revision/5) for some more help if you need it as I won't go into it any deeper.

> Unary means the operator works on only one 
> operand. For example as seen in `for` loops frequently, `i++` 
> unary postfix operator, increments `i` by one.

##Bitshift
There is also some other operators known as bitshift. These move the bits left or right in a binary pattern.
***
### `<<` left shift
Moves the bits in a binary pattern to *n* times to the left. It is represented as `number << placesToShift`, for example `1 << 2`, moves the bits in integer one two places to the left. The effect of moving the bits multiplies the number by {% katex inline %}2^n{% endkatex %}. That is to say, one left shift will multiply the number by {% katex inline %}2^1 = 2{% endkatex %}. A shift two places left would be the number multiplied by {% katex inline %}2^2 = 4{% endkatex %}.

```
System.out.println(2 << 1); // 4
// 0010 == decimal 2
// 0010 << 1 == 0100 == 4
                 ^- 
System.out.println(2 << 2) // 8
// 0010 << 2 == 1000 == 8
                ^--  
```
---
### `>>` right shift
As above, the right shift uses the format `number >> timesToShift`, but it shifts the bits to the right. In effect dividing the number by {% katex inline %}2^n{% endkatex %}.
```
int eight = 8; // 1000 
System.out.println(8 >> 1); // 2^1 == 2. 8 / 2 == 4
// 1000 >> 1 == 0100 == 4
System.out.println(8 >> 2); // 2^2 == 4. 8 / 4 == 2
// 1000 >> 2 == 0010 == 2
System.out.println(8 >> 3); // 2^3 == 8. 8 / 8 == 1
// 1000 >> 4 == 0001 == 1
```

Now you've read this blog you can do this quick trick to impress your coding friends, to divide any number in half `integer >> 1`!

With negative numbers things get a little more interesting. Remember twos compliment uses the most significant bit to declare the number positive or negative, for a positive number bits will be filled with zeroes, for a negative number bits will be filled with ones. The same method applies from the bitwise NOT example above, the binary is summed to find the resulting number.

```
byte negativeFour = -4;
System.out.println(Integer.toBinaryString(0x00FF & 
    negativeFour));      // 11111100
System.out.println(Integer.toBinaryString(0x00FF & 
    negativeFour >> 1)); // 11111110
//                          ^ 1 filled to the left
```

---
### `>>>` unsigned right shift
Twos complement is a signed representation of a number in binary form. That is to say it can represent positive and negative numbers. An unsigned number has no bit that declares it one or the other, so they are always positive. In the case of the unsigned right shift, space after a shift is filled with zeroes, so any negative number will become a positive number as the MSB will no longer be 1.

```
int negativeFour = -4;
System.out.println(Integer.toBinaryString(negativeFour));
System.out.println(Integer.toBinaryString(negativeFour >>> 2));
System.out.println(negativeFour >>> 2);

// Output
// 11111111111111111111111111111100
// ^ MSB is 1, the number is negative
// 00111111111111111111111111111111*
// ^^ shifted two places right and filled with zeroes 
// The final output is the sum of the resulting binary,
// without a sign bit it is a positive number
// 1073741823
```
\* I had to amend the zeroes here for example purposes. The actual output will be without the zeroes.

I hope that is clear for you, it's a little tricky to calculate these long binary patterns just looking at them.

## Example use case of bitshift with booleans
There is really only one bitwise operator which isn't directly translatable with a single conditional operator and that is XOR, exclusive **or**. 

Say you are have a staff rota application. It has employee objects, with a method that returns if they are scheduled to be at work for a given shift. You only need one worker per shift, so you have a method which checks that only one worker is scheduled on a shift at a time, using the `^` operator.
```
// atWork(Date) returns true if employee scheduled for work on 
// that date. Both employees are scheduled for work today.
LocalDate today = LocalDate.now();
if(emplyee1.atWork(today) ^ employee2.atWork(today) {
    // we save the rota if only one employee is working
    workRota.save();
} else {
   // reschedule one of the employees, amend the rota
}
``` 

We can make the same statement with conditional operators but it is a bit more long winded -
```
if (!employee.atWork(today) && employee.atWork(today) 
   || employee.atWork(today) && !employee.atWork(today))
```

It may be a convoluted example that you probably won't have to put in to practice yourself, but it's another tool for your toolbelt, which is never a bad thing.

##Conclusion
Bitwise and bitshift can be confusing at first, possibly you've not seen them often, and you may wonder why you would use them. In fact they can be very useful in algorithms, where manipulating binary bits efficiently is very important. Mainly though, it's good that if you see these in someone else's code you can understand what is happening.
***
Cover image by <a href="https://pixabay.com/users/geralt-9301/?utm_source=link-attribution&amp;utm_medium=referral&amp;utm_campaign=image&amp;utm_content=5180477">Gerd Altmann</a> from <a href="https://pixabay.com/?utm_source=link-attribution&amp;utm_medium=referral&amp;utm_campaign=image&amp;utm_content=5180477">Pixabay</a>