Bit Manipulation Techniques

Before manipulating bits, you must see them clearly. An N-bit unsigned integer is just a polynomial: bit k contributes 2^k to the value. So the 8-bit pattern 0b00101101 equals 0×128 + 0×64 + 1×32 + 0×16 + 1×8 + 1×4 + 0×2 + 1×1 = 45.

C gives you three ways to write integer literals that make bit patterns explicit:

• Hexadecimal (0x2D): each hex digit is exactly four bits, so 0x2D = 0010 1101. This is the dominant style in kernel code because it groups bits cleanly.
• Octal (055): three bits per digit; used almost exclusively for file permission modes (0755, 0644) because Unix permissions are three groups of three bits.
• Binary (0b00101101): C99/C11 with GCC extension; maximally explicit, useful for masks where the bit pattern is the whole point.

For signed integers, two's complement is universal on every real CPU. The sign bit (the most-significant bit) has a weight of −2^(N−1) instead of +2^(N−1). So 0xFF as int8_t is −1. This becomes critical when you right-shift signed values — the C standard calls arithmetic vs. logical right shift implementation-defined for signed types, which is why kernel code almost always works with unsigned types for bit manipulation.

The C types you will use most:

• uint8_t, uint16_t, uint32_t, uint64_t — exact-width, always unsigned, defined in <stdint.h> and <linux/types.h>
• unsigned long — the kernel's workhorse; on a 64-bit platform it is 64 bits, matching the native word size
• __u32, __u64 — kernel-internal variants that avoid userspace namespace pollution

Always use unsigned types for bit manipulation unless you have a specific reason not to. Signed overflow is undefined behavior in C; unsigned wraparound is defined and predictable.

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

int main(void) {
    uint8_t  x = 0b00101101;  /* binary literal (GCC extension) */
    uint8_t  y = 0x2D;        /* same value, hex */
    uint8_t  z = 045;         /* same value, octal */

    printf("x=%u  y=%u  z=%u\n", x, y, z);  /* all print 45 */

    /* Two's complement: 0xFF as signed 8-bit is -1 */
    int8_t  s = (int8_t)0xFF;
    printf("s=%d\n", s);  /* prints -1 */

    /* Arithmetic vs logical right shift - avoid with signed! */
    int32_t  neg = -1;
    uint32_t pos = (uint32_t)neg;
    printf("neg>>1=%d  pos>>1=%u\n", neg>>1, pos>>1);
    /* neg>>1 is implementation-defined; pos>>1 is always 0x7FFFFFFF */
    return 0;
}

Everything in bit manipulation reduces to four operations applied to each pair of corresponding bits independently. Think of them as per-bit logic gates:

AND (&) — both inputs must be 1 for the output to be 1. It is a filter: it forces bits to 0 wherever the mask is 0, and leaves bits unchanged wherever the mask is 1. Use it to isolate (extract) a field.

OR (|) — at least one input must be 1. It is a setter: it forces bits to 1 wherever the mask is 1, and leaves bits unchanged wherever the mask is 0. Use it to set flags.

XOR (^) — inputs must differ for the output to be 1. It is a toggler: wherever the mask is 1, the corresponding bit flips; wherever the mask is 0, the bit is unchanged. XOR also has the beautiful property that x ^ x == 0 and x ^ 0 == x, making it the foundation of many bit hacks.

NOT (~) — unary, inverts every bit. This is the bitwise complement. On an 8-bit type, ~0x0F == 0xF0. Beware: in C, ~ on a value of type int produces an int, and integer promotion can surprise you. Always cast back to your intended type.

The shift operators are equally fundamental:

• Left shift (<<): shift all bits toward the MSB by n positions, filling vacated LSBs with 0. Equivalent to multiplication by 2^n for unsigned types. 1u << 3 == 8.
• Right shift (>>): shift toward the LSB. For unsigned types, vacated MSBs are filled with 0 (logical shift). For signed types, behavior is implementation-defined but all real CPUs do arithmetic shift (fill with sign bit). The C standard ratified this with C99 for most targets.

Critical rule: never shift by a negative amount, and never shift by an amount ≥ the width of the type. Both are undefined behavior in C. The kernel guards against this with helper macros like BIT(n) which includes a static assertion in debug builds.

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

int main(void) {
    uint8_t a = 0b11001010;  /* 0xCA */
    uint8_t b = 0b10110110;  /* 0xB6 */

    printf("a & b = 0x%02X\n", a & b);   /* AND:  0x82 = 1000 0010 */
    printf("a | b = 0x%02X\n", a | b);   /* OR:   0xFE = 1111 1110 */
    printf("a ^ b = 0x%02X\n", a ^ b);   /* XOR:  0x7C = 0111 1100 */
    printf("~a    = 0x%02X\n", (uint8_t)~a); /* NOT: 0x35 = 0011 0101 */

    printf("1u<<3 = %u\n", 1u << 3);     /* 8  */
    printf("0x80u>>4 = 0x%02X\n", (uint8_t)(0x80u >> 4)); /* 0x08 */

    /* XOR swap (educational; prefer tmp variable in real code) */
    uint32_t x = 0xDEAD, y = 0xBEEF;
    x ^= y;  y ^= x;  x ^= y;
    printf("x=0x%X y=0x%X\n", x, y);  /* x=0xBEEF y=0xDEAD */
    return 0;
}

A mask is a value whose bit pattern specifies which bits you care about. The discipline of masking is the core skill of bit manipulation.

Extracting a field: To read bits [high:low] from a value, you right-shift by low to bring the field to the LSB, then AND with a mask of (1u << width) - 1 to zero out everything above it.

field = (value >> low) & ((1u << width) - 1)

The (1u << width) - 1 trick works because shifting 1 left by width positions gives 1000...0 with width trailing zeros; subtracting 1 turns that into 0111...1 — exactly width ones.

Inserting a field: To write a value into bits [high:low], first clear the target bits with value & ~(mask << low), then OR in the new value shifted into position: (new_value & mask) << low. Combined:

value = (value & ~(mask << low)) | ((new_value & mask) << low)

This read-modify-write pattern is everywhere in hardware register programming. The key insight is that AND with an inverted mask clears a field, and OR with a shifted value sets it.

Constructing masks: The kernel uses the GENMASK(hi, lo) macro which generates a mask with bits [hi:lo] all set:

#define GENMASK(h, l)  (((~0UL) << (l)) & (~0UL >> (BITS_PER_LONG - 1 - (h))))

For GENMASK(5, 2) on a 32-bit system: 0b00...00111100 — bits 2, 3, 4, 5 are set.

Masks are also how you deal with packed hardware registers, network protocol headers, and ELF binary fields — all scenarios you will hit in kernel code within your first few hundred lines.

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

/* Extract bits [high:low] inclusive from val */
static inline uint32_t extract_field(uint32_t val, int low, int width) {
    return (val >> low) & ((1u << width) - 1u);
}

/* Insert 'field' into bits [low+width-1:low] of val */
static inline uint32_t insert_field(uint32_t val, uint32_t field,
                                    int low, int width) {
    uint32_t mask = (1u << width) - 1u;
    return (val & ~(mask << low)) | ((field & mask) << low);
}

int main(void) {
    /* Imagine a hardware status register:
     * bits [7:5] = error_code (3 bits)
     * bits [4:2] = mode      (3 bits)
     * bits [1:0] = state     (2 bits)
     */
    uint32_t reg = 0b10110101;  /* 0xB5 */

    uint32_t state      = extract_field(reg, 0, 2);  /* 01 = 1 */
    uint32_t mode       = extract_field(reg, 2, 3);  /* 101 = 5 */
    uint32_t error_code = extract_field(reg, 5, 3);  /* 101 = 5 */

    printf("state=%u mode=%u error_code=%u\n", state, mode, error_code);

    /* Write mode=7 (0b111) into the register */
    uint32_t new_reg = insert_field(reg, 7, 2, 3);
    printf("new_reg=0x%02X\n", new_reg);  /* 0b10111101 = 0xBD */
    return 0;
}

In systems code, you constantly need to manage individual boolean flags packed into an integer — a set of capabilities, a collection of state bits, a permission mask. Four operations cover every use case:

Set bit n (force to 1):

flags |= (1u << n);

OR with a mask that has only bit n set. All other bits are unchanged because x | 0 == x.

Clear bit n (force to 0):

