Bit Manipulation

Inside the computer, every value is a row of bits, each 0 or 1. Most of the time you do not think about them, but C lets you work with individual bits directly. This is essential in embedded systems (where each bit of a hardware register may switch an LED or a motor), in network protocols, in graphics, and whenever you need to pack many yes-or-no facts into a small space.

In this lesson you will use the six bitwise operators, set, clear, toggle and test single bits, store several options as flags in one number, count bits, and pack and unpack fields such as the red, green and blue parts of a colour.

Binary in one minute

Each bit position stands for a power of two, starting from the right with 1, then 2, 4, 8 and so on. The 8-bit value 0b00001101 is 8 + 4 + 1 = 13. Bit 0 is the rightmost bit (worth 1), and bit 7 is the leftmost bit of a byte (worth 128). In C23 you can write binary directly with the 0b prefix, and hexadecimal (0x) is a compact way to write bit patterns: each hex digit is exactly four bits, so 0xF0 is 0b11110000.

The bitwise operators

A small function that prints the bits of a byte makes the operators easy to see:

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

void show(const char *label, uint8_t value)
{
    printf("%-8s ", label);
    for (int bit = 7; bit >= 0; bit--) {
        putchar((value >> bit) & 1u ? '1' : '0');
    }
    printf("  (%3u)\n", (unsigned) value);
}

int main(void)
{
    uint8_t a = 0b11001010;
    uint8_t b = 0b10100110;

    show("a", a);
    show("b", b);
    show("a & b", a & b);
    show("a | b", a | b);
    show("a ^ b", a ^ b);
    show("~a", (uint8_t) ~a);
    show("a << 1", (uint8_t) (a << 1));
    show("a >> 2", a >> 2);
    return 0;
}

a        11001010  (202)
b        10100110  (166)
a & b    10000010  (130)
a | b    11101110  (238)
a ^ b    01101100  (108)
~a       00110101  ( 53)
a << 1   10010100  (148)
a >> 2   00110010  ( 50)

Compare the columns bit by bit and every row follows the table. Shifting left by 1 doubles a number and shifting right by 1 halves it (dropping the remainder), as long as no bits fall off the end. In a << 1, the top bit of a was shifted out of the byte, so the result is 148, not 404.

Use unsigned types for bit work. With signed types, shifting a negative value or shifting a 1 into the sign bit causes undefined or implementation-defined behaviour. Even 1 << 31 is a bug when int is 32 bits, because the result does not fit in an int; write 1u << 31. Shifting by a number of places equal to or larger than the type's width is undefined behaviour too.

Set, clear, toggle and test a bit

Four small expressions cover nearly all single-bit work. 1u << n creates a mask with only bit n set:

• Set bit n: v | (1u << n)
• Clear bit n: v & ~(1u << n)
• Toggle bit n: v ^ (1u << n)
• Test bit n: (v >> n) & 1u

Here a row of 8 cinema seats is stored in one byte, one bit per seat:

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

static inline uint8_t set_bit(uint8_t v, int n)    { return v | (uint8_t) (1u << n); }
static inline uint8_t clear_bit(uint8_t v, int n)  { return v & (uint8_t) ~(1u << n); }
static inline uint8_t toggle_bit(uint8_t v, int n) { return v ^ (uint8_t) (1u << n); }
static inline bool test_bit(uint8_t v, int n)      { return (v >> n) & 1u; }

int main(void)
{
    uint8_t seats = 0;                // all 8 seats free
    seats = set_bit(seats, 0);        // seat 0 booked
    seats = set_bit(seats, 3);
    seats = set_bit(seats, 5);
    seats = clear_bit(seats, 3);      // seat 3 cancelled
    seats = toggle_bit(seats, 7);     // seat 7 was free, now booked

    printf("Seats 0-7: ");
    for (int s = 0; s < 8; s++) {
        putchar(test_bit(seats, s) ? 'B' : '.');
    }
    printf("\nRow stored as the number %u\n", (unsigned) seats);
    return 0;
}

Seats 0-7: B....B.B
Row stored as the number 161

Seats 0, 5 and 7 are booked, so the byte holds 1 + 32 + 128 = 161. One byte stores the state of 8 seats; an array of 25 bytes would cover a 200-seat hall.

Flags: several options in one number

Flags are named single-bit masks. Combine them with |, test them with &, and remove one with & ~. This pattern appears all over C libraries and operating systems, for example in file permissions.

#include <stdio.h>

constexpr unsigned PERM_READ  = 1u << 0;   // 1
constexpr unsigned PERM_WRITE = 1u << 1;   // 2
constexpr unsigned PERM_SHARE = 1u << 2;   // 4

void describe(const char *who, unsigned perms)
{
    printf("%-8s read:%d write:%d share:%d\n", who,
           (perms & PERM_READ) != 0, (perms & PERM_WRITE) != 0, (perms & PERM_SHARE) != 0);
}

int main(void)
{
    unsigned teacher = PERM_READ | PERM_WRITE | PERM_SHARE;
    unsigned student = PERM_READ;

    student |= PERM_SHARE;    // give a permission
    teacher &= ~PERM_SHARE;   // take one away

    describe("Teacher", teacher);
    describe("Student", student);
    return 0;
}

Teacher  read:1 write:1 share:0
Student  read:1 write:0 share:1

The brackets in (perms & PERM_READ) != 0 matter: == and != have higher precedence than &, so without them the comparison would happen first.

Counting bits and powers of two

Two classic tricks rely on x - 1, which flips the lowest 1 bit of x and every 0 bit below it. So x & (x - 1) clears the lowest set bit. Repeating that until x is 0 counts the 1 bits, and a number is a power of two exactly when it has a single 1 bit:

#include <stdio.h>

int count_ones(unsigned x)
{
    int count = 0;
    while (x != 0) {
        x &= x - 1;   // clear the lowest set bit
        count++;
    }
    return count;
}

bool is_power_of_two(unsigned x)
{
    return x != 0 && (x & (x - 1)) == 0;
}

int main(void)
{
    unsigned values[] = {0, 1, 6, 64, 255, 1000, 1024};
    for (int i = 0; i < 7; i++) {
        printf("%4u: %d ones, power of two: %s\n", values[i], count_ones(values[i]),
               is_power_of_two(values[i]) ? "yes" : "no");
    }
    return 0;
}

   0: 0 ones, power of two: no
   1: 1 ones, power of two: yes
   6: 2 ones, power of two: no
  64: 1 ones, power of two: yes
 255: 8 ones, power of two: no
1000: 6 ones, power of two: no
1024: 1 ones, power of two: yes

Packing and unpacking fields

Shifts and masks can pack several small values into one number and take them out again. Web colours store red, green and blue as one byte each in the form 0xRRGGBB:

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

int main(void)
{
    uint32_t saffron = 0xFF9933;   // 0xRRGGBB

    unsigned red   = (saffron >> 16) & 0xFF;
    unsigned green = (saffron >> 8) & 0xFF;
    unsigned blue  = saffron & 0xFF;
    printf("Red %u, green %u, blue %u\n", red, green, blue);

    uint32_t darker = ((red / 2) << 16) | ((green / 2) << 8) | (blue / 2);
    printf("Half brightness: 0x%06X\n", (unsigned) darker);
    return 0;
}

Red 255, green 153, blue 51
Half brightness: 0x7F4C19

To read a field, shift it down to the bottom and mask with 0xFF to keep 8 bits. To build a value, shift each field up to its place and combine with |.

Common mistakes

• & versus &&. & works bit by bit; && is logical and short-circuits. 2 & 1 is 0, but 2 && 1 is 1.
• Precedence. x & 1 == 0 means x & (1 == 0). Write (x & 1) == 0.
• Shifting signed values. Use unsigned types, and write 1u << n, not 1 << n.
• Shifting too far. x << 32 on a 32-bit value is undefined behaviour.
• Forgetting promotion. ~ on a uint8_t first converts it to int, so ~a has 32 bits; cast back to uint8_t when you need a byte.

Key points

• &, |, ^ and ~ work on each bit; << and >> move bits left and right.
• Set, clear, toggle and test bit n with |, & ~, ^ and >> n & 1 using the mask 1u << n.
• Flags store several yes-or-no options in one unsigned number.
• x & (x - 1) clears the lowest set bit, which helps count bits and detect powers of two.
• Shifts and masks pack and unpack fields such as colour channels.
• Use unsigned types; C23 adds stdbit.h, binary literals and printf("%b").

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

int main(void)
{
    const char *days[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
    uint8_t present = 0;

    present |= 1u << 0;   // Monday
    present |= 1u << 1;   // Tuesday
    present |= 1u << 3;   // Thursday
    present |= 1u << 5;   // Saturday

    int count = 0;
    for (int d = 0; d < 7; d++) {
        if ((present >> d) & 1u) {
            count++;
        }
    }
    printf("Days present: %d\n", count);

    printf("Absent on:");
    for (int d = 0; d < 7; d++) {
        if (!((present >> d) & 1u)) {
            printf(" %s", days[d]);
        }
    }
    printf("\n");
    return 0;
}

Days present: 4
Absent on: Wed Fri Sun