Introduction To Bit Hacking
Bit hacking is what you do when you read or write individual bits of a larger number. Reading or writing bytes is fairly trivial, but a byte is the smallest chunk that most languages would provide functions for. If you want to access the bits, you'd have to use what are called bitwise operators like
shift. Since we are fiddling with numbers, the operator to get what we want is not as straightforward as a function name. And it feels low level, hence the term "bit hacking".
There are many reasons why you would want to do this, but the common idea is that you want to read or write binary information that is not ascii or anything that does not already have a library. We will see examples later in this tutorial. Please bear in mind that for simplicity, all numbers in the examples are considered
uint8 (unsigned integers taking 8 bits).
The bitwise operators
I suppose a good thing to clarify is the difference between the "logical" operators and their "bitwise" counter part because in high level programming we are more exposed to the former. For example we often have an
if statement and 2 conditions need to be
if itIsTime and foodIsWarm: eat()
How "truthiness" is defined in each programming language is not necessarily consistant and a source of debate, but regarding numbers, the general rule is "0" is
false and any other number is
true. Whereas bitwise operators would do the same thing but on each bit of the number.
We first will see what they do. Let's start with
not since it only has one operand. It is generally represented with the
~ tilde symbol and basically invert all the bits of the operand.
~ 01010101 -------- = 10101010
If we had used a "logical"
not instead, the result would be
00000000 since non-zero is
and is generally represented with a single
&. Each bit in the result will be "1" if the same bit in each operand is "1" as well.
01010101 & 11000011 -------- = 01000001
or is generally represented with a single
|. Each bit in the result will be "1" if at least one of either operand has the same bit set to "1".
01010101 | 11000011 -------- = 11010111
xor is generally represented with
^. It is similar to
or except that each bit in the result will be "1" if either operand has the same bit on, but not both. Hence the name "exclusive or".
01010101 | 11000011 -------- = 10010110
The last 2 operators are
shift operators, you have
shift left and
shift right. It basically moves the bits to the left or to the right. There are exceptions, especially with signed numbers, but generally speaking when the bits are moved outside of the length of the number are lost and the bits introduced are set to "0". Nethertheless there is a way to make a "circular" shift where bits that are shifted outside in one direction are coming back on the other side. We'll see that later in the tutorial.
The shifts operators are represented with
>>. The second operand represents the number of shifts.
00111100 << 00000001 Shift 1 time to the left -------- = 01111000
00111100 >> 00000010 Shift 2 times to the right -------- = 00001111
Now that this is clear. Let's see some real life examples.
Set and combine flags
One common use case of using bitwise operator is when you want to set flags. This is when you want to use each bit of a number in order to store a set of boolean values (yes or no, on or off, true or false). For example in a byte we can store 8 boolean values.
Let's take a very simple real life example. The permissions of a file on a computer are generally represented by a number with 3 flags for your personal access to it: the right to read, write and execute the file (in this specific order). For example if you have the right to read and execute a file, but not the right to write to it, the flags as a binary number would be
101 because only the first and third flags are on. In most programming languages, this is written
0b101, which is 5 in decimal (
0b indicates a binary number). If you're only allowed to read it, it would be
The typical way to use this is to have each option represented by a number that is the one with just its single bit on and to set options using
or. Here is a pseudo code example:
READ = 0b100 # 4 WRITE = 0b010 # 2 EXECUTE = 0b001 # 1 setFilePermissions( "/path/to/file.txt", READ | EXECUTE )
It is quite common to set binary options like this, especially in low level languages like C. I could have written the number 5 or
0b101 instead of
READ | EXECUTE, but the purpose here is to give a name to options once and for all and then use this layer of abstraction to make the code legible.
Each number has only one "1", and represents only one flag. Therefore when you use the
or bitwise operator, you basically combine the flags. But in the grand scheme of things the principle is that if you want to "switch" a specific bit on in a number, you just
or it with a number which only has this bit on. For example if you want to make sure the third bit of a number is on, you
or it with
On a side note, I said we've made the code more "legible". It is true but there is something missleading and this is where the term "hacking" reaches its full potential. While being more legible than "5", it still looks like "READ or EXECUTE" where you actually set both and it is tempting to use
and instead. Trust me you'll get used to it, but one way to see it is as a list of things I can do: "I can read or execute".
In boolean algebra,
or is often represented with a
+ sign, and
and is represented with a
. multiplication sign, which kind of helps, but this is mainly because the rules for reducing an equation are respectively quite similar.
As you can see on the Wikipedia page about bit masking, most bitwise operators can be seen as some sort of masking, but I think it is more obvious with the
and operator. We generally use it to filter out a specific bit or a portion of bits with what is called a mask. And then you can test if the value is not zero. If it is, it means the bit is on. Let's use again our file permissions example. I have the permission as a number and I want to test if I have the permission to read it.
READ = 0b100 # 4 WRITE = 0b010 # 2 EXECUTE = 0b001 # 1 filePermission = getPermission("/path/to/file.txt") if (filePermission & READ) != 0: print "yes" else: print "no"
Here is what happens if the file permission is
101 & 100 --- = 100
You can see the 3rd bit starting from the right is the only bit in both numbers. Since it is in the first
and the second number, this bit is set in the result. And as a consequence is not "0".
And here is what happens if the file permission is
011 & 100 --- = 000
Here the operand don't share any bit in common, therefore the result has "0"s everywhere.
Now you can see how the second number acts as a mask. Every bit that is "0" in the mask will be "0" in the result. I like to think about them as "discarded". Bits that are set to "1" on the mask are kept exactly like they are on the first number. I like to think about them as "preserved".
Let's say I wanted to keep only the 4 lower bits of a byte, I could
and it with the mask
10100011 & 00001111 -------- = 00000011
See? It "discards" from the original number all the bits that are "0" in the mask.
Let's say we wanted to save numbers in a file and we want this file to be as compact as possible. We know that these numbers can only be between 0 and 15. You can represent a number between 0 and 15 with only 4 bits. Therefore if we want to make it compact, we could save 2 numbers in 1 byte.
A way to achieve this is to
shift one of the numbers 4 times to the left and then use
or to combine them. Since both numbers are below or equal to 15, we know that any bit above the 4th bit is necessarily irrelevant and set to zero. Therefore shifting one of the numbers by 4 bits to the left allows us to combine the 2 numbers without having an overlap. All the significant bits of each number is in its own half.
number1 = 0b00001010 # 10 number2 = 0b00001100 # 12 shiftedNumber1 = number1 << 4 # 0b10100000 combined = shiftedNumber1 | number2 # 0b10101100
Then you can save these numbers to a file and it will take half the space. In order to read them from the file. You can use
and to mask the relevant part and shift the first one in the opposite direction.
combined = 0b10101100 number1 = (combined & 0b11110000) >> 4 # 0b00001010 number2 = combined & 0b00001111 # 0b00001100
This process is actually how you would print bytes in hexadecimal (e.g. "A0") because each character is exactly between 0 and 15. It is split in 2 characters. Therefore you would first extract both hex numbers and then print their characters between "0" and "F".
As mentioned earlier, there is a way to make a
shift "circular", that is to say a
shift where the bits that overflow on one side are coming back on the other side. Here is how you would do a left
shift of 3:
number = 0b11110000 circularLeftShifted = (number << 3) | (number >> (8 - 3)) # 0b10000111
It should be quite self-explanatory. We first do a normal left
shift and we combine it using
or with the same number that is shifted in the orther direction by the complementary number of places.
XOR The Space Sheriff
I am sure you'll notice that I have kept
xor for the end. Honestly I struggled to find a good use case for
xor that is neither too simple, nor too complicated. But there is actually a good reason for that:
xor is actually the wizard of them all. I mean all bitwise operators are magical in their own way, but
xor is the most intriguing. It is probably why X-OR, one of the greatest space sheriff of all time is named after it (in the french version). This is why instead of detailed examples, we will concentrate on its interesting properties.
On the simple end of the spectrum, you will find that we can use
xor the same way we use
or in our file permissions example, except that instead of setting the bit to "1", it toggles it. This is already a very interesting property. In actually does the same thing as the
not operator, except you can control which bits are inverted. You mask with "1"s the bits you want to invert/toggle.
Another particularity of
xor is that if you
xor a number with itself, it returns all "0"s. This is why it is used in checksums to compare numbers. It is also used with graphics, hashing, compression, cryptography. It many cases, one particular interesting aspect of
xor that is exploited is the fact that the distribution probability of its output is 50% which is not the case with
Let's check the truth table or these operators to visualize this:
a | b | a AND b a | b | a OR b a | b | a XOR b --------------- -------------- --------------- 0 | 0 | 0 0 | 0 | 0 0 | 0 | 0 0 | 1 | 0 0 | 1 | 1 0 | 1 | 1 1 | 0 | 0 1 | 0 | 1 1 | 0 | 1 1 | 1 | 1 1 | 1 | 1 1 | 1 | 0
As you can see, the output of
and has more chances to be "0" and the output of
or has more chances to be "1". Only the output of
xor is balanced. This makes it interesting for hash functions. You can combine numbers and because of its balanced output, you reduce the chances of two keys clashing.
I know all this is a little bit abstract but in its most simple form, if you want to hash a list of numbers (or anything since everything is a number in a computer) into one number for a quick comparison, you can
xor them all.
hashForPin = 4 ^ 2 ^ 9 ^ 6 hashForDad = 'd' ^ 'a' ^ 'd'
Please bear in mind that there is a big problem with this, so don't use it in your code unless you know the consequences. It does a good job at avoiding collisions (the output being the same for other numbers or words), but it does not take order into account. That is to say, if you hash the word "dad" and the word "add", the result would be the same for both. This is why there are tons of hashing algorithms that are all way more complicated than just
xoring the numbers. But it is the building block for them.
Obviously the fact that the order don't matter could be exploited as well. It could be exactly what you want.
Parts in code where you use bitwise operators are generally hard to read, therefore I encourage you to bury these under a specific function with a clear name. In order to give more examples, we will publish another article commenting a project using some of these principles.