flags &= ~(1u << n);

AND with the bitwise complement of a mask that has only bit n set. The complement has 0 at position n and 1 everywhere else. Since x & 1 == x and x & 0 == 0, only bit n is affected.

Toggle bit n (flip):

flags ^= (1u << n);

XOR with a mask. Since x ^ 1 flips x and x ^ 0 == x, only bit n changes.

Test bit n (read its value):

bool is_set = (flags >> n) & 1u;
/* or equivalently: */
bool is_set2 = !!(flags & (1u << n));

The first form shifts bit n to position 0 then masks; the second masks and converts to boolean with double negation. Both are correct; the second form avoids the risk of the result being non-zero-but-not-one.

In the Linux kernel, the BIT(n) macro (defined as (1UL << (n))) is used pervasively so that bit numbers are always visible at the call site:

#define PG_locked   0
#define PG_dirty    4
/* Set the dirty flag on a page */
set_bit(PG_dirty, &page->flags);
/* Test it */
if (test_bit(PG_locked, &page->flags)) { ... }

These set_bit/clear_bit/test_bit kernel functions also handle SMP atomicity — crucial when multiple CPUs may modify the same flag word simultaneously.

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

/* Inline helpers matching the mental model */
#define BIT(n)          (1u << (n))
#define SET_BIT(v, n)   ((v) |  BIT(n))
#define CLR_BIT(v, n)   ((v) & ~BIT(n))
#define TOG_BIT(v, n)   ((v) ^  BIT(n))
#define TST_BIT(v, n)   (!!((v) & BIT(n)))

/* Simulated task flags (like parts of task_struct::flags) */
#define TIF_SIGPENDING   0
#define TIF_NEED_RESCHED 1
#define TIF_MEMDIE       9

int main(void) {
    uint32_t tflags = 0;

    tflags = SET_BIT(tflags, TIF_SIGPENDING);
    tflags = SET_BIT(tflags, TIF_NEED_RESCHED);
    printf("flags after set: 0x%08X\n", tflags);  /* 0x00000003 */

    printf("SIGPENDING? %d\n",   TST_BIT(tflags, TIF_SIGPENDING));   /* 1 */
    printf("MEMDIE?     %d\n",   TST_BIT(tflags, TIF_MEMDIE));       /* 0 */

    tflags = CLR_BIT(tflags, TIF_SIGPENDING);
    printf("after clear: 0x%08X\n", tflags);  /* 0x00000002 */

    tflags = TOG_BIT(tflags, TIF_NEED_RESCHED);
    printf("after toggle: 0x%08X\n", tflags); /* 0x00000000 */
    return 0;
}

Bit hacks are algorithms that use bitwise operations to perform what looks like arithmetic, but faster or more elegantly than the obvious approach. Understanding why they work deepens your intuition for the binary number system.

Power-of-two alignment (round up to next multiple of a power-of-two p):

aligned = (value + p - 1) & ~(p - 1);

If p = 16 = 0x10, then p-1 = 0xF and ~(p-1) = 0xFFFFFFF0. ANDing with this clears the low 4 bits, forcing alignment to 16. Adding p-1 first ensures we round up. The kernel uses this constantly for memory alignment: ALIGN(x, a) in <linux/kernel.h>.

Test if a value is a power of two:

bool is_pow2 = (n != 0) && ((n & (n - 1)) == 0);

A power of two has exactly one bit set: 1000...0. Subtracting 1 flips that bit and sets all lower bits: 0111...1. AND-ing them gives 0. Any non-power-of-two has at least two bits set and the AND is nonzero. The kernel macro is_power_of_2(n) does exactly this.

Isolate the lowest set bit:

uint32_t lsb = n & (-n);   /* or n & (~n + 1) -- same thing in two's complement */

This is a beautiful two's-complement identity. -n is the two's complement negation, which inverts all bits and adds 1. The carry from adding 1 propagates through the trailing zeros and flips the lowest set bit back to 1, leaving everything above it inverted. The AND gives only the position of the original lowest set bit.

Clear the lowest set bit:

uint32_t cleared = n & (n - 1);

Subtracting 1 from n borrows from the lowest set bit, turning it to 0 and setting all lower bits. ANDing with original n clears all those changed bits. This is used in __builtin_popcount implementations and in traversing set bits.

Population count (count set bits):

/* Kernighan's method: O(number of set bits) */
int popcount(uint32_t n) {
    int count = 0;
    while (n) { n &= n - 1; count++; }
    return count;
}
/* Or just: __builtin_popcount(n) on GCC */

Find the position of the highest set bit (floor of log2):

31 - __builtin_clz(n);  /* count leading zeros; valid for n > 0 */

The kernel wraps this as fls() (find last set) and fls64().

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

int main(void) {
    /* Alignment */
    uint32_t x = 57;
    uint32_t aligned16 = (x + 15u) & ~15u;
    printf("%u aligned to 16 = %u\n", x, aligned16);  /* 64 */

    /* Power-of-two test */
    for (uint32_t n = 0; n <= 20; n++) {
        int p2 = (n != 0) && ((n & (n-1)) == 0);
        if (p2) printf("%u is a power of two\n", n);
    }
    /* prints: 1 2 4 8 16 */

    /* Lowest set bit */
    uint32_t val = 0b10110100;  /* 0xB4 */
    printf("lsb of 0x%02X = 0x%02X\n", val, val & (uint32_t)(-(int32_t)val));
    /* 0xB4 & 0x4C = 0x04 — bit 2 */

    /* Iterate over all set bits */
    uint32_t mask = 0b10110100;
    printf("set bits in 0x%02X: ", mask);
    uint32_t tmp = mask;
    while (tmp) {
        uint32_t lsb = tmp & (uint32_t)(-(int32_t)tmp);
        int bit_pos = __builtin_ctz(tmp);  /* count trailing zeros */
        printf("%d ", bit_pos);
        tmp &= tmp - 1;  /* clear lowest set bit */
    }
    printf("\n");  /* 2 4 5 7 */
    return 0;
}

In real systems code, individual bit positions always get symbolic names. Raw numbers like flags |= (1u << 3) are unmaintainable — was bit 3 the dirty flag or the locked flag? The canonical pattern is to define each flag as a named constant equal to BIT(n), then use those names everywhere.

The Linux kernel uses this pattern for literally everything. Let us trace through a real example: file access mode flags in <fcntl.h> / <linux/fcntl.h>:

#define O_RDONLY    00000000
#define O_WRONLY    00000001
#define O_RDWR      00000002
#define O_CREAT     00000100   /* octal: bit 6 */
#define O_TRUNC     00001000   /* octal: bit 9 */
#define O_NONBLOCK  00004000   /* octal: bit 11 */

These are ORed together: open("file", O_WRONLY | O_CREAT | O_TRUNC, 0644). The kernel then tests each flag individually: if (flags & O_NONBLOCK) ....

When defining your own flag sets, follow these rules:

1. Use BIT(n) or explicit power-of-two hex/binary values — never consecutive integers (that is an enum, not a flag set).
2. Name the zero value explicitly if it has a meaning: #define STATE_IDLE 0.
3. Define compound masks where useful: #define PERMS_READ_WRITE (O_RDONLY | O_RDWR) — but test with the appropriate operator: if ((flags & PERMS_READ_WRITE) == O_RDWR).
4. For kernel code, prefer BIT() or BIT_ULL() for 64-bit flags:

#define PG_locked      0
#define PG_referenced  1
#define PG_uptodate    2
/* BIT() usage at the call site */
if (PageFlags(page) & BIT(PG_dirty)) ...

C also has a struct bitfield syntax (unsigned int dirty : 1;) which the compiler packs into a word. However, the layout is compiler-and-platform-defined, so it is never safe to use for hardware registers, wire protocols, or on-disk formats. Use explicit masking for those. Struct bitfields are occasionally used in the kernel for internal bookkeeping where layout does not matter.

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

/* Define a set of capability flags for a hypothetical driver */
#define DRV_CAP_DMA        (1u << 0)   /* hardware DMA support */
#define DRV_CAP_IRQ        (1u << 1)   /* can generate interrupts */
#define DRV_CAP_SCATTER    (1u << 2)   /* scatter-gather DMA */
#define DRV_CAP_HOTPLUG    (1u << 4)   /* supports hotplug */
#define DRV_CAP_64BIT      (1u << 7)   /* 64-bit address bus */

