Bit Manipulation Questions

The idea

Every one of the four operations is a one-bit mask plus one operator. Build the mask with 1u << k, which is a word that has a 1 only at position k (counted from the least significant bit, bit 0). Then:

A small worked example makes the four rows concrete. Take an 8-bit value v = 00101100 (0x2C, decimal 44) and work on bit 4, then bit 3, then bit 5:

Each row changes only the bit named by the mask; every other bit passes through unchanged. The 32-bit versions below do exactly the same thing with a wider word.

For several bits at once, use a multi-bit mask: v ^ 0xF flips four bits in one operation, and (v & ~mask) | (value & mask) replaces a whole field.

Out-of-range k

For a 32-bit word the valid values of k are 0 to 31. 1u << 32 is undefined behaviour in C (the standard places no requirement on what the program then does, so the compiler may produce any result, and -fsanitize=undefined reports it), so the check must happen before the shift, not after. The choice to make is what the function does when k is bad. The options are to silently mask k (k & 31, which quietly operates on the wrong bit), to assert (good while developing, absent in release builds), or to report an error. For a library function the safe choice is to report it: mutators return false and leave the value unchanged, and the test returns false. Declaring k unsigned also makes a negative argument wrap to a huge value that the same check rejects. If k is a compile-time constant, a static assertion (_Static_assert, a check the compiler performs while compiling) is better than a runtime check because the mistake cannot ship.

Code

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

#define WORD_BITS 32u

/* k is unsigned, so a negative argument becomes a huge value and is rejected too. */
static bool bit_test(uint32_t v, unsigned k) {
    return k < WORD_BITS && ((v >> k) & 1u) != 0;
}
static bool bit_set(uint32_t *v, unsigned k) {
    if (k >= WORD_BITS) return false;
    *v |= 1u << k;
    return true;
}
static bool bit_clear(uint32_t *v, unsigned k) {
    if (k >= WORD_BITS) return false;
    *v &= ~(1u << k);
    return true;
}
static bool bit_toggle(uint32_t *v, unsigned k) {
    if (k >= WORD_BITS) return false;
    *v ^= 1u << k;
    return true;
}
/* Several bits at once: flip every bit that is 1 in mask. */
static void bits_toggle_mask(uint32_t *v, uint32_t mask) { *v ^= mask; }

/* Replace a multi-bit field: clear it with the mask, then OR in the new value. */
static void field_write(uint32_t *v, uint32_t mask, uint32_t value) {
    *v = (*v & ~mask) | (value & mask);
}

/* Memory-mapped register where writing 1 to a bit clears it (write-one-to-clear),
   simulated here by a plain variable. */
static uint32_t sim_status = 0;
static void sim_write_w1c(uint32_t written) { sim_status &= ~written; }

int main(void) {
    uint32_t v = 0;
    bit_set(&v, 0);  bit_set(&v, 31);
    printf("set 0 and 31 : 0x%08x\n", v);
    printf("test 31, 30  : %d %d\n", bit_test(v, 31), bit_test(v, 30));
    bit_toggle(&v, 5);
    printf("toggle 5     : 0x%08x\n", v);
    bit_clear(&v, 31);
    printf("clear 31     : 0x%08x\n", v);
    bits_toggle_mask(&v, 0x0000000Fu);
    printf("toggle 0xF   : 0x%08x\n", v);
    uint32_t f = 0xFFFFFFFFu;
    field_write(&f, 0x00F0u, 0x5u << 4);
    printf("field 7:4 = 5: 0x%08x\n", f);
    bool ok = bit_set(&v, 32);
    printf("k=32 set ok? : %d, value still 0x%08x\n", ok, v);
    printf("k=-1 test    : %d\n", bit_test(v, (unsigned)-1));

    /* Write-one-to-clear: acknowledge bit 1 while bit 2 is also pending. */
    sim_status = 0x6u;                       /* bits 1 and 2 pending */
    uint32_t tmp = sim_status;               /* read-modify-write (wrong here) */
    tmp &= ~(1u << 1);
    sim_write_w1c(tmp);                      /* writes 1 to bit 2, clearing it */
    printf("RMW ack bit 1  -> status 0x%x (bit 1 not acknowledged, bit 2 cleared unseen)\n", sim_status);

    sim_status = 0x6u;
    sim_write_w1c(1u << 1);                  /* write only the bit to acknowledge */
    printf("direct ack bit 1 -> status 0x%x (bit 2 kept)\n", sim_status);
    return 0;
}

Output:

set 0 and 31 : 0x80000001
test 31, 30  : 1 0
toggle 5     : 0x80000021
clear 31     : 0x00000021
toggle 0xF   : 0x0000002e
field 7:4 = 5: 0xffffff5f
k=32 set ok? : 0, value still 0x0000002e
k=-1 test    : 0
RMW ack bit 1  -> status 0x2 (bit 1 not acknowledged, bit 2 cleared unseen)
direct ack bit 1 -> status 0x4 (bit 2 kept)

Reading the output

• Setting bits 0 and 31 gives 0x80000001. Test 31 is true and test 30 is false.
• Toggling bit 5 adds 0x20, giving 0x80000021. Clearing 31 leaves 0x00000021. Toggling mask 0xF flips four bits: bits 0 (was 1, now 0) and 1, 2, 3 (were 0, now 1), giving 0x2e.
• field_write with mask 0x00F0 and value 5 shifted into place turns 0xffffffff into 0xffffff5f: the four bits 7 to 4 become 0101, nothing else moves.
• k = 32 returns false and the value is unchanged. k = -1 converts to 4294967295 and is rejected.

If the value lives in a shared hardware status register

A hardware register is a location in memory-mapped I/O (MMIO): the address is wired to a peripheral, not to RAM. The same masks apply, but one fact drives everything that changes: the hardware, an interrupt handler or another processor can read and write that location at the same moment your code does. A read-modify-write is the sequence read the whole word, change one bit in a copy, write the whole word back. Every "set bit k", "clear bit k" and "toggle bit k" above is one of those, and that is what becomes unsafe. Three things follow.

