Timed C Bit-Manipulation: Solving and Justifying Each Operation

Welcome back. In the last lesson, you solved a linked-list problem under a timer and had to justify each pointer change, including what happened to the removed node’s memory. Today the object you manipulate is a 32-bit word rather than a chain of nodes. The interview discipline is the same: define the contract, explain why each operation changes only what you intend, and check C’s boundary cases.

You’ll implement a bit-field update function in a 23-minute timed run, then audit it against C’s shift rules and test it on your Linux VM. Allow about 45–50 minutes in total. The example is a software-owned storage completion word; it is not a hardware register, where read-modify-write may have additional device-specific hazards.

From a single-bit mask to a field

Number the bits of a uint32_t from 0 at the least significant bit to 31 at the most significant bit. A mask with a one at bit 3 identifies just that position: OR with the mask sets it, AND with the mask’s complement clears it, and XOR with the mask toggles it. None of those operations should disturb positions where the mask is zero.

Watch Jacob Sorber’s How do I Set, Clear, and Toggle a Single Bit? for the reasoning behind those three choices. Focus on the bit-by-bit argument, not the shorthand syntax.

An interview problem often extends this idea to several adjacent bits. Suppose bits 8 through 15 contain a field. Replacing that field requires two distinct actions: clear its old value without clearing neighboring bits, then put the new value into those positions. Before coding, pay attention to one C-specific constraint: a shift count must be smaller than the width of its promoted left operand. In particular, constructing a 32-bit mask must not shift by 32. Use unsigned fixed-width values for the word and field so the intended bit pattern does not depend on shifting a negative signed value.

Your 23-minute interview run

Implement:

bool insert_field(uint32_t original, unsigned offset, unsigned width,
                  uint32_t field, uint32_t *result);

Treat original as a software-owned 32-bit word. Replace width bits beginning at bit offset with field, interpreted as an unshifted value. Return true and write the updated word to *result on success.

Return false without changing *result if the pointer is null, the width is zero, the field extends beyond bit 31, or field cannot fit in the requested width. A width of 32 is valid when the offset is zero. All bits outside the field must remain unchanged. Do not use compiler-specific bit-field structures or built-in bit operations.

Save this as field.c and replace only the placeholder function during your timed attempt:

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

static bool insert_field(uint32_t original, unsigned offset, unsigned width,
                         uint32_t field, uint32_t *result)
{
    /* Replace this placeholder. */
    (void)original;
    (void)offset;
    (void)width;
    (void)field;
    (void)result;
    return false;
}

static void check(uint32_t original, unsigned offset, unsigned width,
                  uint32_t field, uint32_t expected)
{
    uint32_t result = 0;
    assert(insert_field(original, offset, width, field, &result));
    assert(result == expected);
}

static void check_reject(uint32_t original, unsigned offset, unsigned width,
                         uint32_t field)
{
    uint32_t result = UINT32_C(0x13579bdf);
    assert(!insert_field(original, offset, width, field, &result));
    assert(result == UINT32_C(0x13579bdf));
}

int main(void)
{
    check(UINT32_C(0xa5a5a5a5), 8, 8, UINT32_C(0x3c),
          UINT32_C(0xa5a53ca5));
    check(UINT32_MAX, 0, 1, 0, UINT32_C(0xfffffffe));
    check(0, 31, 1, 1, UINT32_C(0x80000000));
    check(UINT32_C(0x12345678), 0, 32, UINT32_C(0xdeadbeef),
          UINT32_C(0xdeadbeef));
    check(UINT32_C(0xa5a5a5a5), 8, 8, UINT32_C(0xa5),
          UINT32_C(0xa5a5a5a5));

    check_reject(0, 0, 0, 0);
    check_reject(0, 32, 1, 0);
    check_reject(0, 31, 2, 0);
    check_reject(0, 1, 32, 0);
    check_reject(0, 0, 3, 8);
    assert(!insert_field(0, 0, 1, 0, NULL));

    puts("all field tests passed");
    return 0;
}

Use roughly three minutes to state the boundary cases, fifteen to implement and explain your mask construction, and five to compile and test. Run:

gcc -std=c11 -O0 -g -Wall -Wextra -Wpedantic \
  -fsanitize=undefined field.c -o field
./field

You can use Clang instead of GCC. As you code, justify the order of validation: no expression should evaluate an invalid shift before the function has decided to reject the input. Stop at 23 minutes, even if a test is still failing; the review below is part of the lesson.

Audit the C rules

Read the relevant parts of cppreference’s Arithmetic operators now. The page is a language reference rather than an interview solution: use it to check whether your reasoning describes C behavior, not merely the bit pattern you expect from a particular machine.

The central trap in this problem is not whether shifting moves bits. It is whether a particular expression is legal at the boundary. For example, a calculation that produces the correct mask for widths 1 through 31 may invoke undefined behavior when width is 32. Testing the full-width case is therefore part of testing the algorithm, not an obscure portability extra.

Reference solution and operation-by-operation explanation

Compare your attempt only after the timed run:

static bool insert_field(uint32_t original, unsigned offset, unsigned width,
                         uint32_t field, uint32_t *result)
{
    if (result == NULL || width == 0 || width > 32 ||
        offset >= 32 || width > 32 - offset)
        return false;

    uint32_t low_mask = UINT32_MAX >> (32 - width);
    if ((field & ~low_mask) != 0)
        return false;

    uint32_t placed_mask = low_mask << offset;
    *result = (original & ~placed_mask) | (field << offset);
    return true;
}

Here is the justification you should be able to give aloud:

1. Validate before shifting. The checks ensure a nonzero width no greater than 32 and a field wholly inside the word. The offset >= 32 check occurs before the 32 - offset test can be needed; || evaluates from left to right and short-circuits. A null output pointer is rejected before any write.
2. Construct an unshifted field mask. UINT32_MAX >> (32 - width) leaves width low-order ones. When width is 32, the shift count is zero, not 32. When width is 1, it leaves one low-order bit.
3. Reject a field that does not fit. ~low_mask identifies positions above the requested width. If field & ~low_mask is nonzero, placing the value would spill outside the field. Reject it rather than silently truncating it.
4. Move the mask into position. low_mask << offset identifies exactly the bits to replace. The validated offset and width keep this shift within the 32-bit word.
5. Clear, then insert. original & ~placed_mask preserves every bit outside the field and clears the field’s previous contents. field << offset places only the new field bits; OR combines them with the preserved bits. This is assignment of a value, not XOR toggling.

The two shifts in the successful path have different purposes: one creates a width-sized mask; the other positions a mask or value. Naming those purposes is more convincing than saying only that the code “does bit manipulation.” The function uses constant time and constant extra space for a fixed 32-bit word.

Run the instrumented build again after any correction. If all assertions pass, try explaining the full-width case without looking at the code: why does it replace the entire word, and why is no shift by 32 evaluated? The sanitizer can help catch undefined shift behavior on tested paths, but the validation argument is what covers all inputs allowed by the contract.

Key takeaways

For a timed C bit problem, establish the bit numbering, input validity, and behavior on failure before writing a mask. OR sets masked bits, AND with a complemented mask clears them, and XOR toggles them; replacing a multi-bit value requires clearing the old field and inserting a validated new one. Finally, prove that every shift count is valid, especially at the word-width boundary.

This completes the timed C interview-skills module. Next, you’ll carry the same implementation-and-explanation discipline into data-structure operations, beginning with hash-table lookup, insertion, and deletion.