Bitwise Operations and Bit Manipulation Questions

Covers working with binary representations of integers and performing fundamental bitwise operations including and, or, xor, not, and left and right shifts. Includes techniques for testing setting clearing and toggling individual bits, creating and applying masks, and using bit fields and bit packed structures for compact storage. Addresses endianness and byte order considerations, bit level register manipulation for hardware and embedded systems, and efficient bit algorithms such as population count parity leading and trailing zero detection and sign extension. Encompasses practical uses in protocol parsing flag management performance optimizations and cryptographic primitives including substitution and diffusion concepts. Candidates may be assessed with coding problems that require bit tricks and algorithmic reasoning as well as design questions about data layout and low level interfaces.

HardTechnical

53 practiced

A shared MMIO register controls GPIO and multiple CPU cores may update different bits concurrently. Read-modify-write races cause lost updates. Propose hardware and software strategies to ensure correct concurrent bit updates with minimal latency. Discuss hardware SET/CLR registers, LL/SC or CAS approaches, spinlocks, and compare trade-offs (latency, power, complexity). Provide example pseudo-code for a CAS-based bit-update loop.

Sample Answer

**Approach summary**When multiple cores update different bits in one MMIO GPIO register, avoid RMW races by using either hardware bit-set/clear, atomic read-modify primitives (LL/SC or CAS), or software locks. Aim for minimal latency and low power.

**Hardware solutions**- Dedicated SET and CLR MMIO registers (preferred): write-only registers that set or clear bits atomically without reading. Lowest latency, no bus read, minimal contention.- BUS/atomic MMIO support: devices that implement atomic bit ops on the bus.

**Software/CPU primitives**- LL/SC (load-linked / store-conditional): efficient on architectures that support it; retries only on conflicting stores.- CAS loop (compare-and-swap) over a mapped register: works where reads are coherent and device accepts RMW over PCI/MMIO (beware side effects).

**Spinlocks**- Simple, deterministic, but high latency and power (busy-wait), and hurt real-time behavior. Use only if hardware atomic ops unavailable and contention low.

**Trade-offs**- Latency: SET/CLR < LL/SC/CAS < spinlock.- Power: SET/CLR minimal; spinlock worst.- Complexity: SET/CLR simplest API; LL/SC/CAS medium; locks simplest conceptually but add OS integration and priority inversion concerns.

**CAS-based pseudo-code (C-like)**

// atomic MMIO CAS loop: assumes mmio_read/mmio_cas provided by platform
uint32_t update_gpio_bits(uint32_t mmio_addr, uint32_t set_mask, uint32_t clr_mask) {
    uint32_t old, desired;
    do {
        old = mmio_read(mmio_addr);                // read current register
        desired = (old | set_mask) & ~clr_mask;   // compute desired value
    } while (!mmio_cas(mmio_addr, old, desired)); // retry if changed
    return old;
}

Use SET/CLR registers when available. Otherwise prefer LL/SC/CAS for low-latency atomic updates; fall back to locks only when necessary.

HardTechnical

58 practiced

A peripheral's 32-bit control register has: bits [0..7] writable, [8..15] read-only status, [16..23] reserved (must be written as 0), and [24..31] write-only command bits. Multiple threads and ISRs update the writable bits concurrently. Design robust, portable C code to set/clear specific writable bits without modifying RO/reserved fields, minimizing race windows. Explain testing strategy on hardware to validate correctness and race freedom.

Sample Answer

**Approach (brief)** We must modify only writable bits [0..7], preserve read-only bits [8..15], write zeros to reserved [16..23], and avoid changing write-only command bits [24..31]. Use an atomic read-modify-write on the full 32-bit MMIO so no other agent races us. Prefer hardware atomic primitives (exclusive load/store or compiler atomics). If unavailable, protect the minimal window with IRQ-disable for ISR-safety and a mutex for threads.

**Code (portable, with fallbacks)**

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

#define REG_ADDR   ((volatile uint32_t*)0x40001000U)
#define WR_MASK    0x000000FFu      /* bits 0..7 writable */
#define RO_MASK    0x0000FF00u      /* bits 8..15 read-only */
#define RESERVED_MASK 0x00FF0000u   /* must write 0 */
#define CMD_MASK   0xFF000000u      /* write-only, must preserve as 0 in RMW */

static inline void cpu_disable_irq(void);
static inline void cpu_enable_irq(void);

/* Set and/or clear bits specified by set_mask and clear_mask (non-overlapping).
   Returns true on success. */