1. volatile. Declare the pointer volatile uint32_t *. Without it the compiler may cache the value in a CPU register, merge two accesses into one or drop a read whose result is unused, all of which are wrong when reading the location itself has an effect.
2. Read-modify-write is not atomic. *reg |= mask is three steps: read, OR, write. If an interrupt service routine (ISR, a function the hardware runs when an event fires) or another bus master (any other device that can write the same register, such as a second CPU core or a DMA controller that copies data without the CPU) changes a different bit between the read and the write, the write puts back a stale value and that change is lost. For example, your code reads 0x1, an ISR sets bit 3 so the register holds 0x9, and your write of 0x1 | 0x2 = 0x3 silently turns bit 3 back off. Fixes, in order of preference: use the peripheral's separate set and clear registers if it offers them (one write touches only the bits you name); otherwise disable interrupts around the read-modify-write; for shared plain memory (not MMIO) use an atomic operation (one that completes as a single indivisible step, so no other observer can see it half done) such as atomic_fetch_or from <stdatomic.h>, which ORs a mask into a variable atomically.
3. Write-one-to-clear (W1C) status bits. Many status registers clear a flag when you write a 1 to it, and writing 0 changes nothing. Then the read-modify-write "clear" is dangerous: the demo above has bits 1 and 2 pending, so the register reads 0x6 (binary 110). Clearing bit 1 in a temporary gives 0x4 (binary 100), and writing that back writes a 1 to bit 2, which clears bit 2. So 0x6 minus the bits named by the write 0x4 leaves 0x2. The output shows that result: status 0x2, so bit 2 was cleared without anyone handling it and bit 1 was never acknowledged. Writing only the mask (1u << 1) leaves status 0x4, bit 2 intact. For a W1C register the correct "clear bit k" is a single plain write of the mask, and "set" and "toggle" usually do not exist.

Check the peripheral's datasheet for each register's access type (read/write, read-only, W1C, write-only) before choosing the operation.

Complexity and mistakes

Each function is O(1) time and O(1) space: one shift, one mask, one store. Common mistakes: 1 << k with a signed 1 (undefined for k = 31), forgetting the parentheses in (v >> k) & 1u, writing v & mask to "clear" (that keeps the bit), and using || instead of |.

Running the code

gcc -std=c11 -Wall -Wextra -fsanitize=undefined bits.c -o bits && ./bits

The idea in plain words

The integer square root of n is the largest integer r with r * r <= n. A 64-bit n has a root below 2^32, so the root has at most 32 bits. The digit-by-digit method decides those bits from the top: for each bit position k from 31 down to 0, try setting bit k of the root; keep it if the square of the root so far does not exceed n. That is binary search on the answer, done one bit at a time, with no multiplication or division.

The trick that avoids multiplying: if Q is the root bits decided so far (a number whose lower bits are all zero), then

So testing the next bit only needs the remainder n - Q^2 compared with 2 * Q * 2^k + 4^k, and that sum is cheap to maintain with shifts. The code keeps root = Q * 2^(k+1) and bit = 4^k. The variable root is therefore not the partial answer itself but the partial answer multiplied by a power of two (a scaled copy), chosen so that 2 * Q * 2^k is exactly root and the test is simply n >= root + bit. Because the scale changes by a factor of 2 per step, root is halved by a shift each iteration, and it is only equal to the partial answer at the very end, when the scale is 2^0 = 1. So in the trace below the root column can shrink between rows even though the partial answer never does.

Why bit steps by a factor of 4: root bit k has the weight 2^k, and its square contributes 2^(2k) = 4^k to n. So each root bit uses two bits of n (a digit pair, in base 4), a 64-bit n has 32 pairs and the root has at most 32 bits. Starting at bit = 4^31 = 2^62 and moving down with bit >>= 2 visits one pair per root bit.

Brute force and why it is not enough

Counting up until r * r > n takes up to 2^32 steps. A floating-point sqrt on a double is not exact for 64-bit inputs, because double holds only 53 significant bits, so values near 2^64 can come out one too high or low.

The invariant

Before the iteration that handles bit = 4^k:

• root = Q * 2^(k+1), where Q is the root bits already chosen above position k, as a number with zeros below;
• the remaining n equals n0 - Q^2, where n0 is the original input;
• Q^2 <= n0 < (Q + 2^(k+1))^2 (the true root lies between Q and Q + 2^(k+1)).

The test n >= root + bit is equivalent to (Q + 2^k)^2 <= n0. If true, bit k of the root is 1: subtract root + bit from n (it is exactly the increase in the square), and set root = (root >> 1) + bit. The shift halves the scale because the next iteration needs Q' * 2^k instead of Q * 2^(k+1); adding bit = 4^k = 2^k * 2^k adds the new bit 2^k at that scale. If false, only the shift happens. After the last iteration (bit = 1, k = 0) the scale is 2^0 so root = Q is the answer, and the invariant says Q^2 <= n0 < (Q+1)^2, which is the definition of floor of the square root. The first loop skips leading digit pairs (the high base-4 digits of n that are zero, one per root bit that must be 0): bit starts at the largest power of 4 that fits in 64 bits (2^62) and is reduced until bit <= n. This keeps the invariant because n0 < 4^(k+1) already holds there, so the higher root bits are zero. 1ULL << 63 would not do, since the starting bit has to be a power of 4.

The sum root + bit equals 2^k * (2Q + 2^k) = (Q + 2^k)^2 - Q^2, so it is less than (Q + 2^k)^2. Q only has bits above position k and fits in 32 bits, so Q <= 2^32 - 2^(k+1) and Q + 2^k <= 2^32 - 2^k < 2^32. Its square is therefore below 2^64, and root + bit never wraps around in a 64-bit unsigned integer.

