Binary level

Operating at the binary level

System Programming Fundamentals

Operating at the binary level

Bitwise operations
Bitwise AND
Bitwise OR
Bitwise XOR
Bitwise NOT
Bitmasks
Setting a bit (turning a feature **on**)
Clearing a bit (turning a feature **off**)
Toggling a bit (flipping it)
Checking if a bit is set

Bitwise operations

So far we have looked at how various types of data can be encoded in binary strings. Programming languages provide us with operators that can manipulate the data encoded in those binary strings, for example + to sum numbers. But what if we want to manipulate the binary code directly?

For example, the number 6 can be encoded in a byte as 00000110. I can manipulate the number in C using +, -, *, /, %. But what if I want to manipulate the underlying 00000110 byte that represents it?

That's why many languages provide us with bitwise operators. Let's take a look at some of the ones available in C, using the 8-bit integer type uint8_t defined in stdint.h as the binary format of the operands:

bitwise AND

The bitwise AND is represented with the & symbol.

It compares two numbers bit by bit and returns a new value that has set to 1 only the bits that were 1 in both of the original numbers.

For example, if 6 is 00000110 and 4 is 00000100, the only bit they both have set to 1 is the third one from the right, the one with the value 4. So 6 & 4 == 4.

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t x = 6;     // encoded as 00000110
    uint8_t y = 4;     // encoded as 00000100
    uint8_t z = x & y; //     equals 00000100, which is 4

    printf("%u", z); // prints "4"
}

bitwise OR

The bitwise OR is represented with the | symbol.

It compares two numbers bit by bit and returns a new value that has set to 1 all the bits that were 1 in either of the original numbers.

For example, if 6 is 00000110 and 3 is 00000011, you will get 00000111, which has value 7. So 6 | 3 == 7.

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t x = 6;     // encoded as 00000110
    uint8_t y = 3;     // encoded as 00000011
    uint8_t z = x | y; //     equals 00000111, which is 7

    printf("%u", z); // prints "7"
}

bitwise XOR

The bitwise XOR is represented with the ^ symbol.

It compares two numbers bit by bit and returns a new value that has set to 1 the bits that had discording value in the original numbers.

For example, if 3 is 00000011 and 1 is 00000001, they are the same binary string, except for the second bit from the left, which is set to 1 only in one of them. So you will get 00000010, which has value 2. So 3 ^ 1 == 2.

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t x = 3;     // encoded as 00000011
    uint8_t y = 1;     // encoded as 00000001
    uint8_t z = x ^ y; //     equals 00000010, which is 2

    printf("%u", z); // prints "2"
}

bitwise NOT

The bitwise NOT is represented with the ~ symbol.

It takes a numbers and inverts all of its bits.

For example, if 13 is 00001101, its inversion will be 11110010, which has value 242. So ~13 == 242.

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t x = 13;     // encoded as 00001101
    uint8_t y = ~x;     //     equals 11110010, which is 242

    printf("%u", y);  // prints "242"
}

Bitmasks

A bitmask a binary pattern that we use together with bitwise operators to manipulate specific bits in a bitfield.

Let’s revisit the apartment example we used earlier, setting the bits from right to left:

first bit = furnished
second bit = cheap enough
third bit = near bus station
fourth bit = air conditioning
fifth bit = safe area
sixth bit = wifi
last two bits = unused

So, an apartment that satisfies all requirements would be represented by the bitfield 00111111. A bitmask representing the concept of "it's near a bus station" would be 00000100.

Setting a bit (turning a feature on)

Suppose we start with 00000000 (no features), and we find out the apartment has wifi (sixth bit from the right). We can set that bit by making a bitmask with only that bit set to 1 (00100000) and using bitwise OR (|) to combine it with the original bitfield of the apartment.

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t apartment = 0b00000000;  // no features
    uint8_t WIFI_MASK = 0b00100000;  // only sixth bit set

    apartment = apartment | WIFI_MASK;  // turn on wifi bit, obtain 00100000 which is 32

    printf("%u\n", apartment); // prints "32"
}

Now the apartment bitfield is 00100000, meaning "has wifi".

Clearing a bit (turning a feature off)

Suppose the apartment has wifi and AC, so its bitfield is 00101000

but we realize the wifi doesn’t actually work, so we want to turn off the sixth bit. We can do this by making a mask with all 1s except for that bit (11011111) and using bitwise AND (&) on the apartment bitfield to flip that bit, while mantaining the other bits to 1 if they had that value.

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t apartment = 0b00101000;  // wifi + AC
    uint8_t NO_AC_MASK = 0b11011111; // everything except sixth bit

    apartment = apartment & NO_AC_MASK;  // clear wifi bit, obtain 00001000 which is 8

    printf("%u\n", apartment); // prints "8"
}

Now the apartment bitfield is 00001000, meaning "has air conditioning".

Toggling a bit (flipping it)

If we want to flip a bit, regardless of its current value, we can use XOR (^) with a mask:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t apartment = 0b00100000;   // wifi only
    uint8_t AC_MASK =   0b00001000;     // fourth bit, representing AC

    apartment = apartment ^ AC_MASK;  // flip the AC bit regardless of current value, get 00101000 which equals 40

    printf("%u\n", apartment); // prints "40"
}

Now the apartment bitfield is 00101000, meaning "has wifi and AC".

If we run the same toggle again, AC will be removed:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t apartment = 0b00100000;   // wifi only
    uint8_t AC_MASK =   0b00001000;     // fourth bit, representing AC

    apartment = apartment ^ AC_MASK;  // flip the AC bit regardless of current value, get 00101000 which equals 40

    printf("%u\n", apartment); // prints "40"

    apartment = apartment ^ AC_MASK;  // flip the AC bit back to 0, get 00100000 which equals 32

    printf("%u\n", apartment); // prints "32"
}

Checking if a bit is set

To check if the apartment has wifi, we use AND with a mask, and test the result:

#include <stdio.h>
#include <stdint.h>

int main() {
    uint8_t apartment = 0b00101000;  // wifi + AC
    uint8_t WIFI_MASK = 0b00100000;
    uint8_t has_wifi = apartment & WIFI_MASK;

    if (has_wifi) {
        printf("This apartment has wifi!\n");
    } else {
        printf("No wifi here.\n");
    }
}

If the wifi bit is set to 1 on the apartment, the & operator will return the wifi bitmask as it is, otherwise it will return 00000000 because there's no bit set to 1 in both integers.

00000000 is a false-y value in C, so we can use it in our if statement.