Binary and Bitwise Operations for Fun and Bitmap Decoding

By the time you’re done reading, you’ll understand the joke.

Bitwise operations are a powerful tool that is used in many practical scenarios. Just a few examples are optimizing basic mathematical operations, reducing the bandwidth needed to send packets, congregating multiple booleans into one value (as is done in Unix’s implementation of error codes), and many more. As their use cases are so technical, you’d be forgiven if you believed (as I did at first myself) that any project involving bitwise operations will likely lead to headaches. The reality however is that they can be quite fun! By the end of this post, I hope to have given you a working intuition for how they work so that you can start to develop your own projects incorporating them.

So what are bitwise operators exactly? They are operators in a programming language that help you manipulate values, just like how the + operator might help you turn a 1 into a 2. However, instead of working with values on the basis of base 10 mathematics (our good old system of 0-through-9), bitwise operators treat numbers as binary objects — in other words, they operate in base 2 mathematics.

A brief explanation of binary and base 2, then, is required. Fortunately, base 2 math is really just a simplified version of base 10 math wherein instead of rolling over at 9, values roll over at 1. So let’s go all the way back to preschool for a moment and learn how to count to 10.

In base 10, it’s the same as always: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, and… what’s that next number again? We’ve just run out of digits, but we’re still just short. Oh well, I guess we’ll reset our one’s place to 0 and put a 1 in the next place, the ten’s place. When we write 10, we are really denoting 0 ones and 1 tens.

Now for base 2. It starts out the same: 0 is 0, and 1 is 1, and… what comes next? Nothing. 0 and 1 are the only digits we have. So to represent a 2, so we move our 1 over by one place value and replace it with a 0. So 2 becomes 10 in binary.

Confused? I don’t blame you. Maybe this will clear things up a bit:

Base 10 - Base 2
 0 = 0000
1 = 0001
2 = 0010
3 = 0011
4 = 0100
5 = 0101
6 = 0110
7 = 0111
8 = 1000
9 = 1001
10 = 1010
11 = 1011
12 = 1100
13 = 1101
14 = 1110
15 = 1111

It’s important to note that 1 is essentially binary’s 9. If we have 4 digits to play with in base 10, the largest number we can make is 9,999. Likewise, if we have 4 binary bits to play with, the largest number we can make is 1111, or 15. Since programmed data types come with a fixed number of bits, it is important to understand this limitation to the maximum range of possible values that can be stored. Note also that as we (almost) always do in programming, we start at 0 — so if we have 16 possible values with 4 bits, the largest value will actually be one less than that: 15.

Even more importantly, what happens when we have a 1 with a bunch of 0s after it? In base 10, 10 is of course 10, 100 is 100, and 1000 is 1000. In binary however, 10 is 2, 100 is 4, and 1000 is 8. In base 10 they’re all powers of 10, and in base 2 they’re all powers of 2. This should make sense intuitively, since 10 and 2 are simply the points at which we need to roll over our values. In other words, in base 10: 10 is ten 1s, 100 is ten 10s, and 1000 is ten 100s — we always multiply by the last value. It’s principally the same in base 2: 10 is two 1s, 100 is two 2s, and 1000 is two 4s.

Now that we (hopefully) understand binary, let’s talk about the usefulness of bitwise operations.

Let’s say that we want to transmit an associated set of 16 boolean values over a network. Assuming that this is in our own custom application for which we can define a custom protocol (protocol meaning how we want the information we send to be interpreted on the other side), we can do this by sending one 16-bit number (any value between 0 and 65535) and having it stand for 16 individual true/false values — this is called bit mapping. How would the reading of this work in practice? We’d have to use bitwise operations! Let’s learn about these strange beasts and return to our bit map problem when we’re done.

Python comes equipped with 6 bitwise operators for us to play with:

 &: Binary AND
|: Binary OR
^: Binary XOR
~: Binary One's Complement
<<: Binary Left Shift
>>: Binary Right Shift

For those familiar with boolean logic, these might already seem familiar. For those that aren’t, no worries, we’ll explain how these work in just a moment. All of these operators (except for ~) are used to compare two numbers. This is just like how + and  compare two numbers when written between them, but don’t have that meaning if they are written on their own.

By the way, Python’s built-in bin() and int() functions are about to become very useful. These allow us to convert numbers of many types to their binary or base 10 integer representations. Note that in Python (and programming more generally), a prefix of 0x or 0b denotes a hexadecimal or binary number, respectively. (For example, 10 is 10 and 0b10 is 2.)