Code

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

/* floor(sqrt(n)) for any uint64_t, using only shifts, adds, subtracts and compares. */
uint32_t isqrt64(uint64_t n) {
    uint64_t root = 0;                  /* scaled partial root, see the invariant below */
    uint64_t bit = 1ULL << 62;          /* the highest power of 4 that fits in 64 bits */
    while (bit > n) bit >>= 2;          /* skip leading zero digit pairs */
    while (bit != 0) {
        if (n >= root + bit) {          /* is the next root bit 1? */
            n -= root + bit;
            root = (root >> 1) + bit;
        } else {
            root >>= 1;
        }
        bit >>= 2;
    }
    return (uint32_t)root;              /* root <= 2^32 - 1 */
}

static void trace(uint64_t n0) {
    uint64_t n = n0, root = 0, bit = 1ULL << 62;
    while (bit > n) bit >>= 2;
    printf("n0 = %llu\n", (unsigned long long)n0);
    while (bit != 0) {
        int one = n >= root + bit;
        if (one) { n -= root + bit; root = (root >> 1) + bit; } else root >>= 1;
        printf("  bit=%-3llu took=%d  remainder n=%-3llu root=%llu\n", (unsigned long long)bit, one,
               (unsigned long long)n, (unsigned long long)root);
        bit >>= 2;
    }
    printf("  result %llu\n", (unsigned long long)root);
}

int main(void) {
    trace(99);
    uint64_t tests[] = {0, 1, 2, 3, 4, 15, 16, 17, 99, 4294967295ULL * 4294967295ULL - 1,
                        4294967295ULL * 4294967295ULL, UINT64_MAX};
    for (unsigned i = 0; i < sizeof tests / sizeof tests[0]; i++)
        printf("isqrt64(%llu) = %u\n", (unsigned long long)tests[i], isqrt64(tests[i]));
    return 0;
}

Compiled with gcc -std=c11 -Wall -Wextra -fsanitize=undefined -fno-sanitize-recover=undefined in a python:3.12 container (GCC 14.2, aarch64), no warnings or sanitizer reports, it prints:

n0 = 99
  bit=64  took=1  remainder n=35  root=64
  bit=16  took=0  remainder n=35  root=32
  bit=4   took=0  remainder n=35  root=16
  bit=1   took=1  remainder n=18  root=9
  result 9
isqrt64(0) = 0
isqrt64(1) = 1
isqrt64(2) = 1
isqrt64(3) = 1
isqrt64(4) = 2
isqrt64(15) = 3
isqrt64(16) = 4
isqrt64(17) = 4
isqrt64(99) = 9
isqrt64(18446744065119617024) = 4294967294
isqrt64(18446744065119617025) = 4294967295
isqrt64(18446744073709551615) = 4294967295

The function was also checked against the definition r*r <= n < (r+1)*(r+1) (evaluated in 128-bit arithmetic in the test only) for every n below 2^28, for 50 million pseudo-random 64-bit values of varied magnitude, and for the squares r*r and their neighbours r*r - 1 and r*r + 1 at 4,295 values of r stepping through the full 32-bit range: 318,448,340 inputs, no failures.

Worked trace

trace(99) in the output. Here the root is 9 because 9*9 = 81 <= 99 < 100. Each line is printed from the real loop:

Reading the table: root after is the partial answer Q times the current scale 2^k, so it falls from 64 to 32 to 16 while Q stays at 8 (bits k = 2 and k = 1 were tried and rejected, each time only the shift happened). The remaining n is 99 - Q^2: 99 - 64 = 35 in rows 1 to 3 and 99 - 81 = 18 in row 4. In the last row the scale is 1, so root = Q = 9 is the answer.

Complexity

At most 32 iterations of the main loop (one per root bit) plus at most 32 of the skip loop: O(log n), meaning O(word size) for fixed-width input. Space O(1), no recursion.

Edge cases and common mistakes

• n = 0 gives 0 (the skip loop reduces bit to 0, so the main loop never runs); n = 1 gives 1.
• Perfect squares and one below: (2^32 - 1)^2 - 1 gives 2^32 - 2, and UINT64_MAX gives 2^32 - 1, the largest possible root; the result fits in uint32_t.
• Mistake: starting bit at an odd power of two (1ULL << 63) breaks the pairing of digits.
• Mistake: testing (root + bit) squared (multiplication that can overflow); the scaled form avoids it.
• Mistake: (uint64_t)sqrt((double)n) is wrong near 2^64 because converting n to double rounds.
• Mistake: forgetting that n is modified in the loop; keep the original if the caller needs it.

Running the code

gcc -std=c11 -Wall -Wextra -fsanitize=undefined -fno-sanitize-recover=undefined isqrt.c -o isqrt
./isqrt

Save the listing as isqrt.c. No other files are needed.

The idea in plain words

A bit vector is an array of bits stored 64 to a machine word, with the bits of each word numbered from the least significant end (LSB-first: position 0 of a word is its lowest bit). Two questions are asked of it all the time:

• rank(pos): how many 1 bits are in front of position pos. It is defined here as the count in positions 0 .. pos-1 (exclusive, so rank(0) = 0); the inclusive version is rank(pos + 1).
• select(k): the position of the k-th 1 bit, counting from k = 1. It is the inverse of rank: select(k) = p means rank(p) = k - 1 and rank(p + 1) = k.

Counting by scanning from the start costs O(n / 64) per query. The design choice is to spend a small amount of extra memory on precomputed counters so that a query touches only a few words. Static means the bits never change after construction, so the counters never need updating.

Layout

The bits are cut into superblocks (fixed-size chunks) of 512 bits (8 words). A table super[i] holds the prefix count for superblock i, the number of 1 bits in all the superblocks before it, stored as a 32-bit integer (enough for up to 2^32 - 1 ones). One extra entry at the end holds the total.

• rank(pos): take super[pos / 512], add the popcount (number of 1 bits in a word, __builtin_popcountll in GCC/Clang) of the whole words in this superblock before pos, then add the popcount of the partial word masked to the bits below pos. At most 7 whole words plus 1 partial word is 8 popcounts, plus one lookup, a constant independent of n: O(1). The worked trace below adds the three pieces up for rank(700).
• select(k): binary search super[] for the last superblock whose prefix count is below k (O(log(n / 512)) steps), scan its at most 8 words with popcount to find the word holding the k-th one, then inside that word clear the lowest set bit until the wanted one is lowest and take its position with count-trailing-zeros (__builtin_ctzll, which returns the index of the lowest set bit of a word). Clearing works because x - 1 flips the lowest set bit to 0 and turns every bit below it into 1, so x & (x - 1) is x with exactly that lowest 1 removed: for x = 0b101000, x - 1 = 0b100111 and x & (x - 1) = 0b100000. That last step costs at most 63 iterations.

Space overhead and the billion-bit sizing

For n = 1,000,000,000 bits: the raw data is 125.0 MB (10^9 / 8 bytes). There are ceil(10^9 / 512) = 1,953,125 superblocks at 4 bytes each: 7.81 MB, which is 32 / 512 = 6.25% extra. The block size is the knob:

A two-level layout reaches roughly 3% with constant-time rank: a 32-bit absolute count per 4096-bit superblock (32 / 4096 = 0.78%) plus a 12-bit count relative to its superblock for every 512-bit block (12 / 512 = 2.34%; 12 bits suffice because at most 3,584 ones precede a block inside a superblock), total 3.125%. Binary search for select then runs over superblock counts and a small scan over the relative counts. For a billion bits the single-level 512-bit layout needs ceil(log2(1,953,125)) = 21 binary-search steps in select.

Commit to the single-level 512-bit layout by default: 6.25% overhead, O(1) rank (at most 8 popcounts and one lookup) and select in O(log(n / 512)) plus at most 8 popcounts and 63 bit-clears. Two refinements exist when the default is not enough. The two-level layout applies when memory is the binding constraint. A sampled select index (store the position of every s-th one, which costs extra space, so a query starts near its answer instead of binary searching the whole table) applies when the O(log(n / 512)) search in select is too slow. A worst-case constant bound needs more structure than is described here.

Code

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

#define WORDS_PER_SUPER 8                       /* 8 * 64 = 512 bits per superblock */
#define BITS_PER_SUPER (WORDS_PER_SUPER * 64)

typedef struct {
    uint64_t nbits;
    uint64_t nwords;
    uint64_t *words;                            /* the bits, LSB-first inside each word */
    uint32_t *super;                            /* super[i] = set bits before superblock i; one extra entry at the end = total */
    uint64_t nsuper;
} BitVec;

static BitVec build(const uint64_t *words, uint64_t nbits) {
    BitVec v;
    v.nbits = nbits;
    v.nwords = (nbits + 63) / 64;
    v.words = calloc(v.nwords ? v.nwords : 1, sizeof(uint64_t));
    memcpy(v.words, words, v.nwords * sizeof(uint64_t));
    if (nbits % 64) v.words[v.nwords - 1] &= (1ULL << (nbits % 64)) - 1;   /* clear bits past the end */
    v.nsuper = (v.nwords + WORDS_PER_SUPER - 1) / WORDS_PER_SUPER;
    v.super = malloc((v.nsuper + 1) * sizeof(uint32_t));
    uint32_t running = 0;
    for (uint64_t s = 0; s < v.nsuper; s++) {
        v.super[s] = running;
        for (uint64_t w = s * WORDS_PER_SUPER; w < (s + 1) * WORDS_PER_SUPER && w < v.nwords; w++)
            running += (uint32_t)__builtin_popcountll(v.words[w]);
    }
    v.super[v.nsuper] = running;
    return v;
}

/* Number of set bits in positions [0, pos). pos may equal nbits. */
static uint64_t rank1(const BitVec *v, uint64_t pos) {
    uint64_t w = pos / 64, s = w / WORDS_PER_SUPER;
    uint64_t r = v->super[s];
    for (uint64_t i = s * WORDS_PER_SUPER; i < w; i++) r += (uint64_t)__builtin_popcountll(v->words[i]);
    if (pos % 64) r += (uint64_t)__builtin_popcountll(v->words[w] & ((1ULL << (pos % 64)) - 1));
    return r;
}

/* Same pieces as rank1, printed one by one. */
static void explain_rank(const BitVec *v, uint64_t pos) {
    uint64_t w = pos / 64, s = w / WORDS_PER_SUPER;
    uint64_t r = v->super[s];
    printf("  pos %llu is in word %llu, superblock %llu: super[%llu] = %llu\n", (unsigned long long)pos,
           (unsigned long long)w, (unsigned long long)s, (unsigned long long)s, (unsigned long long)r);
    for (uint64_t i = s * WORDS_PER_SUPER; i < w; i++) {
        uint64_t c = (uint64_t)__builtin_popcountll(v->words[i]);
        r += c;
        printf("  whole word %llu adds %llu, running total %llu\n", (unsigned long long)i, (unsigned long long)c,
               (unsigned long long)r);
    }
    if (pos % 64) {
        uint64_t c = (uint64_t)__builtin_popcountll(v->words[w] & ((1ULL << (pos % 64)) - 1));
        r += c;
        printf("  word %llu masked to its low %llu bits adds %llu, rank = %llu\n", (unsigned long long)w,
               (unsigned long long)(pos % 64), (unsigned long long)c, (unsigned long long)r);
    }
}

/* Position of the k-th set bit, k = 1 for the first. Returns UINT64_MAX if there are fewer than k. */
static uint64_t select1(const BitVec *v, uint64_t k) {
    if (k == 0 || k > v->super[v->nsuper]) return UINT64_MAX;
    uint64_t lo = 0, hi = v->nsuper - 1;        /* last superblock whose prefix count is < k */
    while (lo < hi) {
        uint64_t mid = (lo + hi + 1) / 2;
        if (v->super[mid] < k) lo = mid; else hi = mid - 1;
    }
    uint64_t need = k - v->super[lo];           /* 1-based rank inside the superblock */
    uint64_t w = lo * WORDS_PER_SUPER;
    for (;; w++) {
        uint64_t c = (uint64_t)__builtin_popcountll(v->words[w]);
        if (need <= c) break;
        need -= c;
    }
    uint64_t x = v->words[w];
    while (--need) x &= x - 1;                  /* drop the lowest set bit need-1 times */
    return w * 64 + (uint64_t)__builtin_ctzll(x);
}

/* Same steps as select1, printing the state after each one. */
static void explain_select(const BitVec *v, uint64_t k) {
    uint64_t lo = 0, hi = v->nsuper - 1;
    while (lo < hi) {
        uint64_t mid = (lo + hi + 1) / 2;
        printf("  binary search lo=%llu hi=%llu mid=%llu super[mid]=%u -> %s\n", (unsigned long long)lo,
               (unsigned long long)hi, (unsigned long long)mid, v->super[mid], v->super[mid] < k ? "go right" : "go left");
        if (v->super[mid] < k) lo = mid; else hi = mid - 1;
    }
    uint64_t need = k - v->super[lo];
    printf("  superblock %llu, ones before it %u, need the %llu-th one inside it\n", (unsigned long long)lo, v->super[lo],
           (unsigned long long)need);
    uint64_t w = lo * WORDS_PER_SUPER;
    for (;; w++) {
        uint64_t c = (uint64_t)__builtin_popcountll(v->words[w]);
        printf("  word %llu has %llu ones, need=%llu\n", (unsigned long long)w, (unsigned long long)c, (unsigned long long)need);
        if (need <= c) break;
        need -= c;
    }
    uint64_t x = v->words[w];
    printf("  inside word %llu: clear the lowest set bit %llu times, then take ctz\n", (unsigned long long)w,
           (unsigned long long)(need - 1));
    while (--need) x &= x - 1;
    printf("  position = %llu * 64 + %d = %llu\n", (unsigned long long)w, __builtin_ctzll(x),
           (unsigned long long)(w * 64 + (uint64_t)__builtin_ctzll(x)));
}

int main(void) {
    /* 1200-bit vector, set where position % 7 == 0 or position % 64 == 63 */
    uint64_t nbits = 1200, words[19] = {0};
    for (uint64_t p = 0; p < nbits; p++)
        if (p % 7 == 0 || p % 64 == 63) words[p / 64] |= 1ULL << (p % 64);
    words[18] |= ~0ULL << 48;                   /* garbage in the 16 spare bits past position 1199: build() must clear it */
    BitVec v = build(words, nbits);
    printf("total ones = %u, superblocks = %llu\n", v.super[v.nsuper], (unsigned long long)v.nsuper);
    uint64_t probes[] = {0, 1, 7, 8, 63, 64, 511, 512, 513, 1199, 1200};
    for (unsigned i = 0; i < sizeof probes / sizeof probes[0]; i++)
        printf("rank1(%4llu) = %3llu\n", (unsigned long long)probes[i], (unsigned long long)rank1(&v, probes[i]));
    uint64_t ks[] = {1, 2, 10, 74, 75, 76, 200};
    for (unsigned i = 0; i < sizeof ks / sizeof ks[0]; i++) {
        uint64_t p = select1(&v, ks[i]);
        if (p == UINT64_MAX) printf("select1(%3llu) = none\n", (unsigned long long)ks[i]);
        else printf("select1(%3llu) = %4llu  rank1(pos)=%llu rank1(pos+1)=%llu\n", (unsigned long long)ks[i], (unsigned long long)p,
                    (unsigned long long)rank1(&v, p), (unsigned long long)rank1(&v, p + 1));
    }
    printf("trace of rank1(700):\n");
    explain_rank(&v, 700);
    printf("trace of select1(75):\n");
    explain_select(&v, 75);
    /* sizing for one billion bits */
    double n = 1e9, raw = n / 8;
    double sup = (n / BITS_PER_SUPER) * 4;
    printf("1e9 bits: raw %.1f MB, superblock counts %.2f MB (%.2f%% overhead)\n",
           raw / 1e6, sup / 1e6, 100.0 * sup / raw);
    free(v.words); free(v.super);
    return 0;
}

Compiled with gcc -std=c11 -Wall -Wextra -fsanitize=undefined,address -fno-sanitize-recover=undefined in a python:3.12 container (GCC 14.2, aarch64), no warnings or sanitizer reports, it prints:

total ones = 187, superblocks = 3
rank1(   0) =   0
rank1(   1) =   1
rank1(   7) =   1
rank1(   8) =   2
rank1(  63) =   9
rank1(  64) =  10
rank1( 511) =  79
rank1( 512) =  80
rank1( 513) =  80
rank1(1199) = 187
rank1(1200) = 187
select1(  1) =    0  rank1(pos)=0 rank1(pos+1)=1
select1(  2) =    7  rank1(pos)=1 rank1(pos+1)=2
select1( 10) =   63  rank1(pos)=9 rank1(pos+1)=10
select1( 74) =  469  rank1(pos)=73 rank1(pos+1)=74
select1( 75) =  476  rank1(pos)=74 rank1(pos+1)=75
select1( 76) =  483  rank1(pos)=75 rank1(pos+1)=76
select1(200) = none
trace of rank1(700):
  pos 700 is in word 10, superblock 1: super[1] = 80
  whole word 8 adds 10, running total 90
  whole word 9 adds 10, running total 100
  word 10 masked to its low 60 bits adds 8, rank = 108
trace of select1(75):
  binary search lo=0 hi=2 mid=1 super[mid]=80 -> go left
  superblock 0, ones before it 0, need the 75-th one inside it
  word 0 has 10 ones, need=75
  word 1 has 10 ones, need=65
  word 2 has 10 ones, need=55
  word 3 has 10 ones, need=45
  word 4 has 10 ones, need=35
  word 5 has 10 ones, need=25
  word 6 has 10 ones, need=15
  word 7 has 10 ones, need=5
  inside word 7: clear the lowest set bit 4 times, then take ctz
  position = 7 * 64 + 28 = 476
1e9 bits: raw 125.0 MB, superblock counts 7.81 MB (6.25% overhead)

Worked trace

rank. rank1(700) on the demo vector from the listing adds three pieces. Position 700 is in word 10 (700 / 64 = 10, remainder 60) and superblock 1 (word 10 / 8 words). The superblock table gives super[1] = 80 ones before bit 512. Whole words 8 and 9 (bits 512 to 639) hold 10 ones each, giving 80 + 10 + 10 = 100. The partial word 10 is masked to its low 60 bits (bits 640 to 699, mask (1ULL << 60) - 1) and holds 8 ones, so rank1(700) = 108, exactly the printed trace.

select. The demo vector has 1,200 bits with a 1 at every position divisible by 7 or ending a word (position % 64 = 63): 187 ones, three superblocks. Each 64-bit word holds 10 ones in superblock 0, so super[1] = 80. The printed trace of select1(75): the binary search over super[] finds superblock 0 (super[1] = 80 is not below 75). The scan subtracts the 10 ones of words 0 through 6 (75, 65, 55, 45, 35, 25, 15 down to 5 still needed), leaving the 5th one of word 7. Clearing the lowest set bit 4 times and taking the trailing-zero count gives bit 28, so the position is 7 * 64 + 28 = 476. The check line rank1(pos)=74 rank1(pos+1)=75 confirms it.

Complexity

Build: O(n / 64) time, one pass of popcounts. Extra space: 4 bytes per 512 bits (6.25%) plus the 4-byte total. rank: O(1) (at most 8 popcounts: 7 whole words plus 1 partial word). select: O(log(n / 512)) for the search plus at most 8 popcounts plus at most 63 bit-clears.

Edge cases and common mistakes

• pos = n for rank (the exclusive end) must work, so keep the extra total entry in super[]; a multiple of 512 bits puts pos = n exactly on the extra entry.
• Bits past n in the last word must be cleared at build time, or they inflate counts. The demo sets the 16 spare bits of its last word to 1 before building; the printed total of 187 shows they were cleared (without the clearing line the total would read 203).
• select(k) for k = 0 or k larger than the total has no answer; return a sentinel, not garbage.
• 1ULL << 64 is undefined in C, which is why the partial-word mask is only built when pos % 64 != 0.
• Superblocks with zero ones repeat the same prefix count, so the binary search must pick the last superblock whose prefix is below k.
• Mistake: storing 16-bit counters for large vectors; counters overflow beyond 65,535 ones.
• The listing keeps its counts in uint32_t and does not check the limit: a vector holding 2^32 or more ones would wrap the counters, so use uint64_t counters beyond that size (the billion-bit example is well inside the limit).

Running the code

gcc -std=c11 -Wall -Wextra -fsanitize=undefined,address -fno-sanitize-recover=undefined rank_select.c -o rank_select
./rank_select

Save the listing as rank_select.c. It needs GCC or Clang for the popcount and count-trailing-zeros built-ins.

The idea

x & -x keeps only the lowest 1 bit of x and clears all the others, so the result is a power of two: the value 2^k where k is the position of that bit. In two's complement, -x equals ~x + 1 (flip every bit and add one). Look at what that does bit by bit. Let k be the position of the lowest 1 in x, so bits 0 to k-1 of x are 0.

• Below k: x has 0s, so ~x has 1s. Adding 1 makes the carry ripple through all those 1s (a carry ripple: each 1 plus the incoming carry gives 0 and passes a carry to the next bit up), turning each into 0.
• At k: x has a 1, so ~x has a 0 there. The carry arrives and turns it into 1.
• Above k: the carry stops at k, so these bits stay equal to ~x, the opposite of x.

Now AND x with that: below k both are 0, giving 0; at k both are 1, giving 1; above k the bits are opposites, giving 0. Only bit k survives.

The same argument as columns, for x = 12 in 8 bits (the lowest 1 is at k = 2):

Worked examples

The trace is printed by the program in the next section, using 8 bits for display.

• Positive, x = 12 (00001100): -x is 11110100. AND gives 00000100, which is 4: the lowest set bit is at position 2.
• Negative, x = -12 (11110100): -x is 12 (00001100). AND gives 00000100 again, which is 4. Negative inputs work because the argument above only used the representation of x, not its sign.
• x = 40 (00101000): result 00001000, which is 8.

Looping over all set bits

Peel off the lowest set bit, process it, remove it with XOR, repeat. The loop runs once per set bit, not once per bit position. x &= x - 1 is an equivalent way to remove the lowest set bit.

Where else it shows up

• Fenwick tree (binary indexed tree): a structure that answers prefix sums (the sum of the first i entries) and point updates in O(log n) using an array. Node i stores the sum of a block whose length is the lowest set bit of i, ending at position i. For n = 16 the blocks are:

A query walks down with i -= i & -i: the block ending at i is summed, then the walk jumps to the position just before that block. An update walks up with i += i & -i, visiting exactly the nodes whose block contains the changed position. For a change at position 5 those are node 5 (5 to 5), node 6 (5 to 6), node 8 (1 to 8) and node 16 (1 to 16), which is the path the code prints. The code prints the real paths.

• Bitmaps of ready items: a scheduler or allocator keeps a word with one bit per item; x & -x finds the lowest-numbered ready one, and .bit_length() - 1 turns the power of two into an index (.bit_length() is the number of binary digits needed to write the integer, which is k + 1 for 2^k). In C, a count-trailing-zeros instruction (it counts the 0 bits below the lowest 1, which is exactly k) does the same job.
• Bit-set iteration in general, and finding alignment: the largest power of two that divides x is exactly x & -x.

Code

def lowest_set_bit(x: int) -> int:
    """Return 2**k where k is the index of the lowest 1 bit (0 if x == 0)."""
    return x & -x


def show8(label: str, value: int) -> None:
    print(f"{label:<6}{value & 0xFF:08b}  ({value})")


for x in (12, -12, 40):
    print(f"x = {x}")
    show8("x", x)
    show8("-x", -x)
    show8("x&-x", lowest_set_bit(x))
print()


def set_bit_indexes(x: int) -> list[int]:
    """Visit each set bit once, lowest first. x must be >= 0."""
    found = []
    while x:
        low = x & -x                    # isolate the lowest set bit (a power of two)
        found.append(low.bit_length() - 1)
        x ^= low                        # remove it (same as x &= x - 1)
    return found


print("set bits of 0b1011001 (89):", set_bit_indexes(0b1011001))
print("set bits of 0:", set_bit_indexes(0))


class Fenwick:
    """Binary indexed tree over positions 1..n for prefix sums."""

    def __init__(self, n: int) -> None:
        self.n = n
        self.tree = [0] * (n + 1)

    def add(self, i: int, delta: int) -> list[int]:
        path = []
        while i <= self.n:
            self.tree[i] += delta
            path.append(i)
            i += i & -i                 # climb to the next node that covers i
        return path

    def prefix_sum(self, i: int) -> int:
        total = 0
        while i > 0:
            total += self.tree[i]
            i -= i & -i                 # drop the lowest set bit
        return total


fw = Fenwick(16)
print("add at 5 touches nodes:", fw.add(5, 10))
print("add at 3 touches nodes:", fw.add(3, 4))
print("prefix_sum(5) =", fw.prefix_sum(5), " prefix_sum(2) =", fw.prefix_sum(2))
steps = []
i = 13
while i > 0:
    steps.append(i)
    i -= i & -i
print("query path for 13:", steps)

import random
random.seed(7)
for _ in range(300):
    n = random.randint(1, 40)
    vals = [0] * (n + 1)
    f = Fenwick(n)
    for _ in range(30):
        p, d = random.randint(1, n), random.randint(-9, 9)
        vals[p] += d
        f.add(p, d)
        q = random.randint(0, n)
        assert f.prefix_sum(q) == sum(vals[1:q + 1])
for x in range(-300, 300):
    if x:
        k = (x & -x).bit_length() - 1
        assert x % (1 << k) == 0 and (x >> k) & 1 == 1
print("checks passed")

Output:

x = 12
x     00001100  (12)
-x    11110100  (-12)
x&-x  00000100  (4)
x = -12
x     11110100  (-12)
-x    00001100  (12)
x&-x  00000100  (4)
x = 40
x     00101000  (40)
-x    11011000  (-40)
x&-x  00001000  (8)

set bits of 0b1011001 (89): [0, 3, 4, 6]
set bits of 0: []
add at 5 touches nodes: [5, 6, 8, 16]
add at 3 touches nodes: [3, 4, 8, 16]
prefix_sum(5) = 14  prefix_sum(2) = 0
query path for 13: [13, 12, 8]
checks passed

Reading the output

• The three blocks match the examples: 12 and -12 both give 4, and 40 gives 8.
• set_bit_indexes(89) (1011001) lists positions 0, 3, 4 and 6, lowest first, in four iterations. For 0 the loop body never runs.
• Adding at position 5 touches nodes 5, 6, 8, 16: from 5 (101) add its lowest bit 1 to reach 6 (110), add 2 to reach 8, add 8 to reach 16. Adding at 3 touches 3, 4, 8, 16. The prefix sum up to 5 reads node 5 (covering position 5, value 10) and node 4 (covering 1 to 4, value 4), giving 14. The query path for 13 is 13, 12, 8: three steps, one per set bit of 13 (1101).
• The final checks compare the Fenwick tree with a plain running sum on random operations (fixed seed) and verify the lowest-bit property for every x from -300 to 299.

Complexity, edge cases, mistakes

• The set-bit loop is O(popcount(x)) iterations, each O(1) for a machine word. A Fenwick update is O(log n) because each step moves the lowest set bit strictly higher; a query is O(popcount(i)) which is at most O(log n). Space is O(1) for the loop and O(n) for the tree.
• x & -x is 0 when x is 0, so the loop condition while x stops correctly.
• In C, use an unsigned type. For signed INT_MIN, -x overflows, which is undefined behaviour. For uint32_t x, x & (0u - x) is fully defined because unsigned arithmetic wraps.
• The loop in Python requires x >= 0 as written, because a negative integer has infinitely many leading ones and never reaches 0 by removing low bits.
• Mixing up the index (k) and the value (2^k) is the usual slip: x & -x returns the value.

Running the code

python lowbit.py

The short answer

A right shift moves every bit toward the low end. The two flavours differ only in what enters at the top. A logical right shift always shifts in zeros, so it treats the value as an unsigned bit pattern. An arithmetic right shift copies the old top (sign) bit into the vacated positions, so a negative number stays negative. In C, >> on an unsigned type is always logical. On a negative signed value the standard does not say which one you get: the result is implementation-defined (C11 section 6.5.7), meaning each compiler must choose and document it. Almost every mainstream compiler chooses arithmetic, but portable code should not rely on that.

What the standard guarantees

Three terms in the table, in plain words. Undefined behaviour means the standard puts no requirement on what the program does at all, so the compiler may produce any result and may assume it never happens. Implementation-defined means the compiler must pick one behaviour and document it, so the result is reliable on one compiler but may differ on another. Two's complement, the way mainstream machines store signed integers, writes a negative number as a bit pattern whose top bit is 1; in that scheme ~x == -x - 1.

So the portable design is to decide which shift you mean and write it so the answer does not depend on the compiler.

Portable versions

• Logical shift of a signed value: convert to unsigned first. Conversion of a signed value to an unsigned type is defined (it wraps modulo 2^32), and shifting an unsigned value is defined: (uint32_t)x >> n.
• Arithmetic shift without relying on the compiler: for a negative x, ~x is non-negative (~x == -x - 1), so shifting it is fully defined. Shift that, then flip back: ~(~x >> n). For non-negative x a plain >> is already arithmetic.

Why ~(~x >> n) works, on 8 bits

Take x = -20. In 8 bits (two's complement) that is 11101100. Shifting it directly is the problem case, so complement first:

The result 11111011 is x shifted right by 2 with ones, not zeros, entering at the top. That is exactly what an arithmetic shift does: it sign-extends, meaning it copies the sign bit into the vacated positions. The flip works because complementing turns "fill with copies of the sign bit" into "fill with zeros", which an ordinary shift on a non-negative value already does. The C program below does the same on 32 bits.

Floor and truncation, with one number: -5 / 2 is -2.5. Floor rounds toward minus infinity and gives -3, which is what the arithmetic shift -5 >> 1 gives (11111011 shifted becomes 11111101, which is -3). Truncation rounds toward zero and gives -2, which is what C's / gives for -5 / 2 (C99 and later define this). The two agree for non-negative numbers and for exact divisions, and differ for inexact negative ones.

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

/* Logical right shift: zeros enter on the left. n must be 0..31. */
static uint32_t shr_logical(int32_t x, unsigned n) {
    return (uint32_t)x >> n;
}

/* Arithmetic right shift: the sign bit is copied in. n must be 0..31.
   For negative x, ~x is non-negative, so the shift below is fully defined. */
static int32_t shr_arithmetic(int32_t x, unsigned n) {
    return x < 0 ? ~(~x >> n) : x >> n;
}

int main(void) {
    int32_t x = -20;
    printf("x = %d = 0x%08x\n", x, (uint32_t)x);
    for (unsigned n = 1; n <= 3; n++) {
        printf("n=%u  logical=0x%08x  arithmetic=%d (0x%08x)\n", n,
               shr_logical(x, n), shr_arithmetic(x, n),
               (uint32_t)shr_arithmetic(x, n));
    }
    printf("-20 / 8 in C (truncates toward zero) = %d\n", x / 8);
    printf("-1 >> 5 arithmetic = %d\n", shr_arithmetic(-1, 5));
    printf("-1 >> 5 logical    = 0x%08x\n", shr_logical(-1, 5));
    printf("INT32_MIN >> 31 arithmetic = %d\n", shr_arithmetic(INT32_MIN, 31));

    /* Check against the compiler's own >> (arithmetic on gcc) on many values. */
    srand(12345);
    for (int i = 0; i < 200000; i++) {
        int32_t v = (int32_t)(((uint32_t)rand() << 16) ^ (uint32_t)rand());
        unsigned n = (unsigned)(rand() % 32);
        if (shr_arithmetic(v, n) != (v >> n)) { printf("MISMATCH\n"); return 1; }
        if (v >= 0 && shr_logical(v, n) != (uint32_t)(v >> n)) { printf("MISMATCH\n"); return 1; }
    }
    printf("portable shifts agree with gcc's >> on 200000 samples\n");
    return 0;
}

Output:

x = -20 = 0xffffffec
n=1  logical=0x7ffffff6  arithmetic=-10 (0xfffffff6)
n=2  logical=0x3ffffffb  arithmetic=-5 (0xfffffffb)
n=3  logical=0x1ffffffd  arithmetic=-3 (0xfffffffd)
-20 / 8 in C (truncates toward zero) = -2
-1 >> 5 arithmetic = -1
-1 >> 5 logical    = 0x07ffffff
INT32_MIN >> 31 arithmetic = -1
portable shifts agree with gcc's >> on 200000 samples

Reading the output

• -20 is 0xffffffec. Logically shifted right by 1 it becomes 0x7ffffff6, a huge positive number, because a zero entered at the top. Arithmetically shifted it becomes -10 (0xfffffff6), which is the sign-preserving answer.
• Shifting by 3 gives -3, not -2: an arithmetic right shift rounds toward negative infinity (floor), so -20 / 8 = -2.5 becomes -3. C division truncates toward zero and gives -2 for -20 / 8. Using >> as a divide-by-power-of-two on signed values is therefore not the same as / when the value is negative and not exactly divisible.
• -1 shifted arithmetically stays -1 for any count (all ones, copy a one in), while the logical shift of the same pattern gives 0x07ffffff.
• The sanity run compares shr_arithmetic with gcc's own >> on 200000 random values and shift counts and finds no mismatch, and the unsigned conversion path agrees with >> on every non-negative sample.

Edge cases and mistakes

• Shift count out of range. shr_arithmetic(x, 32) would shift by the width, which is undefined. Check n < 32 or mask it (n & 31) and document which.
• INT32_MIN. ~INT32_MIN is INT32_MAX, which is representable, so the trick works. Writing -x instead would overflow, which is why the code uses ~.
• Assuming >> divides. It floors, / truncates, and the two disagree for negatives.
• Assuming char is signed. Plain char may be signed or unsigned depending on the platform, and right-shifting a promoted negative char (C first widens it to int, keeping its sign) hits the same implementation-defined rule. Use uint8_t when you mean bytes.
• Java and others. Java defines both shifts (>> arithmetic, >>> logical), so this question only bites in C and C++.

Running the code

gcc -std=c11 -Wall -Wextra -fsanitize=undefined shift.c -o shift && ./shift