bool reg_update_bits(uint32_t set_mask, uint32_t clear_mask)
{
    volatile uint32_t *r = REG_ADDR;
    set_mask &= WR_MASK;
    clear_mask &= WR_MASK;
    if (set_mask & clear_mask) return false;

#if defined(HAS_ATOMIC_CAS_FOR_MMIO)
    /* Prefer an atomic CAS loop if MMIO supports it */
    uint32_t oldv, newv;
    do {
        oldv = *r;                       /* read full register */
        /* preserve RO bits, zero reserved and cmd bits */
        newv = (oldv & RO_MASK)          /* keep RO */
               & ~RESERVED_MASK;         /* ensure reserved cleared (redundant) */
        /* apply writable changes */
        newv &= ~clear_mask;
        newv |= set_mask;
        /* ensure reserved and cmd bits are zero in the write */
        newv &= ~(RESERVED_MASK | CMD_MASK);
    } while (!atomic_compare_exchange_mmio(r, &oldv, newv));
    return true;
#else
    /* Fallback: briefly disable interrupts to prevent ISR races.
       Thread-level races must be protected by a mutex outside this function. */
    cpu_disable_irq();
    uint32_t v = *r;
    uint32_t out = (v & RO_MASK);
    out &= ~clear_mask;
    out |= set_mask;
    out &= ~(RESERVED_MASK | CMD_MASK); /* ensure zeros */
    *r = out;
    cpu_enable_irq();
    return true;
#endif
}

Notes:- atomic_compare_exchange_mmio is a platform helper that uses LDREX/STREX or equivalent; use compiler intrinsics if available.- Do not rely on reading CMD bits (write-only). Always write zero to CMD_MASK to avoid firing commands.- Keep IRQ-disabled window minimal (single read-modify-write).

Testing strategy on hardware- Unit tests in simulator to validate mask logic.- Concurrency stress: two threads and an ISR repeatedly flip different writable bits; verify using a shadow model in RAM that serializes same operations and compare final states.- Observe bus: attach logic analyzer / trace on the MMIO address to confirm every write has cmd/reserved bits zero and RO bits unchanged.- Fault injection: introduce synthetic delays between read and write to stress races (if using CAS, force CAS failures).- Long-run soak test under highest interrupt load; check for lost updates.- Add hardware readback where possible: after each update, read RO bits to ensure unchanged; verify no unintended command writes by monitoring side-effects that commands would trigger.

MediumSystem Design

57 practiced

A 12-byte telemetry packet must pack many variable-length fields bitwise to minimize airtime. As an embedded developer, propose a portable bit-field layout and parsing/writing strategy that addresses alignment, endianness, future extension (versioning), and error detection. Provide pseudocode or an outline of your parser and how you would test it across big/little-endian hosts.

Sample Answer

**Approach summary**Use a byte-array canonical on-wire format and implement portable bit-level pack/unpack routines rather than C compiler bitfields. Reserve a version and flags field, include a CRC8 for error detection, and allow optional extension blocks. Handle endianness by reading/writing bits in a defined MSB-first or LSB-first order.

**Packet layout (12 bytes = 96 bits) — example**- byte 0: [ version:3 | flags:5 ]- bits 8..31: fieldA:24- bits 32..47: fieldB:16- bits 48..71: fieldC:24- bits 72..87: fieldD:16- bits 88..95: checksum:8 (CRC-8 of bytes 0..10)

This is MSB-first within each byte (network order).

**Why not compiler bitfields**- Compiler-dependent packing/endianness/ordering. Portable code should manipulate bytes and bits explicitly.

**Parsing/writing pseudocode (C-style)**

// read bitfield helper (MSB-first within bytes)
uint64_t read_bits(const uint8_t *buf, int bit_offset, int bit_len) {
    uint64_t v = 0;
    for (int i = 0; i < bit_len; ++i) {
        int b = bit_offset + i;
        uint8_t byte = buf[b / 8];
        int bit_in_byte = 7 - (b % 8); // MSB-first
        v = (v << 1) | ((byte >> bit_in_byte) & 1);
    }
    return v;
}

void write_bits(uint8_t *buf, int bit_offset, int bit_len, uint64_t value) {
    for (int i = bit_len - 1; i >= 0; --i) {
        int b = bit_offset + (bit_len - 1 - i);
        uint8_t *byte = &buf[b / 8];
        int bit_in_byte = 7 - (b % 8);
        uint8_t bit = (value >> i) & 1;
        *byte = (*byte & ~(1 << bit_in_byte)) | (bit << bit_in_byte);
    }
}

**High-level parser**- Verify packet length == 12- Compute CRC-8 over bytes 0..10, compare to checksum at byte 11- Extract version = read_bits(buf, 0, 3)- Switch on version; for unknown higher version return controlled error (or attempt best-effort)- Extract fields via read_bits()- Validate ranges and flags

**Versioning & extensibility**- 3-bit version allows evolving format. New fields appended into reserved flag space or new extension region flagged by flags bits. Receiver ignores unknown optional extensions.