Just to make life even easier though, I wrote a tiny wrapper around bin() which presents a more symmetrical representation of our results, making it even easier to interpret them.

def pbin(n):
"""Prints a prettified binary representation of a number."""
bin_rep = bin(n)[2:]
print(('0'*8)[len(bin_rep):] + bin_rep)

Let’s start with binary AND&. Binary AND copies bits to the result only if those bits are present in both numbers. For example…

240 & 60 == 48

Why?

pbin(240)
pbin(60)
pbin(48)
# 11110000
# 00111100
# Becomes...
# 00110000

Notice where the 1s overlap: only the shared 1s got transferred to our result. Bitwise AND is extremely useful for checking for the presence of bits set to 1, and spoiler alert, it’s the tool we’ll be using for our bit map problem. But let’s explore the other bitwise operators first anyway.

Binary OR | set a value if it’s present in either value.

102 | 60 == 126

Because…

pbin(102)
pbin(60)
pbin(126)
# 01100110
# 00111100
# Becomes...
# 01111110

Look at the 1s in the top two numbers and follow them to the bottom — see the pattern?

Binary XOR ^ is a stricter version of binary OR which only sets a bit if it is present in one number but not both.

102 ^ 60 == 126

Because…

pbin(102)
pbin(60)
pbin(90)
# 01100110
# 00111100
# Becomes...
# 01011010

Once again, just trace the 1s in the two top numbers down into the 1s on the bottom and find the pattern.

Next we have ~, or binary one’s complement. This one is tricky to understand as its mechanics involve the way that positive and negative integers are “signed” in two’s complement binary. Suffice it to say however that ~positive_number will give you an equivalent negative number minus one more, and ~negative_number will give you an equivalent positive number plus one more.

~10
# -11
~-11
# 10

Finally there are the binary shifts ( << and >> ), which are two of my personal favorites (and arguably also the easiest to understand).

1 << 4 == 16
# And!
16 >> 4 == 1
pbin(1)
pbin(16)
# 00000001
# 00010000

When we bit shift 1 << 4, we get 1 with four 0s after it (16). When we bit shift 16 >> 4, the zeros go away again. The same naturally extends to more complex numbers.

pbin(0b1011)
pbin(0b1011 << 4)
pbin(0b1011 >> 2)
# 00001011 
# 10110000
# 00000010

Finally, we have our toolkit and are ready to return to our bit map reading problem! Over the network we receive some 16 bit number, i.e. any value from 0 to 65535, and we want to interpret it as 16 unique boolean values. The data is all there, but how to read it?

The answer is bit masking. By applying a very specific number in a binary AND operation, we can check the value at one specific part of our input number.

For example, let’s say we received a 60846 as input, or0b1110110110101110. If we run 60846 & 0b1, we get a zero, because there is no overlap in the bits set to 1. But if we run 60846 & 0b10 we get a 0b10, because the bits overlap. We can check every single bit one at a time by continuously shifting our 0b1 farther and farther over, then cast the values to a bool() (since that’s what we’re treating them as here anyway). Notice how the sequence of Trues and Falses in the following cell matches the sequence of 1s and 0s in 60486 perfectly.

for n in range(16):
print(bool(60846 & (0b1 << n)))
# False
# True
# True
# True
# False
# True
# False
# True
# True
# False
# True
# True
# False
# True
# True
# True

And the following list comprehension will put all of that data in a list for us with just one line of code:

[bool(60846 & (0b1 << n)) for n in range(16)]

Nice! It may have taken a lot of explanation to grok the underlying concepts, but as you can see it’s very simple to actually use this stuff in practice. Let’s try one more nifty little trick.

We can use bitwise operations to check if a number is odd or not. An odd number will have a 1 in the one’s place, so n & 1 will return 1 if odd and 0 otherwise. Since Python interprets any non-zero number as True, this is all that is needed.

-73 & 1 # 1, True
400 & 1 # 0, False

We can use this to filter odd numbers thusly:

odd_numbers = []
for n in range(100):
if n & 1:
odd_numbers.append(n)

That little n & 1 is terse and elegant, isn’t it?

Bitwise operations are widely used in compression, encryption, graphics, network communication, graphics, low-level programming, and essentially any application where the values of individual bits matters. Having this skillset opens a lot of interesting doors in those areas, so you have a lot of options if you want to explore these magic little tools called bitwise operations further. Thanks for reading!