Bit Manipulation Questions

Answer (concise, step-by-step)

Definition / formula
For Cortex-M SRAM bit-band (bit-band region base 0x2000_0000, alias base 0x2200_0000) the alias address for bit at byte address addr and bit number bit (0..7) is:

alias = 0x22000000 + ((addr - 0x20000000) * 32) + (bit * 4)

Plain English: each byte in bit-band region maps to 32 bytes in alias region (one word per bit); each bit maps to a 4-byte word whose LSB write sets/clears the bit.

Example: addr = 0x2000A000, bit = 5

1. Compute byte offset from bit-band base:
   offset = addr - 0x20000000 = 0x2000A000 - 0x20000000 = 0x0000A000

2. Multiply offset by 32:
   offset * 32 = 0xA000 * 32 = 0xA000 * 0x20 = 0x140000

3. Compute bit contribution:
   bit * 4 = 5 * 4 = 20 = 0x14

4. Add alias base:
   alias = 0x22000000 + 0x140000 + 0x14 = 0x22140014

Answer: alias address = 0x22140014

You can access it in C as:

volatile uint32_t *bit_alias = (uint32_t *)0x22140014;
*bit_alias = 1; // set bit
*bit_alias = 0; // clear bit

How C bitfields work (brief)

A bitfield declares integer members using a width:

struct { unsigned a:3; unsigned b:5; };

The compiler packs members into one or more implementation-defined storage units (usually underlying int), assigning each field the specified number of bits. Accessors read/write only those bits with generated masks/shift code.

Advantages for hardware registers

• Concise, readable mapping of named fields to bit widths
• Compiler generates masking/shift code for you
• Good for quick prototypes or documentation

Disadvantages / gotchas (important for firmware)

• Portability: ordering of bitfields within storage (LSB-first vs MSB-first) is implementation-defined; different compilers/ABIs may pack differently.
• Packing/alignment: padding between fields or across storage-unit boundaries varies.
• Width of underlying unit: signedness and unit size (int vs unsigned int) are implementation-defined.
• Volatile semantics: declaring struct volatile affects whole object, but compilers may still optimize reads/writes differently for bit accesses — read-modify-write sequences might be generated unexpectedly.
• Atomicity: accesses are not atomic; writing one bitfield may read-modify-write the containing word, causing race or side effects (important for hardware where writing certain bits clears flags).
• Debugging: debuggers may show whole storage word, making bit-level state less obvious; compiler-generated code can be non-obvious in disassembly.

Safer portable alternative
Use explicit masks and inline accessors around integer types placed at exact addresses:

#define REG (*(volatile uint32_t*)0x40010000U)
static inline uint32_t reg_get_a(void){ return (REG >> 0) & 0x7; }   // 3 bits
static inline void     reg_set_a(uint32_t v){ REG = (REG & ~0x7U) | (v & 0x7U); }

• Use volatile on the base integer to ensure ordered accesses.
• For fields that must be changed without affecting others or need atomicity, use read/modify/write with interrupt masking or hardware-supported atomic bit-set/clear registers.
• Document endianness and hardware behavior; add static asserts for register size.

This approach is explicit, portable, debuggable, and avoids compiler-specific bitfield packing pitfalls.

Approach (O(log W) using binary search on bit groups)

Use successive shifts/masks to test half-word, quarter-word, etc., adding offsets when higher/lower groups are zero. This takes O(log W) steps (W=32).

Code (portable C, returns 32 for x==0):

#include <stdint.h>

int count_leading_zeros32(uint32_t x) {
    if (x == 0) return 32;
    int n = 0;
    if ((x >> 16) == 0) { n += 16; x <<= 16; }
    if ((x >> 24) == 0) { n += 8;  x <<= 8; }
    if ((x >> 28) == 0) { n += 4;  x <<= 4; }
    if ((x >> 30) == 0) { n += 2;  x <<= 2; }
    if ((x >> 31) == 0) { n += 1; }
    return n;
}

int count_trailing_zeros32(uint32_t x) {
    if (x == 0) return 32;
    int n = 0;
    if ((x & 0xFFFF) == 0) { n += 16; x >>= 16; }
    if ((x & 0xFF) == 0)   { n += 8;  x >>= 8; }
    if ((x & 0xF) == 0)    { n += 4;  x >>= 4; }
    if ((x & 0x3) == 0)    { n += 2;  x >>= 2; }
    if ((x & 0x1) == 0)    { n += 1; }
    return n;
}

Explanation

• Each step halves the search space (16, 8, 4, 2, 1), so complexity is O(log W) = O(5) constant steps for 32-bit.
• Shifts and masks are cheap and portable for embedded targets without intrinsics.

de Bruijn trick for CTZ (brief)

• Multiply (x & -x) — isolates lowest set bit — by a 32-bit de Bruijn constant, then shift to form an index into a 32-entry table mapping bit patterns to trailing-zero counts.
• It yields CTZ in one multiply, one shift, and one table lookup — faster but requires the lookup table and careful constant selection. Common constant: 0x077CB531U and table of 32 indices. Good for performance-critical embedded code where multiplication cost + table fits constraints.

When is it safe

• Safe for unsigned integers where you want arithmetic mod 2^N behavior: replacing x * 2^k with x << k and x / 2^k with x >> k (logical for unsigned) is well-defined if shift count < width.

Why signed is tricky

• Right shift of signed negatives is implementation-defined (arithmetic vs logical).
• Left shifting signed values that would set or move the sign bit causes UB/overflow.

Incorrect examples

• Signed negative: -1 >> 1 may stay -1 (arithmetic) or become implementation-dependent.
• Overflow: int x = 1 << 31; // UB on 32-bit int if sign bit becomes set
• Division rounding: x / 4 vs x >> 2 for negative x differ (C truncates toward 0; arithmetic shift rounds toward -inf).

Safe idioms (embedded focus)

• Use unsigned types for bit shifts:

uint32_t y = x_u << 3;        // multiply by 8, safe if no meaningful overflow
uint32_t z = x_u >> 2;        // divide by 4, logical shift

• For signed divide by power-of-two with C semantics (round toward 0):

int32_t div_pow2(int32_t v, unsigned k){
    int32_t sign = v >> 31;
    return (v + (sign & ((1 << k) - 1))) >> k;
}

• Or use compiler intrinsics/optimizations and enable -O2; prefer clarity unless measurement shows shift wins.

Guidelines

• Prefer unsigned for bit ops, check shift < width, avoid shifting into sign bit, test edge cases on target MCU, and rely on compiler warnings for UB.

Approach
Use a small integer whose lowest-address byte can be inspected. This avoids compiler macros and relies on runtime memory layout.

#include <stdint.h>

/* Return 1 if little-endian, 0 if big-endian */
int is_little_endian(void)
{
    uint16_t x = 0x0102;
    /* Inspect the first byte in memory */
    uint8_t *b = (uint8_t *)&x;
    return (b[0] == 0x02);
}

Why this works

• On little-endian, low-order byte (0x02) is at the lowest address -> b[0] == 0x02.
• On big-endian, high-order byte (0x01) is first -> b[0] == 0x01.

Embedded implications

• Register maps and wire protocols specify byte order. If CPU endianness differs from peripheral/wire format, you must byte-swap when reading/writing multi-byte registers.
• Use volatile pointers for MMIO and be careful with unaligned accesses on architectures that fault.
• Prefer memcpy or explicit byte operations (or builtins like __builtin_bswap32) rather than direct type-punning where alignment or atomicity matters.
• Incorrect handling leads to corrupted values, wrong checksums, and subtle bugs in comms or sensor data.