zeros and ones for bit operations

“Why would I ever need it?”, “WTF?”, “Keep it for yourself, mate”, these are reactions you can sometimes get when try to convince developers to use bit operations (manipulation). To be honest, after university I didn’t have any relationship with bits and thought the same thing – “I can solve all problems without this bloody complicated old school data structure”. Until now. It is amazing data structure. It is not complicated at all and might be very practical. For ex, you have an application with many true or false flags. Normally, we have key value pairs like “something”: “true/false” and that might cause many records records in DB. We can get the same effect with a single integer, just setting bits in particular positions.

Facebook bit example

Let’s follow a flag example and imagine Facebook user account which has three true/false flags:

  • business user
  • admin
  • browser notifying enabled

Information above is stored in bits 0111(0 in the beginning not required) or

  • 0
  • 1 – business user
  • 1 – admin
  • 1 – browser notifications

So… we have a structure, and we need to prepare CRUD(Create, Read, Update, Delete) operations in our code.

Read or check bit

public boolean isBit(int n, int i) {

return (n & (1 << i)) != 0;

}

Let’s quickly analyse what has been done here.

Argument n is a storage of flags, just an integer. If we set all flags enabled we get number 0111 in binary which is equal to 7 in decimal.

Argument i is bit index to be checked. It’s important to note that bits are indexed from right to left and starts from 0.

Let’s say, we want to check admin flag bit, which is the second last bit or in other words has index 1. All flags currently are set to true.

n = 7, i = 1

First, we do (1 << i), which is to shift 1 from the right to the left to ith position and keep others as 0. When i = 1 we get 0010

Then we apply the result for AND operation. This is AND operation for bits:

0111
& 0010
—-
0010

0010 in binary is equal to 2 in decimal. We compare the result to zero to get the final result.
(2 != 0) what is the result? Correct, it’s false. If the ith bit is 0 – we get 0, if it is 1 – we get any non zero number. It’s easy as 2×53, right?

Create, Update or set bit

Let’s say we only have browser notifications enabled within our flags. Which is 0001 or 1 in decimal. We want to set a user as business customer now. That means n = 1, i = 2.

public int setBit(int n, int i) {

return n | (1 << i);

}

(1 << i) – shift 1 from the right to the left to ith position, i = 2 so we get 0100

n | (1 << i) is OR operation for bits, n = 0001, so

0001
| 0100
—-
0101

0101 in binary is equal to 5 in decimal. Easier than you thought!

Delete or clear bit

Let’s say we have all our flags set – 0111, which is 7 in decimal and we want to remove user from admin. isAdmin is bit under index 1.

n = 7, i = 1

public int clearBit(int n, int i) {

return n & ~(1 << i);

}

same old (1 << i), where i = 1. Result is equal to 0010

~ is inverse bits, so ~0010 = 1101

finally we apply AND operation

0111
& 1101
—-
0101

0101 in decimals is equal to 5. So all our flags enabled, except of admin is 5. That was too easy!

To sum up

My goal here is not to teach how to use bit operations. My goal is to point out the importance of them. It is possible to do very advanced operations in situations you never though bit might be helpful. Many people doesn’t agree with me saying this is very low level programming and modern programming languages take care of all that. Even more, focus on business instead of bits. And this is total true. But we talk so much about better performance, response time and costs for hardware. Tricks like these might help to improve all of mentioned. I don’t say we need to use bits in all the situations. No, at all. What I am saying, this is something to consider and keep in mind when designing algorithms and this is something sitting behind all programming languages. The only way to get the most out of tools we are using is is to know how they work. This is basic of all programming languages and nobody has yet discovered better approaches in decades.

Takeaways

  • bits is compact data structure with powerful operations
  • bit operations are usually faster than arithmetic operations
Share: