Bit-Level Operations

1The operators

These are not the logical operators. & works on every bit independently and yields a number; && treats its operands as true or false and yields 0 or 1. 1 & 2 is 0; 1 && 2 is 1. Confusing them compiles cleanly and produces wrong answers.

Shifting is multiplication and division by powers of two

x << n      /* x * 2^n */
x >> n      /* x / 2^n, for non-negative x */

Write the multiplication. Any compiler since the 1990s emits a shift for x * 8, and x * 8 says what you mean. Use shifts when you are genuinely manipulating bit positions, not as an optimization.

The shift traps

• Shifting by the width of the type or more is undefined behavior. x << 32 on a 32-bit int is not zero; it is undefined, and in practice x86 shifts by 32 % 32 = 0, leaving x unchanged.
• Shifting a negative value left is undefined.
• Right-shifting a negative value is implementation-defined: it may fill with zeros (logical) or with the sign bit (arithmetic). Every mainstream compiler does the arithmetic shift, which preserves the sign — but it is not guaranteed.

The rule that follows: do bit manipulation on unsigned types. unsigned, or better the fixed-width uint32_t from week 37. Signedness has no meaning when you are treating a value as a row of bits, and it introduces three ways to be undefined.

2The four idioms

Almost all bit manipulation is one of these four, written against a mask that selects the bits you care about.

#define FLAG_READ   (1u << 0)     /* 0001 */
#define FLAG_WRITE  (1u << 1)     /* 0010 */
#define FLAG_EXEC   (1u << 2)     /* 0100 */

unsigned flags = 0;

flags |=  FLAG_READ;              /* SET    */
flags &= ~FLAG_READ;              /* CLEAR  */
flags ^=  FLAG_READ;              /* TOGGLE */
if (flags & FLAG_READ) { … }      /* TEST   */

Building masks: 1u << n selects bit n. Several bits are combined with |. A mask of the low n bits is (1u << n) - 1.

Testing several bits

if ((flags & (FLAG_READ | FLAG_WRITE)) == (FLAG_READ | FLAG_WRITE)) {
    /* BOTH are set */
}
if (flags & (FLAG_READ | FLAG_WRITE)) {
    /* at least ONE is set */
}

The difference is easy to get wrong and easy to state: comparing against the mask tests "all", comparing against zero tests "any".

3Packing values into one integer

When several small quantities travel together — a colour, a date, a hardware register — they can share one word. Two operations: pack with shift-and-OR, unpack with shift-and-mask.

/* Pack an RGB colour into 24 bits. */
uint32_t rgb = ((uint32_t)r << 16) | ((uint32_t)g << 8) | b;

/* Unpack. */
uint8_t red   = (rgb >> 16) & 0xFF;
uint8_t green = (rgb >>  8) & 0xFF;
uint8_t blue  =  rgb        & 0xFF;

The mask after the shift is essential: without & 0xFF, rgb >> 8 still carries the red bits above the green ones.

This is exactly how a hardware register is written in week 50, how an instruction is encoded, and how a network protocol header is laid out. The pattern does not change; only the field widths do.

4Bit-fields

C offers syntax for this directly:

struct Flags {
    unsigned read  : 1;      /* one bit  */
    unsigned write : 1;
    unsigned level : 3;      /* three bits, values 0-7 */
    unsigned       : 0;      /* force alignment to the next unit */
};

struct Flags f = { .read = 1, .level = 5 };
if (f.read) { … }

Readable, type-checked, and the compiler does the shifting. So why does most portable C avoid them?

So a bit-field struct cannot be used to describe an external binary format — a file header, a network packet, a hardware register — because the layout is not guaranteed to match. Use explicit masks and shifts for anything that crosses a boundary, and reserve bit-fields for internal storage where only your own code sees them.

Note also the last item: always write unsigned or signed explicitly on a bit-field. Plain int has implementation-defined signedness here, and a one-bit signed field can hold only 0 and −1, which surprises everyone once.

5Worked example: permissions, packing, and popcount

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <time.h>

/* ---------- named flags ---------- */

typedef enum {
    PERM_READ    = 1u << 0,
    PERM_WRITE   = 1u << 1,
    PERM_EXEC    = 1u << 2,
    PERM_DELETE  = 1u << 3,
    PERM_ALL     = 0x0Fu
} Permission;

static void print_bits(uint32_t value, int width)
{
    for (int bit = width - 1; bit >= 0; bit--) {
        putchar((value >> bit) & 1u ? '1' : '0');
        if (bit % 4 == 0 && bit != 0) putchar(' ');
    }
}

static void show_permissions(const char *label, unsigned flags)
{
    printf("  %-14s %c%c%c%c  ", label,
           (flags & PERM_READ)   ? 'r' : '-',
           (flags & PERM_WRITE)  ? 'w' : '-',
           (flags & PERM_EXEC)   ? 'x' : '-',
           (flags & PERM_DELETE) ? 'd' : '-');
    print_bits(flags, 8);
    printf("  (0x%02X)\n", flags);
}

/* ---------- packing ---------- */

static uint32_t rgb_pack(uint8_t r, uint8_t g, uint8_t b)
{
    return ((uint32_t)r << 16) | ((uint32_t)g << 8) | (uint32_t)b;
}

static void rgb_unpack(uint32_t rgb, uint8_t *r, uint8_t *g, uint8_t *b)
{
    *r = (uint8_t)((rgb >> 16) & 0xFFu);
    *g = (uint8_t)((rgb >>  8) & 0xFFu);
    *b = (uint8_t)( rgb        & 0xFFu);
}

/* ---------- counting set bits, three ways ---------- */

static int popcount_naive(uint32_t v)
{
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += (int)((v >> i) & 1u);
    }
    return count;                          /* always 32 iterations */
}

/* Kernighan's method: v & (v-1) clears the lowest set bit,
   so the loop runs once per SET bit rather than once per bit. */
static int popcount_kernighan(uint32_t v)
{
    int count = 0;
    while (v != 0) {
        v &= v - 1;
        count++;
    }
    return count;
}

/* ---------- a simple checksum ---------- */

static uint32_t checksum(const uint8_t *data, size_t n)
{
    uint32_t sum = 0;
    for (size_t i = 0; i < n; i++) {
        sum ^= data[i];
        sum = (sum << 1) | (sum >> 31);    /* rotate left by one */
    }
    return sum;
}

/* ---------- bit-fields, for internal use only ---------- */

struct Packed {
    unsigned read  : 1;
    unsigned write : 1;
    unsigned level : 3;
};