/* Compound mask: DMA that can actually do something useful */
#define DRV_CAP_DMA_FULL   (DRV_CAP_DMA | DRV_CAP_SCATTER)

void describe_caps(uint32_t caps) {
    printf("DMA:     %s\n", (caps & DRV_CAP_DMA)     ? "yes" : "no");
    printf("IRQ:     %s\n", (caps & DRV_CAP_IRQ)     ? "yes" : "no");
    printf("Scatter: %s\n", (caps & DRV_CAP_SCATTER) ? "yes" : "no");
    printf("Hotplug: %s\n", (caps & DRV_CAP_HOTPLUG) ? "yes" : "no");
    printf("64-bit:  %s\n", (caps & DRV_CAP_64BIT)   ? "yes" : "no");
    /* Test compound: needs ALL bits of DMA_FULL */
    bool full_dma = (caps & DRV_CAP_DMA_FULL) == DRV_CAP_DMA_FULL;
    printf("Full DMA: %s\n", full_dma ? "yes" : "no");
}

int main(void) {
    uint32_t my_caps = DRV_CAP_DMA | DRV_CAP_IRQ | DRV_CAP_64BIT;
    describe_caps(my_caps);
    /* DMA: yes, IRQ: yes, Scatter: no, Hotplug: no, 64-bit: yes */
    /* Full DMA: no (scatter is missing) */
    return 0;
}

A bitmap (or bitset) is an array of words used to track the state of N boolean items. If you have 1024 items and 64-bit words, you need only 16 words (128 bytes) instead of 1024 bytes. The Linux kernel uses bitmaps everywhere: to track which CPU IDs are online (cpumask_t), which pages in a zone are free, which IRQ lines are in use.

The fundamental operations:

Finding the word and bit for item i (with 64-bit words):

word_index = i / 64;   /* or i >> 6 */
bit_within_word = i % 64;  /* or i & 63 */

Setting, clearing, testing item i:

bitmap[i / 64] |=  (1UL << (i % 64));  /* set */
bitmap[i / 64] &= ~(1UL << (i % 64));  /* clear */
bool set = (bitmap[i / 64] >> (i % 64)) & 1UL;  /* test */

Finding the next set bit (scanning for the next 1 starting from position p): This is the key performance-critical operation. The naive approach checks bit by bit, but the fast approach skips whole zero words using __builtin_ctzl() (count trailing zeros) to find the first set bit within a non-zero word:

for (word = p/64; word < nwords; word++) {
    unsigned long w = bitmap[word];
    if (w) return word * 64 + __builtin_ctzl(w);
}

The Linux kernel bitmap API (in <linux/bitmap.h>):

• DECLARE_BITMAP(name, n_bits) — declares a unsigned long array of the right size
• bitmap_set(map, start, n) — sets n bits starting at start
• bitmap_clear(map, start, n) — clears n bits
• bitmap_test_bit(map, bit) — tests one bit
• for_each_set_bit(bit, addr, size) — elegant iterator macro
• bitmap_weight(map, size) — count of set bits

The cpumask_t type wraps a bitmap and has its own iterator: for_each_cpu(cpu, mask). If you ever add or remove a CPU from an IPI target set, you are using this API.

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

#define BITS_PER_WORD  64
#define NWORDS(n)      (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)

typedef unsigned long bitmap_t;

static inline void bm_set(bitmap_t *bm, int i) {
    bm[i / BITS_PER_WORD] |= (1UL << (i % BITS_PER_WORD));
}
static inline void bm_clear(bitmap_t *bm, int i) {
    bm[i / BITS_PER_WORD] &= ~(1UL << (i % BITS_PER_WORD));
}
static inline int bm_test(const bitmap_t *bm, int i) {
    return (bm[i / BITS_PER_WORD] >> (i % BITS_PER_WORD)) & 1UL;
}

/* Find first set bit at or after 'start'; returns -1 if none */
static int bm_next_set(const bitmap_t *bm, int nbits, int start) {
    int nwords = NWORDS(nbits);
    for (int w = start / BITS_PER_WORD; w < nwords; w++) {
        unsigned long word = bm[w];
        if (w == start / BITS_PER_WORD)
            word &= ~((1UL << (start % BITS_PER_WORD)) - 1UL);
        if (word) {
            int bit = w * BITS_PER_WORD + __builtin_ctzl(word);
            return bit < nbits ? bit : -1;
        }
    }
    return -1;
}