**Error detection**- Use CRC-8 (polynomial e.g., 0x07) in last byte. Also include sanity checks (range, reserved bits zero).

**Testing strategy (big/little-endian)**- Unit tests use reference vectors: construct packet via write_bits on a known-endian host, compare against known good hex string.- Cross-build and run tests on both little-endian and big-endian boards (or QEMU for big-endian sim).- Property tests: randomize fields, pack then unpack and assert equality; also flip single bits and assert CRC catches errors.- Fuzz tests: malformed lengths, corrupted checksum, version mismatch.- CI: include tests running in a deterministic emulator for both endiannesses and check reference CRC and fields.

**Trade-offs**- Bit-wise helpers cost a few cycles but are small and portable. If performance critical, offer optimized versions for common platforms using aligned reads with explicit byte-order conversions.

EasyTechnical

75 practiced

You have a volatile 32-bit STATUS_REG that holds device flags. Implement a function void toggle_flags(volatile uint32_t *reg, uint32_t mask) that toggles bits specified by mask without touching reserved bits. Assume mask contains only writable bits. Provide a safe approach for single-core scenario where both main code and ISR may call toggle_flags.

Sample Answer

**Approach (brief)**Use an atomic read-modify-write: read register, XOR with mask, write back. In a single-core system where ISRs may preempt, protect the RMW with a critical section (disable/restore interrupts). Assume mask already contains only writable bits.

**Implementation**

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

void toggle_flags(volatile uint32_t *reg, uint32_t mask)
{
    uint32_t primask;
    uint32_t val;

    /* Save and disable interrupts (platform-specific) */
    primask = __disable_irq();    /* example CMSIS call; replace as needed */

    val = *reg;                   /* read volatile */
    val ^= mask;                  /* toggle writable bits only */
    *reg = val;                   /* write back */

    /* Restore interrupts */
    __restore_irq(primask);       /* platform-specific restore */
}

**Why**- Disabling interrupts prevents concurrent ISR RMW races on single-core hardware.- Using XOR toggles only bits in mask; reserved bits remain unchanged since mask excludes them.- volatile ensures actual memory access.

**Edge cases & notes**- Keep critical section minimal and fast.- Use platform-specific functions to save/restore interrupt state rather than unconditionally enabling.- If ISR must also call toggle_flags, ensure it obeys same convention.

MediumTechnical

60 practiced

On a single-core ARM Cortex-M MCU, both main thread and an ISR need to set and clear individual bits in a shared 32-bit MMIO control register. Describe three safe approaches to perform these bit manipulations atomically and list pros/cons for each (interrupt-disable RMW, bit-banding, dedicated SET/CLR registers). Provide short pseudo-code or code snippets for each approach.

Sample Answer

**Approach 1 — Disable interrupts around read-modify-write (RMW)**- Idea: In main thread disable IRQs, perform read/modify/write, re-enable. ISR cannot interrupt while IRQs are masked.- Pros: Simple, works on any Cortex-M; minimal hardware support.- Cons: Blocks all interrupts (latency), must be short and careful with nesting/priority.

// C pseudo-code
uint32_t reg = MMIO_REG;
reg |= (1u << bit);       // set bit
MMIO_REG = reg;

Wrap with:

uint32_t primask = __get_PRIMASK();
__disable_irq();
... // RMW
if (!primask) __enable_irq();

**Approach 2 — Bit-banding (alias region)**- Idea: Use Cortex-M bit-band alias to map each bit to a 32-bit word; atomic single-word access.- Pros: True atomic bit set/clear without disabling IRQs; fast.- Cons: Only on MCUs that expose bit-band (e.g., some Cortex-M3/M4); extra address computation.

// compute alias address then write 0 or 1
volatile uint32_t *alias = (BITBAND_ALIAS_BASE + ((MMIO_ADDR - PERIPH_BASE) * 32) + bit*4);
*alias = 1; // sets bit atomically

**Approach 3 — Dedicated SET/CLR MMIO registers**- Idea: Many peripherals expose separate SET and CLEAR registers: write 1s to affect bits.- Pros: Hardware atomic, very efficient, no IRQ masking.- Cons: Requires peripheral support; different registers consume address space.

MMIO_REG_SET = (1u << bit);   // sets bit atomically
MMIO_REG_CLR = (1u << bit);   // clears bit atomically

Recommendation: Prefer dedicated SET/CLR or bit-banding when available for lowest latency and safest concurrency; use IRQ masking only for very short critical updates when hardware support is absent.

Unlock Full Question Bank

Get access to hundreds of Bitwise Operations and Bit Manipulation interview questions and detailed answers.

Join thousands of developers preparing for their dream job.