int main(void)
{
    puts("== the four idioms ==");
    unsigned flags = 0;
    show_permissions("start", flags);

    flags |= PERM_READ;                   show_permissions("set read", flags);
    flags |= PERM_WRITE | PERM_EXEC;      show_permissions("set w+x", flags);
    flags &= ~(unsigned)PERM_WRITE;       show_permissions("clear write", flags);
    flags ^= PERM_EXEC;                   show_permissions("toggle exec", flags);
    flags |= PERM_ALL;                    show_permissions("set all", flags);

    puts("\n== any versus all ==");
    unsigned rw = PERM_READ | PERM_WRITE;
    unsigned only_read = PERM_READ;
    printf("  only_read has ANY of r|w : %s\n",
           (only_read & rw) ? "yes" : "no");
    printf("  only_read has ALL of r|w : %s\n",
           ((only_read & rw) == rw) ? "yes" : "no");

    puts("\n== the precedence trap ==");
    unsigned f = 0x0C;
    printf("  f & PERM_EXEC == 0    gives %u   <-- parses as f & (EXEC==0)\n",
           f & PERM_EXEC == 0);
    printf("  (f & PERM_EXEC) == 0  gives %d   <-- what you meant\n",
           (f & PERM_EXEC) == 0);

    puts("\n== packing and unpacking ==");
    uint32_t colour = rgb_pack(255, 128, 64);
    printf("  rgb(255,128,64) = 0x%06X  ", colour);
    print_bits(colour, 24);
    putchar('\n');
    uint8_t r, g, b;
    rgb_unpack(colour, &r, &g, &b);
    printf("  unpacked        = (%u, %u, %u)\n", r, g, b);
    printf("  without the mask, (colour >> 8) = 0x%X  <-- red bits still there\n",
           colour >> 8);

    puts("\n== shifting ==");
    uint32_t v = 0x0000000Fu;
    printf("  0x0F << 4  = 0x%08X   (multiply by 16)\n", v << 4);
    printf("  0xF0 >> 4  = 0x%08X   (divide by 16)\n", 0xF0u >> 4);
    int negative = -16;
    printf("  -16 >> 2   = %d   (arithmetic shift here, but not guaranteed)\n",
           negative >> 2);
    puts("  do bit work on unsigned types and the question does not arise");

    puts("\n== counting set bits ==");
    uint32_t samples[] = { 0x00000000u, 0x00000001u, 0x0000FFFFu, 0xFFFFFFFFu };
    for (size_t i = 0; i < 4; i++) {
        printf("  0x%08X : naive %2d, kernighan %2d\n", samples[i],
               popcount_naive(samples[i]),
               popcount_kernighan(samples[i]));
    }

    clock_t t0 = clock();
    long total = 0;
    for (uint32_t i = 0; i < 3000000u; i++) total += popcount_naive(i);
    double naive_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

    t0 = clock();
    total = 0;
    for (uint32_t i = 0; i < 3000000u; i++) total += popcount_kernighan(i);
    double kern_time = (double)(clock() - t0) / CLOCKS_PER_SEC;

    printf("  3M values: naive %.3fs, Kernighan %.3fs\n",
           naive_time, kern_time);
    puts("  v &= v-1 clears the lowest set bit, so the loop runs once per 1");

    puts("\n== a checksum ==");
    const char *text = "the quick brown fox";
    printf("  checksum(\"%s\") = 0x%08X\n",
           text, checksum((const uint8_t *)text, 19));
    printf("  checksum(\"the quick brown fpx\") = 0x%08X  <-- one byte changed\n",
           checksum((const uint8_t *)"the quick brown fpx", 19));

    puts("\n== bit-fields: convenient, but not portable ==");
    struct Packed p = { .read = 1, .write = 0, .level = 5 };
    printf("  read=%u write=%u level=%u, sizeof = %zu\n",
           p.read, p.write, p.level, sizeof p);
    puts("  the standard does not fix the order or the padding,");
    puts("  so never use a bit-field struct to describe a file or packet format");

    return EXIT_SUCCESS;
}

gcc -std=c17 -Wall -Wextra -g -o bits bits.c
./bits

The warning that proves the trap

bits.c:118:32: warning: suggest parentheses around comparison
              in operand of '&' [-Wparentheses]

The output shows f & PERM_EXEC == 0 evaluating to 0 while (f & PERM_EXEC) == 0 gives 1. Same tokens, opposite meanings, one warning between you and a silent bug.

Provoke the undefined shift

uint32_t x = 1;
printf("%u\n", x << 32);     /* undefined behavior */

warning: left shift count >= width of type [-Wshift-count-overflow]

Run it and you will probably see 1, not 0 — x86 uses only the low five bits of the shift count, so a shift by 32 is a shift by 0. Build with -fsanitize=undefined and it is reported explicitly:

runtime error: shift exponent 32 is too large for 32-bit type

Why Kernighan's method is faster

v & (v - 1) clears the lowest set bit: subtracting 1 flips that bit to 0 and every bit below it to 1, so the AND keeps only the bits above. The loop therefore runs once per set bit rather than once per bit position. For sparse values the difference is large; for 0xFFFFFFFF the two are identical. The timing in the output shows it on a realistic mix.

6Common mistakes

8Where this leads

Week 26 turns to files and streams — opening, reading, writing, positioning, and the buffering that explains why output sometimes appears late. The binary record format built there is the first place this week's packing matters outside your own process, and week 37 then makes such a format portable across machines with different byte order.