int main(void) {
    bitmap_t bm[NWORDS(128)];
    memset(bm, 0, sizeof(bm));

    bm_set(bm, 0);  bm_set(bm, 5);  bm_set(bm, 63);
    bm_set(bm, 64); bm_set(bm, 127);

    printf("Set bits: ");
    for (int b = bm_next_set(bm, 128, 0); b >= 0;
             b = bm_next_set(bm, 128, b + 1))
        printf("%d ", b);
    printf("\n");  /* 0 5 63 64 127 */
    return 0;
}

Endianness describes how a multi-byte integer is stored in memory. On a little-endian CPU (x86, x86-64, most modern ARM in LE mode), the least significant byte is stored at the lowest address. On a big-endian CPU (network byte order, older SPARC, PowerPC in BE mode), the most significant byte is stored first.

An analogy: consider the number 305,419,896 = 0x12345678. In memory:

• Little-endian (x86): address 0x00=0x78, 0x01=0x56, 0x02=0x34, 0x03=0x12
• Big-endian: address 0x00=0x12, 0x01=0x34, 0x02=0x56, 0x03=0x78

This only matters when you interpret raw bytes as a multi-byte integer — which happens constantly in network programming, file format parsing, and hardware register access. Bit manipulation adds a twist: on a little-endian CPU, if you cast a uint32_t to a uint8_t * and inspect the bytes, the physical bit layout in memory differs from the logical bit numbers. A BIT(0) (LSB) is in byte 0 on little-endian but byte 3 on big-endian.

The kernel's approach (in <linux/byteorder/generic.h> and <asm/byteorder.h>):

• cpu_to_be32(x) — convert from CPU native to big-endian (used before writing to a network header)
• be32_to_cpu(x) — convert from big-endian to CPU native (used after reading)
• cpu_to_le32(x), le32_to_cpu(x) — same for little-endian (used for PCI, USB, most on-disk formats)
• On x86, cpu_to_le32 is a no-op; cpu_to_be32 calls bswap32 or __builtin_bswap32.

Manual byte-swap when you need it:

uint32_t bswap32(uint32_t x) {
    return ((x & 0x000000FFu) << 24) |
           ((x & 0x0000FF00u) <<  8) |
           ((x & 0x00FF0000u) >>  8) |
           ((x & 0xFF000000u) >> 24);
}

GCC and Clang will often compile this to a single bswap instruction.

