Bits & Bytes

A value and its byte representation are not the same thing

An integer is a value; width and byte order describe a representation. Do not assume that a byte stream is a properly aligned native integer object. Reconstructing from unsigned bytes makes the format explicit and avoids depending on host endianness.

Big-endian [0x01,0x00] is 256; little-endian interpretation gives 1. For a two-byte unsigned field, value=(first×256)+second. A cast to a uint16_t pointer does not convert byte order.

What changes if a field is signed?

Decode the specified width and signed representation deliberately; identify its range and sign-extension rule. Do not assume a host cast repairs byte order, alignment, object access rules or signed-format differences.

Masks isolate a field; shifts move it

AND selects positions, OR sets positions and XOR toggles positions. To replace a field, clear its mask first and then insert a masked new value. Use unsigned operands for bit manipulation and ensure the shift count is smaller than the promoted operand width.

For a four-bit field at bits 7..4, mask=0xF0. Replacing it in 0xA5 with 3 gives (0xA5 & ~0xF0) | (3 << 4) = 0x35 within the intended width. The low nibble 5 survives.

Why is x & (x−1) useful, and what input needs special care when testing a power of two?

For nonzero unsigned x, it clears the lowest set bit. A power of two has exactly one set bit, so the result is zero. Zero also produces zero for that expression and must be excluded explicitly.

Hardware registers are not ordinary RAM

A correct RAM bit-field update can still be wrong for a peripheral register. Some bits are write-one-to-clear, read-sensitive or updated by hardware. Read-modify-write can acknowledge a status unintentionally or lose a concurrent update. The register contract is supplied by the hardware documentation.

If a status register reads 0b0011 and writing 1 clears a flag, writing the same value back clears both flags. “Preserve existing bits” has the opposite effect from ordinary storage.

Does volatile make a read-modify-write atomic?

No. It affects observable accesses but does not make a sequence indivisible or establish inter-thread synchronisation. Use the peripheral’s set/clear mechanism or a target-appropriate synchronisation design.

Read and change a field of bits

An unsigned integer is a row of bits. A mask selects the positions an operation may change.

Suppose an eight-bit configuration value is 10110010. Bits 3 and 2 hold a mode, and we want that mode to become binary 01. Replacing the whole byte with 01 would clear unrelated enable bits.

First construct 00001100, the mask for positions 3 and 2. AND with its complement clears only those positions: 10110010 becomes 10110010 in this case because both selected bits were already zero. Shift 01 left by two to get 00000100; OR it into the cleared value to obtain 10110110.

The same discipline helps decode bytes from a wire. Bytes 0x12 and 0x34 in big-endian order represent 0x1234: multiply the first by 256 and add the second. Load bytes individually so the explanation does not depend on native alignment or byte order.

Follow the worked example

• Old register: 0xB2 = 10110010.
• Field mask: 3 shifted left by 2 = 0x0C.
• Clear selected positions: 0xB2 & ~0x0C = 0xB2 within eight bits.
• Insert mode 1: 0xB2 | 0x04 = 0xB6. All other positions remain unchanged.

Connect the steps to code

#include <stdint.h>
uint32_t set_mode(uint32_t reg, uint32_t mode) {
    const uint32_t mask = UINT32_C(3) << 2;
    return (reg & ~mask) | ((mode & 3u) << 2);
}

• The mask contains exactly the two mode bits.
• mode & 3u keeps only the two bits accepted by this example; larger modes are truncated.
• The fixed shift of two is valid for uint32_t. A general field helper must also check the requested width and shift.

Check your understanding

What would OR-ing the new mode without clearing the field fail to do?

It could set bits but could not clear old one-bits, so changing mode 3 to mode 1 would leave mode 3.

Use Trace on the field-update exercise, then move to Arrays & Windows.

Easy - Update a Register Field

Every peripheral driver you will ever write. Configuring a UART's baud divisor, a timer's prescaler or a GPIO's mode is a read-modify-write of one field inside a shared register.

Replace a bit-field [lsb, lsb+width) in a 32-bit register without changing any other bit. Handle width 32 without undefined shifts.

Checked 32-bit field writer

Returns false for an invalid field. On success, changes only [lsb,lsb+width) and masks value to width.

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

bool field_write(uint32_t reg, uint8_t lsb, uint8_t width,
                 uint32_t value, uint32_t *out) {
    if (out == NULL || width == 0u || width > 32u ||
        lsb >= 32u || width > (uint8_t)(32u - lsb)) {
        return false;
    }
    uint32_t low_mask = width == 32u
        ? UINT32_MAX
        : ((UINT32_C(1) << width) - UINT32_C(1));
    uint32_t mask = low_mask << lsb;
    *out = (reg & ~mask) | ((value & low_mask) << lsb);
    return true;
}

• Validation makes every later shift count legal.
• The width==32 branch avoids shifting 1 by 32.
• Clear with reg & ~mask, then merge only masked input bits.

Cases the tests must cover

• width 1 at bit 0
• field spanning bit 31
• width 32 with lsb 0
• reject width 0 and lsb+width>32
• prove untouched bits remain equal

How it gets written wrong

• Do not return a sentinel uint32_t; every bit pattern is valid output.
• Use unsigned constants so shifts and complements have the intended width.

Easy - Reverse 32 Bits

Bit-order conversion between a peripheral and a wire format: SPI devices that clock LSB-first, CRC implementations with reflected input, and LCD or LED drivers that expect a mirrored byte.

Reverse every bit in a uint32_t using masks and shifts. Do not use a string, array, or compiler builtin.

Branch-free 32-bit reversal by divide and conquer

Returns value with its bit order reversed (bit 0 becomes bit 31). Pure function with no state, no tables, and no undefined shifts.

#include <stdint.h>

uint32_t reverse_bits(uint32_t value) {
    /* Stage 1: swap adjacent bits. 0x5 = 0101 keeps even bits,
       the shifted copy brings odd bits into even positions. */
    value = ((value & 0x55555555u) << 1) | ((value >> 1) & 0x55555555u);
    /* Stage 2: swap adjacent 2-bit groups. */
    value = ((value & 0x33333333u) << 2) | ((value >> 2) & 0x33333333u);
    /* Stage 3: swap adjacent nibbles (4-bit groups). */
    value = ((value & 0x0F0F0F0Fu) << 4) | ((value >> 4) & 0x0F0F0F0Fu);
    /* Stage 4: swap adjacent bytes. */
    value = ((value & 0x00FF00FFu) << 8) | ((value >> 8) & 0x00FF00FFu);
    /* Stage 5: swap the two 16-bit halves. */
    value = (value << 16) | (value >> 16);
    return value;
}

• Reversing 32 bits one at a time costs 32 loop iterations. The divide-and-conquer trick finishes in 5 straight-line steps with no branches, which pipelines beautifully on a Cortex-M.
• Each stage swaps neighbor groups whose size doubles: single bits, then pairs, then nibbles, then bytes, then half-words. After swapping 1-bit neighbors inside every pair, then pairs inside every nibble, and so on, the whole word is reversed.
• The mask picks the bits that stay in place for this stage; the shifted, re-masked copy brings the partner bits alongside them. OR-ing the two merges both halves of the swap.
• Every shift amount is a constant between 1 and 16, so there is no way to hit the undefined behavior of shifting by 32 or more.
• The final stage needs no mask: a plain 16-bit rotate of the word swaps the halves because the shifted-out bits fall off the unsigned type.

Cases the tests must cover

• reverse_bits(0x00000000u) == 0x00000000u
• reverse_bits(0xFFFFFFFFu) == 0xFFFFFFFFu
• reverse_bits(0x00000001u) == 0x80000000u (bit 0 lands on bit 31)
• reverse_bits(0x12345678u) == 0x1E6A2C48u
• reverse_bits(reverse_bits(x)) == x for several random x (involution property)

How it gets written wrong

• Writing the masks with the wrong hex digit count, e.g. 0x5555555 (28 bits) silently drops the top nibble.
• Forgetting the mask on the right-shifted half, which smears bits that were already placed into their neighbors.
• Using a loop that shifts by a variable amount up to 31 is fine, but shifting by 32 on a 32-bit type is undefined behavior.
• Doing this on a signed int makes the right shifts arithmetic and replicates the sign bit; always use uint32_t.

Easy - Streaming Parity

Any link with a parity bit - UART frames, memory with parity, smartcard protocols - computed one byte at a time as the bytes arrive in an interrupt.

Compute even parity while bytes arrive one at a time. The update function must be usable from an ISR and keep only one byte of state.

One-byte running parity for streaming bytes

Returns the updated even-parity accumulator after consuming byte. Callable from an ISR; keeps exactly one byte of state owned by the caller.

#include <stdint.h>

uint8_t parity_update(uint8_t parity, uint8_t byte) {
    /* XOR folds the byte into the accumulator: bit i of the result
       flips wherever byte has a 1, which is exactly how parity behaves. */
    parity ^= byte;
    /* Fold the 8 bits down to one: XOR the high nibble into the low,
       then keep collapsing until a single bit remains. */
    parity ^= (uint8_t)(parity >> 4);  /* bits 0-3 now hold XOR of pairs 4 apart */
    parity ^= (uint8_t)(parity >> 2);  /* bits 0-1 hold XOR of pairs 2 apart */
    parity ^= (uint8_t)(parity >> 1);  /* bit 0 is the XOR of everything */
    return (uint8_t)(parity & 0x01u);
}

• Even parity of a stream is just the XOR of every bit seen so far. XOR is associative and commutative, so you can fold a new byte into a one-byte accumulator and never re-read old data — ideal for an ISR that gets bytes one at a time.
• After parity ^= byte, the accumulator holds 8 partial parity bits. The shift-and-XOR ladder collapses them: each step halves the width while preserving the XOR of all bits in bit 0.
• The function is re-entrant and ISR-safe because it touches no global or static state; the caller keeps the single accumulator byte.
• Cost is three shifts and four XORs per byte — constant time, no loops, no tables, and no data-dependent branches, so interrupt latency stays deterministic.

Cases the tests must cover

• Feeding 0x00 into parity 0 returns 0
• Feeding 0xFF into parity 0 returns 0 (eight 1-bits is even)
• Feeding 0x01 into parity 0 returns 1
• Parity of a multi-byte stream equals parity of all bytes XORed together
• Interleaved streams with separate accumulators stay independent

How it gets written wrong

• Returning the accumulator before folding it down — the caller expects a single 0/1 bit, not the 8-bit partial XOR.
• Keeping the accumulator in a global inside the function, which breaks re-entrancy when two protocols use it concurrently.
• Using a per-bit loop; it works but costs 8 iterations plus branches where 6 instructions suffice.

Easy - Portable Packet Decode

Decoding every network and sensor packet that arrives as a byte array: Modbus registers, IP headers, I2C sensors that publish 16-bit results big-endian.

Read an unsigned 16-bit and 32-bit big-endian value from an unaligned byte buffer without pointer casts or alignment assumptions.

Alignment-safe big-endian reader

Reads width bytes (1..4) from buf as a big-endian unsigned value. Returns 0 for NULL buf or width outside 1..4. No pointer casts, no alignment assumptions, host-endianness independent.

#include <stddef.h>
#include <stdint.h>

uint32_t read_be(const uint8_t *buf, uint8_t width) {
    if (buf == NULL || width == 0u || width > 4u) {
        return 0u;  /* defensive: callers on error paths get a neutral value */
    }
    uint32_t value = 0u;
    for (uint8_t i = 0u; i < width; i++) {
        /* Shift the accumulator up by one byte, then drop the next
           (most significant remaining) byte into the low 8 bits. */
        value = (value << 8) | (uint32_t)buf[i];
    }
    return value;
}

• Big-endian means the first byte in the buffer is the most significant. The loop models exactly that: each iteration makes room for 8 more bits and ORs the next byte into the bottom.
• Reading byte-by-byte through uint8_t is the only fully portable approach. Casting buf to uint16_t* or uint32_t* can fault on strict-alignment cores (Cortex-M0 with unaligned access disabled) and breaks the strict aliasing rule.
• Because the value is assembled from bytes, the result is identical on little-endian ARM, big-endian MIPS, or x86 — that is the whole point of a wire-format decoder.
• width is validated before the loop so a corrupted header claiming width 200 cannot run the shift count past the 32-bit accumulator.

Cases the tests must cover

• {0x12,0x34}, width 2 → 0x1234
• {0xDE,0xAD,0xBE,0xEF}, width 4 → 0xDEADBEEF
• {0x7F}, width 1 → 0x7F
• width 0 and width 5 both return 0 without touching buf
• Run on a buffer at an odd address — must still work (alignment independence)

How it gets written wrong

• Casting to uint32_t* and byte-swapping afterwards: fast on x86, but it faults on unaligned addresses and is endian-dependent.
• Shifting buf[i] by 24 when buf[i] promotes to signed int — always cast to uint32_t before shifting into the top byte.
• Trusting a width field from a received packet without bounding it to 4.

Medium - Next Power-of-Two Capacity

Sizing any ring buffer, hash table or DMA block whose index arithmetic uses a mask instead of a modulo.

Return the smallest power of two greater than or equal to n. Define behavior for zero and overflow explicitly.

Overflow-checked next power of two

Writes the smallest power of two >= n into *out and returns true. Returns false for n == 0 (undefined request), n > 2^31 (result would not fit), or NULL out. *out is untouched on failure.

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

bool next_pow2_u32(uint32_t n, uint32_t *out) {
    if (out == NULL || n == 0u || n > 0x80000000u) {
        return false;  /* 2^32 does not fit in uint32_t, and 0 has no capacity meaning */
    }
    if (n == 1u) {
        *out = 1u;
        return true;
    }
    n--;                    /* exact powers of two must map to themselves */
    n |= n >> 1;            /* smear the top set bit one position down */
    n |= n >> 2;            /* now 2 positions are filled below it */
    n |= n >> 4;            /* 4 */
    n |= n >> 8;            /* 8 */
    n |= n >> 16;           /* all 31 bits below the top set bit are now 1 */
    *out = n + 1u;          /* 0x000FFFFF + 1 = the next clean power of two */
    return true;
}

• Every power of two has exactly one set bit. The classic trick fills every bit below the highest set bit with 1s, then adds 1 to roll over into a single higher bit.
• The n-- first is what makes already-power-of-two inputs idempotent: without it, 8 would fill down to 15 and round up to 16 instead of staying 8.
• Each doubling step (1, 2, 4, 8, 16) doubles the run of 1s under the top bit, so 5 steps cover all 32 positions — that is where O(log W) comes from.
• n > 2^31 is rejected because the answer 2^32 cannot be represented; returning false with *out untouched lets the caller fail its allocation cleanly instead of wrapping to 0 and under-allocating a ring buffer.
• This is the standard sizing step before allocating a power-of-two ring buffer so index masking with (capacity - 1) works.

Cases the tests must cover

• next_pow2_u32(1) → 1, next_pow2_u32(2) → 2, next_pow2_u32(3) → 4
• next_pow2_u32(1000) → 1024
• next_pow2_u32(1024) → 1024 (exact powers map to themselves)
• next_pow2_u32(0x80000000u) → 0x80000000u (largest representable)
• next_pow2_u32(0x80000001u) and next_pow2_u32(0) both return false, *out unchanged

How it gets written wrong

• Forgetting n--, which rounds exact powers up to double their value.
• Using a loop like while (p < n) p <<= 1 with p starting at 1: on overflow p becomes 0 and the loop never terminates.
• Shifting 1u << 32 for the overflow check — undefined behavior; compare against 0x80000000u instead.
• Touching *out before all validation passes, leaving callers with a half-written result on error paths.

Easy - Count Set Bits

Counting ready tasks in a scheduler bitmask, counting set channels in a DMA status word, or Hamming-distance checks on a received code word.

Count the set bits in a uint32_t without a lookup table or compiler builtin. Iterate once per set bit, not once per bit position.

