Bitset (C)
Topics: bit manipulation, popcount, fixed-size set
Problem
Implement a fixed-size bit set over caller-provided 64-bit words (no allocation) — the compact
"set of small integers" behind bitmap indexes, scheduler ready-masks, and Bloom-filter bins.
typedef struct { uint64_t *words; size_t nbits; } BitSet;
void bs_init(BitSet *bs, uint64_t *words, size_t nbits); // clears the set
void bs_set(BitSet *bs, size_t i);
void bs_clear(BitSet *bs, size_t i);
void bs_toggle(BitSet *bs, size_t i);
bool bs_test(const BitSet *bs, size_t i);
size_t bs_count(const BitSet *bs); // number of set bits
Bit i lives in words[i/64] at bit position i%64. words holds at least ceil(nbits/64)
entries; bs_init zeroes them.
Key concepts
- Word + bit split:
word = i / 64, mask = 1ULL << (i % 64) — then |= to set, &= ~mask to
clear, ^= to toggle, >> & 1 to test.
- popcount: sum
__builtin_popcountll(word) across all words for bs_count — only valid bits
are ever set, so the tail stays zero.
1ULL matters: shifting a 32-bit 1 past bit 31 is undefined; shift a 64-bit one.
Run
cc -std=c11 -O2 -Wall tests.c -o /tmp/bs && /tmp/bs
Sign in to submit your solution.