The golden rule: define your data structures with explicit-width types and mark them with __be32 or __le32 (kernel typedef'd to uint32_t but used as a documentation/sparse-checker annotation). Never dereference a raw pointer to a network/disk buffer as a native integer without a byte-order conversion.

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

/* Portable byte-swap (compiler usually optimises to bswap) */
static uint32_t bswap32(uint32_t x) {
    return ((x & 0x000000FFu) << 24) |
           ((x & 0x0000FF00u) <<  8) |
           ((x & 0x00FF0000u) >>  8) |
           ((x & 0xFF000000u) >> 24);
}

/* Simulate reading a 4-byte big-endian field from a packet */
static uint32_t read_be32(const uint8_t *p) {
    /* Always construct from bytes; never cast uint8_t* to uint32_t* */
    return ((uint32_t)p[0] << 24) |
           ((uint32_t)p[1] << 16) |
           ((uint32_t)p[2] <<  8) |
           ((uint32_t)p[3]      );
}

int main(void) {
    /* Detect endianness at runtime */
    uint32_t probe = 0x01020304u;
    uint8_t  first_byte;
    memcpy(&first_byte, &probe, 1);
    printf("This machine is %s-endian\n",
           first_byte == 0x04 ? "little" : "big");

    /* Byte-swap demo */
    uint32_t val = 0x12345678u;
    printf("0x%08X swapped = 0x%08X\n", val, bswap32(val));
    /* 0x12345678 swapped = 0x78563412 */

    /* Read a big-endian IPv4 src address from a raw header fragment */
    uint8_t pkt[] = { 0xC0, 0xA8, 0x01, 0x01 };  /* 192.168.1.1 */
    uint32_t ip = read_be32(pkt);
    printf("%u.%u.%u.%u\n",
           (ip>>24)&0xFF, (ip>>16)&0xFF, (ip>>8)&0xFF, ip&0xFF);
    /* 192.168.1.1 */
    return 0;
}

The Linux kernel provides a rich, architecture-optimized set of bit manipulation functions in <linux/bitops.h>, <linux/bitmap.h>, and the architecture-specific <asm/bitops.h>. Understanding this API is directly useful for kernel contribution.

Atomic bit operations (SMP-safe, operate on unsigned long *):

• set_bit(nr, addr) — atomically sets bit nr; uses lock; bts on x86
• clear_bit(nr, addr) — atomically clears bit nr
• change_bit(nr, addr) — atomically toggles bit nr
• test_bit(nr, addr) — reads bit nr (not atomic by itself, but ordering is provided by surrounding barriers)
• test_and_set_bit(nr, addr) — atomic test-then-set, returns old value; used for spinlocks and page flags
• test_and_clear_bit(nr, addr) — atomic test-then-clear

Non-atomic variants (when you hold a lock or only one CPU touches the word):

• __set_bit(nr, addr), __clear_bit(nr, addr), __change_bit(nr, addr), __test_and_set_bit(nr, addr)
• These are significantly faster — no memory lock prefix.

Bit-search operations (find first/next/last set or clear bit in a bitmap):

• find_first_bit(addr, size) — position of first 1 bit
• find_first_zero_bit(addr, size) — position of first 0 bit
• find_next_bit(addr, size, offset) — first 1 at or after offset
• find_last_bit(addr, size) — position of last 1 bit
• These are used heavily in the scheduler (cpumask), memory allocator (buddy bitmaps), and IRQ subsystem.

Word-level helpers:

• hweight32(x), hweight64(x) — Hamming weight (population count); maps to popcnt on CPUs that support it
• ffs(x) — find first set bit (1-indexed, 0 if no bit set); wraps __builtin_ffs
• fls(x) — find last set bit (1-indexed); used to compute order of magnitude
• rol32(x, n), ror32(x, n) — rotate left/right; important in cryptography and hash functions

Iteration macros (from <linux/bitmap.h>):

for_each_set_bit(bit, addr, size) { /* ... */ }
for_each_clear_bit(bit, addr, size) { /* ... */ }

These expand to a loop using find_next_bit internally and are used throughout the kernel wherever you need to iterate over e.g. online CPUs, allocated IRQs, or dirty pages in a batch.

/* Kernel-style code (would be inside a kernel module or driver) */
/* Headers: <linux/bitops.h>, <linux/bitmap.h>, <linux/cpumask.h> */

/*
 * Example 1: page flags (simplified from include/linux/page-flags.h)
 * PG_locked is bit 0 of page->flags (an unsigned long).
 */
#define PG_locked  0
#define PG_dirty   4

void lock_page_example(struct page *page) {
    /* Atomically set the locked bit; another CPU may be racing */
    while (test_and_set_bit(PG_locked, &page->flags))
        cpu_relax();  /* spin until we win the race */
}

void mark_page_dirty(struct page *page) {
    /* Non-atomic OK here if called under page lock */
    __set_bit(PG_dirty, &page->flags);
}

/*
 * Example 2: iterate over online CPUs
 * for_each_online_cpu wraps for_each_cpu(cpu, cpu_online_mask)
 * which uses find_next_bit internally.
 */
void send_ipi_to_all(void) {
    int cpu;
    for_each_online_cpu(cpu) {
        send_ipi(cpu, IPI_RESCHEDULE);
    }
}

/*
 * Example 3: allocate a free slot from a bitmap
 */
#define MAX_SLOTS  256
DECLARE_BITMAP(slot_bitmap, MAX_SLOTS);  /* static, zero-initialized */

int alloc_slot(void) {
    int bit = find_first_zero_bit(slot_bitmap, MAX_SLOTS);
    if (bit >= MAX_SLOTS)
        return -ENOSPC;
    set_bit(bit, slot_bitmap);
    return bit;
}
void free_slot(int bit) {
    clear_bit(bit, slot_bitmap);
}