Kernighan popcount

Returns the number of set bits in a 32-bit word. Loops once per set bit; zero input returns zero.

#include <assert.h>
#include <stdint.h>

/* Brian Kernighan's trick: v & (v-1) clears the lowest set bit,
   so the loop runs once per 1-bit instead of once per position. */
uint8_t popcount32(uint32_t v)
{
    uint8_t n = 0U;
    while (v != 0U) {
        v &= v - 1U;
        ++n;
    }
    return n;
}

int main(void)
{
    assert(popcount32(0U) == 0U);
    assert(popcount32(1U) == 1U);
    assert(popcount32(0x80000000U) == 1U);
    assert(popcount32(0xA5A5A5A5U) == 16U);
    assert(popcount32(0xFFFFFFFFU) == 32U);
    return 0;
}

• v-1 flips the lowest set bit and every bit below it; ANDing removes exactly one 1-bit.
• Unsigned arithmetic makes v-1 defined even at v==0 (loop never executes).
• The count fits in uint8_t: a 32-bit word has at most 32 set bits.

Cases the tests must cover

• 0 returns 0
• single top bit 0x80000000
• alternating pattern A5A5A5A5 is 16
• all ones is 32
• dense pattern 0xF0F0F0F0 is 16

How it gets written wrong

• A per-bit loop costs 32 iterations even for sparse status words.
• Do not use __builtin_popcount in portable code paths without a fallback.

Easy - Lowest Set Bit and Trailing Zeros

Finding the highest-priority ready task from a bitmask, or the lowest free slot in a bitmap allocator, in constant time.

Isolate the lowest set bit of a word and count trailing zeros without division or builtins. Define the result for a zero input explicitly.

Lowest set bit and trailing-zero count

lowest_set_bit returns only the lowest 1-bit (0 for 0). count_trailing_zeros returns the word width for a zero input, per the stated contract.

#include <assert.h>
#include <stdint.h>

/* Two's complement: v & (0u - v) keeps exactly the lowest set bit. */
uint32_t lowest_set_bit(uint32_t v)
{
    return v & (0U - v);
}

uint8_t count_trailing_zeros(uint32_t v)
{
    uint8_t n = 0U;
    if (v == 0U) return 32U;   /* contract: no set bit -> word width */
    while ((v & 1U) == 0U) {
        v >>= 1;
        ++n;
    }
    return n;
}

int main(void)
{
    assert(lowest_set_bit(0x28U) == 0x08U);
    assert(lowest_set_bit(0U) == 0U);
    assert(count_trailing_zeros(0x28U) == 3U);
    assert(count_trailing_zeros(1U) == 0U);
    assert(count_trailing_zeros(0U) == 32U);
    assert(count_trailing_zeros(0x80000000U) == 31U);
    return 0;
}

• 0U - v is unsigned negation: defined modulo 2^32, no signed-negation UB.
• The zero case must be in the contract; CLZ-style intrinsics are undefined there too.
• The shift loop is bounded by the word width: at most 31 iterations for nonzero input.

Cases the tests must cover

• 0x28 -> lowest 0x08, 3 trailing zeros
• 1 -> 0 trailing zeros
• 0 -> 32 per contract
• top bit only -> 31
• all ones -> 0 trailing zeros

How it gets written wrong

• -v on a signed int is UB at INT_MIN; stay unsigned.
• ctz(v)==0 does not mean v==1; it means the lowest bit is set.

More in Embedded DSA

• Sorting Under ConstraintLearn nine sorting algorithms with record-by-record traces: insertion, selection, bubble, Shell, merge, quick, heap, counting and radix. Compare stability, temporary storage and input-dependent work, then solve the C11 firmware exercises.
• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Lists, Pools & ArenasFollow packet storage through allocation, use and release. Compare fixed-block pools, linked lists and arenas, including exhaustion, lifetime and allocation trade-offs.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• Heaps & SchedulingInsert and remove deadlines in a binary min-heap, then study scheduling and wrapping tick counters. Heaps and timer wheels are different timer-management structures.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.