Bit Manipulation Questions
Working directly with binary representations: bitwise operators (AND, OR, XOR, NOT, shifts, rotates) and how they differ from the logical operators, masking, two's complement and sign extension, endianness, and classic bit tricks (popcount, parity, leading and trailing zeros, lowest and highest set bit, power-of-two tests and rounding, Gray code, bit reversal, swapping without a temporary, and finding unique or missing elements with XOR). Covers bitsets and bit-vectors (including rank and select, set operations, and bitmap-based counting and sieving), packing and unpacking fields into words, protocol headers and bit-level streams, C bitfields and their portability limits, bitmask enumeration of subsets, maximum XOR and Hamming distance, SIMD and table-driven popcount, branchless arithmetic and when it pays off, overflow detection with bit operations, and integer square root by bitwise methods. Especially relevant where memory and cycles are constrained. Excludes general number theory and modular arithmetic, device register programming, Bloom filters and hash design, and cryptographic primitives, which are covered elsewhere.
Implement roundUpToPowerOfTwo(x) (smallest power of two >= x, 0 for x == 0) and roundDownToPowerOfTwo(x) for 32-bit unsigned values without loops over every bit. Cover x already a power of two and x above 2^31.
Sample Answer
Short answer
Both functions rest on one move, the right-smear: copy the highest set bit into every position below it by OR-ing the value with itself shifted right by 1, 2, 4, 8 and 16. The result is a block of ones from the top bit down (for example 0b00100101 becomes 0b00111111). Round-down is then v - (v >> 1), which keeps only the top bit. Round-up smears x - 1 and adds 1, which turns the block of ones into the next power of two. The - 1 is what makes inputs that are already powers of two come back unchanged. Both finish in 5 shift-or steps with no loop over individual bits.
Why each step works
- Smear. After
v |= v >> 1, the top two bits are ones; afterv |= v >> 2the top four; then 8, 16, 32 (this chain of five steps, each building on the previous result, doubles the run of ones each time, and 1, 2, 4, 8, 16 are enough because 32 bits need five doublings). - Round-down: if the smeared value is
2^(k+1) - 1(ones from bit k down), thenv >> 1is2^k - 1, and the difference is exactly2^k, the highest set bit. This subtraction cannot overflow, sox >= 2^31is safe. - Round-up: for x already a power of two, say 64,
x - 1is 63, the smear leaves 63, and adding 1 gives 64. For x = 65,x - 1is 64, which smears to 127, and adding 1 gives 128. Without the- 1, 64 would smear to 127 and round up to 128, which is wrong. - x == 0 is checked first, because
0 - 1wraps to0xFFFFFFFFand would round up to 2^32. The required answer is 0 for both functions.
The input above 2^31
If x is greater than 2^31 (for example 0x80000001), the smallest power of two that is at least x is 2^32, which does not fit in a uint32_t. A uint32_t return would wrap to 0, the same value used for x == 0, so the caller could not tell the two apart. The code therefore returns uint64_t from round_up_pow2, which represents 2^32 exactly. A function that must return 32 bits should instead document and return a sentinel (a reserved value, here 0, that tells the caller there is no valid answer) for this case and let the caller check the input first. Round-down never overflows: the largest result is 2^31.
Code (C)
#include <stdint.h>
#include <stdio.h>
/* Copy the highest set bit into every position below it: 0b0010_0100 -> 0b0011_1111. */
static uint32_t smear_right(uint32_t v, FILE *trace) {
v |= v >> 1; if (trace) fprintf(trace, " |= >>1 : 0x%08X\n", v);
v |= v >> 2; if (trace) fprintf(trace, " |= >>2 : 0x%08X\n", v);
v |= v >> 4; if (trace) fprintf(trace, " |= >>4 : 0x%08X\n", v);
v |= v >> 8; if (trace) fprintf(trace, " |= >>8 : 0x%08X\n", v);
v |= v >> 16; if (trace) fprintf(trace, " |= >>16: 0x%08X\n", v);
return v;
}
/* Smallest power of two >= x; 0 for x == 0. Returns 64 bits because the answer for x > 2^31 is 2^32. */
static uint64_t round_up_pow2(uint32_t x, FILE *trace) {
if (x == 0) return 0;
uint32_t v = smear_right(x - 1, trace); /* all ones up to the top bit of x-1 */
return (uint64_t)v + 1; /* +1 carries into a single bit */
}
/* Largest power of two <= x; 0 for x == 0. */
static uint32_t round_down_pow2(uint32_t x, FILE *trace) {
if (x == 0) return 0;
uint32_t v = smear_right(x, trace); /* 0b0011_1111 for x in [32, 63] */
return v - (v >> 1); /* keep only the top bit; cannot overflow */
}
/* Reference by repeated doubling in 64-bit arithmetic. */
static uint64_t ref_up(uint32_t x) {
if (x == 0) return 0;
uint64_t p = 1;
while (p < x) p <<= 1;
return p;
}
static uint32_t ref_down(uint32_t x) {
if (x == 0) return 0;
uint64_t p = 1;
while (p * 2 <= x) p <<= 1;
return (uint32_t)p;
}
int main(void) {
uint32_t samples[] = {0u, 1u, 2u, 3u, 37u, 64u, 65u, 0x7FFFFFFFu, 0x80000000u, 0x80000001u, 0xFFFFFFFFu};
printf("%10s %12s %12s\n", "x", "round_up", "round_down");
for (unsigned i = 0; i < sizeof samples / sizeof samples[0]; i++) {
printf("0x%08X %12llu %12u\n", samples[i],
(unsigned long long)round_up_pow2(samples[i], NULL), round_down_pow2(samples[i], NULL));
}
printf("\ntrace of round_up_pow2(37): x-1 = 36 = 0x24\n");
uint64_t up = round_up_pow2(37, stdout);
printf(" +1 : %llu\n", (unsigned long long)up);
printf("trace of round_down_pow2(37):\n");
uint32_t down = round_down_pow2(37, stdout);
printf(" v - (v>>1): %u\n", down);
long bad = 0;
for (uint32_t x = 0; x < 100000; x++) {
if (round_up_pow2(x, NULL) != ref_up(x) || round_down_pow2(x, NULL) != ref_down(x)) bad++;
}
for (int k = 0; k < 32; k++) {
uint32_t p = (uint32_t)1 << k;
uint32_t probes[] = {p - 1, p, p + 1};
for (int j = 0; j < 3; j++) {
if (round_up_pow2(probes[j], NULL) != ref_up(probes[j]) || round_down_pow2(probes[j], NULL) != ref_down(probes[j])) bad++;
}
}
uint32_t state = 31u;
for (int n = 0; n < 100000; n++) {
state = state * 1664525u + 1013904223u;
if (round_up_pow2(state, NULL) != ref_up(state) || round_down_pow2(state, NULL) != ref_down(state)) bad++;
}
printf("\nmismatches against doubling loops: %ld\n", bad);
return 0;
}
Compiled with gcc 14.2 and -Wall -Wextra -fsanitize=undefined, it prints:
x round_up round_down
0x00000000 0 0
0x00000001 1 1
0x00000002 2 2
0x00000003 4 2
0x00000025 64 32
0x00000040 64 64
0x00000041 128 64
0x7FFFFFFF 2147483648 1073741824
0x80000000 2147483648 2147483648
0x80000001 4294967296 2147483648
0xFFFFFFFF 4294967296 2147483648
trace of round_up_pow2(37): x-1 = 36 = 0x24
|= >>1 : 0x00000036
|= >>2 : 0x0000003F
|= >>4 : 0x0000003F
|= >>8 : 0x0000003F
|= >>16: 0x0000003F
+1 : 64
trace of round_down_pow2(37):
|= >>1 : 0x00000037
|= >>2 : 0x0000003F
|= >>4 : 0x0000003F
|= >>8 : 0x0000003F
|= >>16: 0x0000003F
v - (v>>1): 32
mismatches against doubling loops: 0
Worked trace: x = 37 (binary 100101)
- Round-up:
x - 1 = 36 = 100100(0x24). After|= >>1it is110110(0x36), after|= >>2it is111111(0x3F), and the later steps leave it at 0x3F. Adding 1 gives 64. - Round-down: smearing 37 itself gives 0x37 after the first step and 0x3F after the second.
0x3F - (0x3F >> 1) = 63 - 31 = 32.
The table of samples shows the edge behaviour: 64 maps to 64 in both columns (already a power of two), 65 rounds up to 128 and down to 64, 0x7FFFFFFF rounds up to 2^31 (2147483648), 0x80000000 stays put, and 0x80000001 and 0xFFFFFFFF round up to 4294967296 (2^32) while rounding down to 2147483648.
Complexity
Five shift-or steps, so O(log W) time for word size W = 32 (a constant), and O(1) space. The fixed step count does not depend on the input, in contrast to a doubling loop that takes up to 32 iterations (the reference function in the listing).
Edge cases and common mistakes
- x == 0: return 0 explicitly in both.
- x already a power of two: round-up must return x. This is why you smear
x - 1, notx. - x above 2^31: round-up needs a 33rd bit, so widen the return type or define a sentinel.
- Computing
1u << 32anywhere (for instance as1u << (32 - clz)) is undefined; the smear-and-add form has no such shift. - A count-leading-zeros shortcut,
1u << (32 - clz(x - 1))(whereclz(y)is the number of 0 bits above the highest set bit ofy), is shorter but undefined at x == 1 (it needsclz(0), which is undefined) and at x > 2^31 (thenclz(x - 1)is 0 and the shift count is 32); guard those two cases. - Smearing with fewer than five steps works for small inputs and silently fails for large ones (a 20-bit value needs the
>> 16step); the checks cover powers of two and their neighbours at every bit position. - The results match doubling-loop references for x from 0 to 99,999, for every power of two with its neighbours, and for 100,000 pinned pseudo-random values; the printed mismatch count is 0.
Running the code
gcc -std=c11 -O2 -Wall -Wextra -fsanitize=undefined pow2_round.c -o pow2_round && ./pow2_round
Save the listing as pow2_round.c.
Pack two 16-bit unsigned fields into one 32-bit word and write the matching extraction. Then extend it to three fields of different widths, one of them a signed 16-bit temperature.
Sample Answer
The idea in plain words
A 32-bit word has 32 bit positions. Packing means placing each field in its own range of positions: shift the field up to its range, and combine the fields with OR. Unpacking is the reverse: shift the range down to position 0 and cut off everything above the field's width with a mask (a number with 1s in the positions you want to keep, ANDed with the value). Two rules keep it correct: every field must be reduced to exactly its own width before it is shifted in, and every field must be extracted with its own mask.
Part 1: two unsigned 16-bit fields
Put the first field in the high 16 bits and the second in the low 16 bits.
static uint32_t pack2(uint16_t hi, uint16_t lo) {
return ((uint32_t)hi << 16) | lo;
}
static void unpack2(uint32_t w, uint16_t *hi, uint16_t *lo) {
*hi = (uint16_t)(w >> 16);
*lo = (uint16_t)(w & 0xFFFFu);
}
The cast to uint32_t before the shift matters. In C, a uint16_t used in arithmetic is first converted to int (integer promotion), and shifting a value into the sign bit of a 32-bit int is undefined behaviour (the standard places no requirement on what the program then does, so any result is allowed). Doing the shift on a uint32_t is always defined. With real values: pack2(0xABCD, 0x1234) shifts 0xABCD left by 16 to get 0xABCD0000, then ORs in 0x1234, which only touches the low 16 bits, to get 0xABCD1234. unpack2 shifts right by 16 to get 0xABCD back and masks with 0xFFFF to get 0x1234. Both functions appear in the complete program in the next section.
Part 2: three fields of different widths, one of them a signed 16-bit temperature
Layout, high bits to low bits, 32 bits in total:
| Field | Width | Bits | Type |
|---|---|---|---|
sensor_id | 10 | 31..22 | unsigned, 0 to 1023 |
temp | 16 | 21..6 | signed, -32768 to 32767 |
flags | 6 | 5..0 | unsigned, 0 to 63 |
10 + 16 + 6 = 32. The temperature is stored in two's complement (the usual signed representation, where the top bit of the field is the sign). Two details make the signed field correct:
- Packing a negative value.
(uint32_t)(uint16_t)tempreduces the number modulo 2^16 and keeps exactly the 16 bits of its two's complement form. "Modulo 2^16" means adding 65,536 until the value lies in 0..65535: for -40 that gives 65,496, which is0xFFD8, the 16-bit two's complement pattern of -40. Converting a negative value to an unsigned type is defined by C as that reduction. If you instead widen the value to 32 bits first, every bit above bit 15 is 1 and ORing it in overwrites thesensor_idfield. The program shows the damage: without the 16-bit cut the word isfffff605and the unpacked id is 1023 instead of 300. - Unpacking (sign extension). After masking you hold a number from 0 to 65535 in which bit 15 is the sign. Sign extension means copying that bit into all higher bits so the value keeps its sign. The expression
(t ^ 0x8000) - 0x8000does it with defined arithmetic: XOR with0x8000flips only the sign bit, and that turns the 16-bit patterns into plain unsigned numbers in the same order as the signed values they stand for: the most negative pattern0x8000(-32768) becomes0x0000,0xFFFF(-1) becomes0x7FFF,0x0000(0) becomes0x8000, and0x7FFF(32767) becomes0xFFFF. So the range -32768..32767 lands on 0..65535, shifted up by exactly 32768, and subtracting 32768 shifts it back. Fort = 0xFFD8the XOR gives0x7FD8(32,728) and subtracting 32,768 gives -40. This avoids relying on casting an out-of-range value to a signed type, which is implementation-defined in C (each compiler must choose and document a behaviour; the standard does not fix one).
The signature the question asks for is pack_fields(sensor_id, temp, flags, &out) and unpack_fields(word, &sensor_id, &temp, &flags). Pack reports an error (returns -1) when sensor_id or flags do not fit, instead of silently cutting them off, because an oversized id would otherwise corrupt a neighbour field.
#include <stdint.h>
#include <stdio.h>
/* Part 1: two unsigned 16-bit fields in one 32-bit word. hi in bits 31..16, lo in bits 15..0. */
static uint32_t pack2(uint16_t hi, uint16_t lo) {
return ((uint32_t)hi << 16) | lo;
}
static void unpack2(uint32_t w, uint16_t *hi, uint16_t *lo) {
*hi = (uint16_t)(w >> 16);
*lo = (uint16_t)(w & 0xFFFFu);
}
/* Part 2: sensor_id 10 bits (31..22), temperature signed 16 bits (21..6), flags 6 bits (5..0). */
#define ID_BITS 10
#define TEMP_BITS 16
#define FLAG_BITS 6
#define FLAG_SHIFT 0
#define TEMP_SHIFT FLAG_BITS
#define ID_SHIFT (FLAG_BITS + TEMP_BITS)
#define MASK(bits) ((1u << (bits)) - 1u)
/* Returns 0 on success, -1 if id or flags do not fit their fields. */
static int pack_fields(uint32_t sensor_id, int16_t temp, uint32_t flags, uint32_t *out) {
if (sensor_id > MASK(ID_BITS) || flags > MASK(FLAG_BITS)) return -1;
uint32_t t = (uint32_t)(uint16_t)temp; /* reduce modulo 2^16: the two's complement bits */
*out = (sensor_id << ID_SHIFT) | (t << TEMP_SHIFT) | (flags << FLAG_SHIFT);
return 0;
}
static void unpack_fields(uint32_t w, uint32_t *sensor_id, int16_t *temp, uint32_t *flags) {
*sensor_id = (w >> ID_SHIFT) & MASK(ID_BITS);
uint32_t t = (w >> TEMP_SHIFT) & MASK(TEMP_BITS);
/* Sign extension without relying on implementation-defined conversions:
flip the sign bit, then subtract it back out. */
*temp = (int16_t)((int32_t)(t ^ 0x8000u) - 0x8000);
*flags = (w >> FLAG_SHIFT) & MASK(FLAG_BITS);
}
int main(void) {
uint16_t hi, lo;
uint32_t w = pack2(0xABCD, 0x1234);
unpack2(w, &hi, &lo);
printf("pack2 -> %08x, unpacked %04x %04x\n", w, hi, lo);
uint32_t id, flags, packed;
int16_t temp;
pack_fields(300, -40, 5, &packed);
unpack_fields(packed, &id, &temp, &flags);
printf("fields -> %08x id=%u temp=%d flags=%u\n", packed, id, temp, flags);
printf("temp -40 as 16 bits: %04x\n", (unsigned)(uint16_t)(int16_t)-40);
/* Common mistake: widen the signed temperature without cutting it to 16 bits first. */
uint32_t wrong = (300u << ID_SHIFT) | ((uint32_t)(int32_t)-40 << TEMP_SHIFT) | 5u;
unpack_fields(wrong, &id, &temp, &flags);
printf("no 16-bit mask -> %08x id=%u (was 300)\n", wrong, id);
printf("id too big : %d\n", pack_fields(1024, 0, 0, &packed));
printf("flags too big: %d\n", pack_fields(0, 0, 64, &packed));
/* Exhaustive on temperature, boundary values on id and flags. */
uint32_t ids[] = {0, 1, 511, 1023}, fl[] = {0, 1, 31, 63};
long checked = 0;
for (int ii = 0; ii < 4; ii++)
for (int fi = 0; fi < 4; fi++)
for (int32_t tv = -32768; tv <= 32767; tv++) {
uint32_t w2, id2, fl2;
int16_t t2;
if (pack_fields(ids[ii], (int16_t)tv, fl[fi], &w2) != 0) return 1;
unpack_fields(w2, &id2, &t2, &fl2);
if (id2 != ids[ii] || t2 != (int16_t)tv || fl2 != fl[fi]) {
printf("FAIL id=%u temp=%d flags=%u\n", ids[ii], tv, fl[fi]);
return 1;
}
checked++;
}
printf("round trips checked: %ld\n", checked);
return 0;
}
Output:
pack2 -> abcd1234, unpacked abcd 1234
fields -> 4b3ff605 id=300 temp=-40 flags=5
temp -40 as 16 bits: ffd8
no 16-bit mask -> fffff605 id=1023 (was 300)
id too big : -1
flags too big: -1
round trips checked: 1048576
Worked trace
Packing sensor_id = 300, temp = -40, flags = 5 gives 0x4b3ff605. Step by step, with ID_SHIFT = 22 and TEMP_SHIFT = 6:
sensor_id << 22: 300 is0x12C, and0x12C << 22is0x4B000000.t = (uint32_t)(uint16_t)-40 = 0xFFD8, and0xFFD8 << 6is0x003FF600.flags << 0is0x00000005.- OR of the three:
0x4B000000 | 0x003FF600 | 0x00000005 = 0x4B3FF605. The three ranges do not overlap, so OR loses nothing.
Unpacking the same word w = 0x4B3FF605: w >> 22 is 0x12C (300), already free of higher bits. For the temperature, w >> 6 is 0x12CFFD8; the mask MASK(16) = 0xFFFF keeps only the low 16 bits, 0xFFD8, and the sign-extension step then gives -40. w & MASK(6) is 0x05. Written out as bits:
| Part | Bits |
|---|---|
sensor_id 300, 10 bits | 0100101100 |
temp -40 as 16 bits (0xffd8) | 1111111111011000 |
flags 5, 6 bits | 000101 |
| Concatenated, grouped by 4 | 0100 1011 0011 1111 1111 0110 0000 0101 = 4 b 3 f f 6 0 5 |
The program unpacks the word back to the same three values, and the exhaustive loop confirms the claim for all 65,536 temperatures combined with the boundary values 0, 1, 511, 1023 for the id and 0, 1, 31, 63 for the flags (1,048,576 round trips).
Complexity
Pack and unpack are O(1) time and O(1) space: a fixed number of shifts, masks and ORs.
Why not C bit-fields
A struct with bit-fields (members declared with an explicit width in bits, such as unsigned id : 10;) looks simpler, but the C standard leaves the order in which fields are allocated within a word, and whether a field may straddle a boundary, to the implementation. The same struct can have a different bit layout under a different compiler or byte order (whether a machine stores the most significant byte of a number first or last), so for data that is stored or sent, explicit shifts and masks are the portable choice.
Edge cases and common mistakes
- Forgetting the mask on unpack leaves the upper fields' bits in the extracted value.
- Forgetting to cut a signed value to its width on pack (shown above).
- Shifting a signed
intinto the sign bit: undefined behaviour. Useuint32_tfor everything that is shifted. - Out-of-range inputs: the code rejects an id above 1023 or flags above 63. For the temperature the type
int16_talready constrains the range. - A shift count equal to or larger than the type width (for example a 32-bit shift on a
uint32_t) is undefined; the layout here keeps every shift below 32. - Hard-coded numbers: use named widths and shifts so changing a field width changes one line.
- Extending the layout: the shift of each field is the total width of the fields below it, so adding a field means recomputing the shifts and making sure the widths still sum to the word size.
Running the code
gcc -std=c11 -O2 -Wall -Wextra -fsanitize=undefined pack.c -o pack && ./pack
Compare std::bitset<N>, std::vector<bool> and a hand-rolled packed bit array in C++. When would you choose each, considering memory, speed of set, test and scan, and API surprises?
Sample Answer
Direct answer
All three can store one bit per flag, but they differ in who decides the size and how you scan. Use std::bitset<N> when N is a compile-time constant and you want a small, bounds-aware, operator-rich type. Use std::vector<bool> only when the size is decided at run time and you accept its quirks and slower, bit-at-a-time access. Use a hand-rolled array of 64-bit words when you need run-time size plus fast scanning, word-level operations, serialization or SIMD (single instruction, multiple data) access to the raw words.
What each one is
std::bitset<N> | std::vector<bool> | Packed array of uint64_t words | |
|---|---|---|---|
| Size | Fixed: N is a template parameter (a value written in angle brackets that the compiler fixes when it compiles), known at compile time | Run time, can resize and push_back | Run time (you write the resize) |
| Memory | About N/8 bytes rounded up to a whole word, no heap allocation by itself (1,000,000 bits: 125,000 bytes in the run below) | Packing is allowed but not guaranteed ("implementation defined" per cppreference); libstdc++ (the C++ standard library that ships with GCC) packs it, and the object also holds heap bookkeeping | Exactly ceil(n/64) words, 15,625 words (125,000 bytes) for 1,000,000 bits |
| Set / test | set, reset, flip, test, [], and whole-set &, |, ^, ~, shifts | v[i], flip, push_back; no whole-set operators | You write them: shift and mask, one machine instruction each |
| Scan for set bits | No iterator for set bits in the standard interface; loop test(i) over every index, or use a library extension | Same: loop over every index | Skip an all-zero word in one comparison, then peel set bits with countr_zero (count trailing zeros: the number of 0 bits below the lowest 1 bit, which is that bit's index) |
| Count set bits | count() | std::count (the standard does not promise a word-at-a-time version) | popcount per word, 15,625 calls for a million bits |
| Fits when | Flag sets known at build time; hash-table sized masks; small sieve | Run-time size, speed not critical, convenience matters | Large sparse sets, hot scans, set algebra, interop with raw words |
API surprises (each one is real, shown below)
std::vector<bool>is not a normal container.operator[]returns a small proxy object (a stand-in that remembers the word and bit; in libstdc++ it is a pointer to the word plus a mask, which is why the run printssizeof(proxy) = 16: 8 bytes each), sobool* p = &v[0]andauto& r = v[0]do not compile. In GCC 14.2 the errors arecannot convert 'std::vector<bool>::reference*' to 'bool*'andcannot bind non-const lvalue reference ... to an rvalue. It has nodata(), and generic code written forvector<T>that takes references breaks. Writes go through the proxy and do reach the vector.- Because it may not be a real container, concurrent writes to two different elements are a data race (two threads touching the same memory location with at least one write and no synchronisation, which makes the program's behaviour undefined; here they share a word), unlike
vector<int>where each element is its own location. bitset::operator[]does not check bounds;test(i)does and throwsstd::out_of_range.to_ulong()throwsstd::overflow_errorwhen a bit above the width ofunsigned longis set.- N cannot be chosen at run time: a
bitset<N>with a variable N does not compile, and a very large N can overflow the stack, the fixed-size memory area for local variables (8 MiB per thread is the common Linux default, checked withulimit -sin the test container; 125,000 bytes here is fine, tens of megabytes is not). - Both standard types miss "find next set bit". libstdc++'s
_Find_firstand_Find_nextdo it forbitset, but they are non-standard extensions (only GCC's library provides them), so portable code rolls its own.
How the word-skipping scan works
Take a 128-bit set with bits 3, 64 and 127 on. Stored as two 64-bit words, word 0 is 0x8 (only bit 3) and word 1 is 0x8000000000000001 (bits 0 and 63, which are flags 64 and 127). The loop in for_each_set does this:
| Step | Word | countr_zero(w) | Flag index wi * 64 + countr_zero | w &= w - 1 leaves |
|---|---|---|---|---|
| word 0, first bit | 0x8 | 3 | 0 * 64 + 3 = 3 | 0 (loop ends) |
| word 1, first bit | 0x8000000000000001 | 0 | 1 * 64 + 0 = 64 | 0x8000000000000000 |
| word 1, second bit | 0x8000000000000000 | 63 | 1 * 64 + 63 = 127 | 0 (loop ends) |
w & (w - 1) clears the lowest set bit because subtracting 1 turns that bit into 0 and every zero below it into 1, so AND zeroes exactly that run. A word that is already 0 skips the inner loop at once, which is the word skipping.
Code
#include <bit>
#include <bitset>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <vector>
// Hand-rolled packed bit array: dynamic size, raw 64-bit words, fast scan.
class PackedBits {
public:
explicit PackedBits(std::size_t n) : size_(n), words_((n + 63) / 64, 0) {}
void set(std::size_t i) { words_[i >> 6] |= (std::uint64_t{1} << (i & 63)); }
void reset(std::size_t i) { words_[i >> 6] &= ~(std::uint64_t{1} << (i & 63)); }
bool test(std::size_t i) const { return (words_[i >> 6] >> (i & 63)) & 1; }
std::size_t count() const {
std::size_t c = 0;
for (auto w : words_) c += std::popcount(w);
return c;
}
// Visit set bits, skipping empty words; counts how many words were examined.
template <class F> void for_each_set(F f, std::size_t& words_seen) const {
for (std::size_t wi = 0; wi < words_.size(); ++wi) {
++words_seen;
for (std::uint64_t w = words_[wi]; w; w &= w - 1)
f(wi * 64 + std::countr_zero(w));
}
}
std::size_t word_count() const { return words_.size(); }
private:
std::size_t size_;
std::vector<std::uint64_t> words_;
};
int main() {
constexpr std::size_t N = 1'000'000;
std::bitset<N> fixed;
std::vector<bool> dyn(N);
PackedBits packed(N);
std::cout << "sizeof(bitset<1000000>) = " << sizeof(fixed) << " bytes\n";
std::cout << "PackedBits words = " << packed.word_count() << " x 8 = "
<< packed.word_count() * 8 << " bytes\n";
for (std::size_t i : {3u, 64u, 999'999u}) { fixed.set(i); dyn[i] = true; packed.set(i); }
std::cout << "counts: " << fixed.count() << " " << packed.count() << "\n";
// API surprises
std::vector<bool> small{true, false};
auto r = small[1]; // a proxy object, not a bool
r = true; // writes through to the vector
std::cout << "proxy write-through: small[1] = " << small[1]
<< ", sizeof(proxy) = " << sizeof(r) << "\n";
// bool* p = &small[0]; // does not compile: no bool* exists
// auto& ref = small[0]; // does not compile: cannot bind a temporary
try { fixed.test(N); } catch (const std::out_of_range& e) { std::cout << "bitset::test(N) throws out_of_range\n"; }
try { fixed.to_ulong(); } catch (const std::overflow_error&) { std::cout << "to_ulong throws overflow_error (bit 999999 set)\n"; }
// Scan cost: bit-by-bit test versus word skipping, counted not timed
std::size_t bit_tests = 0, hits = 0;
for (std::size_t i = 0; i < N; ++i) { ++bit_tests; hits += dyn[i]; }
std::size_t words_seen = 0, found = 0;
packed.for_each_set([&](std::size_t) { ++found; }, words_seen);
std::cout << "bit-by-bit: " << bit_tests << " tests, " << hits << " hits\n";
std::cout << "word skip : " << words_seen << " words, " << found << " hits\n";
}
Run output (GCC 14.2, aarch64 Linux, libstdc++, compiled as in the last section; the sizes are implementation facts that can differ on another standard library):
sizeof(bitset<1000000>) = 125000 bytes
PackedBits words = 15625 x 8 = 125000 bytes
counts: 3 3
proxy write-through: small[1] = 1, sizeof(proxy) = 16
bitset::test(N) throws out_of_range
to_ulong throws overflow_error (bit 999999 set)
bit-by-bit: 1000000 tests, 3 hits
word skip : 15625 words, 3 hits
The scan numbers are counts of work, not times. Testing every index does 1,000,000 tests for 3 hits (the bit-by-bit line); the word-skipping scan examines 15,625 words (the word skip line) and peels each of the 3 set bits with countr_zero and w &= w - 1 (clear the lowest set bit). That is 64 times fewer examinations when the set is sparse, and the advantage shrinks toward nothing when most words contain bits, because every set bit still costs one step.
Choosing
- Compile-time size and mostly set operations (union, test, count):
std::bitset<N>. It does the word loops for you andcount()is built in. - Run-time size, simple use, not performance critical:
std::vector<bool>, understanding the proxy and that you must not rely on its layout. - Large, hot, scan-heavy, or needing raw words (network headers, memory-mapped files, SIMD, atomic words for concurrent updates): the packed
uint64_tarray. Concurrency is a real reason: withstd::atomic<uint64_t>words you canfetch_orone bit atomically (an OR that completes as one indivisible step, so no other thread sees a half-done update), which neither standard type offers. - What would flip the choice: if N is known only at run time but you want the
bitsetoperator set, use a library dynamic bitset (for exampleboost::dynamic_bitsetfrom the Boost C++ libraries), which cppreference itself names as the alternative.
Complexity and pitfalls
set,test,resetare O(1) for all three. Whole-set operations andcountare O(N/64) word operations forbitsetand the hand-rolled array (O(N) per-bit work forvector<bool>without a specialised algorithm).- The shipped scan is O(N/64 + k) for k set bits; testing every index is O(N).
- Space: N/8 bytes rounded up to a word, for the bitset and the packed array.
- Pitfalls:
i >> 6andi & 63needuint64_t{1}(not1) before the shift, or the shift happens in a 32-bitintand is undefined for any index of 32 or more; forgetting the last partial word's unused bits when you invert (~) and then count; mistakingvector<bool>for a container ofbool.
Running the code
g++ -std=c++20 -Wall -Wextra -O2 -fsanitize=undefined bitset_compare.cpp -o bitsets && ./bitsets
Needs C++20 for <bit> (std::popcount, std::countr_zero).
Every value in an integer array appears exactly twice except one that appears once. Find it in O(n) time and O(1) extra space, and explain why the method works.
Sample Answer
The idea
XOR (^) combines two bits and gives 1 only when they differ. It has three properties that solve this problem:
a ^ a = 0: a value cancels itself.a ^ 0 = a: zero changes nothing.- XOR is commutative and associative: commutative means
a ^ b = b ^ a(swapping operands changes nothing), associative means(a ^ b) ^ c = a ^ (b ^ c)(how you group them changes nothing). Together they let you reorder and regroup a whole array freely.
So if you XOR every element together, each value that appears twice cancels to 0 wherever it sits in the array, and what is left is 0 ^ single = single. For [4, 1, 2, 1, 2] the result is 4 ^ (1 ^ 1) ^ (2 ^ 2) = 4 ^ 0 ^ 0 = 4.
Why the obvious approaches are not enough
| Approach | Time | Extra space |
|---|---|---|
| Count with a dictionary or set | O(n) | O(n) |
| Sort, then compare neighbours | O(n log n) | O(1) to O(n), depending on the sort |
| XOR of everything | O(n) | O(1) |
The dictionary works but uses memory proportional to the number of distinct values, which the question rules out. Sorting breaks the O(n) time. XOR needs one integer and one pass.
Code
from functools import reduce
from operator import xor
def find_single(nums: list[int]) -> int:
result = 0
for x in nums:
result ^= x
return result
def find_single_traced(nums: list[int]) -> int:
result = 0
print(f"{'x':>3} {'x binary':>9} {'running xor':>12}")
for x in nums:
result ^= x
print(f"{x:>3} {x:>9b} {result:>7} = {result:b}")
return result
def find_two_singles(nums: list[int]) -> tuple[int, int]:
both = find_single(nums) # a ^ b, because every pair cancels
low = both & -both # lowest set bit of a ^ b: a and b differ there
a = 0
for x in nums:
if x & low: # this half holds exactly one of the two
a ^= x
return a, both ^ a
print(find_single_traced([4, 1, 2, 1, 2]))
print(find_single([7]), find_single([-3, 5, -3]), find_single([0, 9, 0]))
print(reduce(xor, [4, 1, 2, 1, 2]))
import random
from collections import Counter
random.seed(11)
for _ in range(500):
odd = random.randint(-20, 20)
others = [v for v in range(-20, 21) if v != odd]
pairs = random.sample(others, random.randint(0, 12))
data = pairs + pairs + [odd]
random.shuffle(data)
counts = Counter(data)
assert counts[odd] == 1 and find_single(data) == odd
print("checks passed")
data = [1, 2, 1, 3, 2, 5]
both = find_single(data)
low = both & -both
print(f"both = {both:b}, low = {low:b}")
print("with the bit set:", [x for x in data if x & low], "without:", [x for x in data if not x & low])
print(find_two_singles(data))
Output:
x x binary running xor
4 100 4 = 100
1 1 5 = 101
2 10 7 = 111
1 1 6 = 110
2 10 4 = 100
4
7 5 9
4
checks passed
both = 110, low = 10
with the bit set: [2, 3, 2] without: [1, 1, 5]
(3, 5)
Reading the output
The table is the real running XOR after each element. 4 gives 100. XOR with 1 gives 101 (5). XOR with 2 gives 111 (7). The second 1 flips bit 0 back, giving 110 (6). The second 2 flips bit 1 back, giving 100 (4). The pairs undid themselves and the unpaired 4 remains. The next line shows the edge cases: a single element returns itself, [-3, 5, -3] gives 5 (negative numbers work because XOR acts on the bit pattern and the pair still cancels), and [0, 9, 0] gives 9. functools.reduce with operator.xor is the same fold in one line. The last check compares the function with a Counter on 500 random arrays (fixed seed) that contain pairs plus one unpaired value, shuffled.
Complexity
Time O(n): one pass with one XOR per element. Space O(1): a single integer, no recursion and no auxiliary list. Each XOR is constant time for values that fit in a machine word.
Edge cases and mistakes
- A one-element array returns that element. An empty array returns 0, which only matters if the contract allows empty input; here exactly one value is unpaired, so the input is never empty.
- The method relies on the pairing guarantee. If a value can appear three times, or two different values appear once, the XOR is a mix and the result is wrong. With exactly two unpaired values
aandbthe XOR isa ^ b; to separate them, take any set bit of that XOR (for example the lowest,x & -x), split the array by that bit, and XOR each half. A set bit ofa ^ bis a position whereaandbdiffer, so exactly one of them has it, and each pair lands entirely in one half (both copies share that bit). Take[1, 2, 1, 3, 2, 5], where 3 and 5 are unpaired. The XOR of everything is3 ^ 5 = 110(6). Its lowest set bit is10(2). The elements with that bit set are[2, 3, 2], whose XOR is 3; the others are[1, 1, 5], whose XOR is 5. The last lines of the output showboth = 110, low = 10, those two groups, and the result(3, 5)fromfind_two_singles. - Using addition and subtraction ("2 times the sum of the set minus the sum of the array") needs a set, so it fails the O(1) space requirement.
Running the code
python single.py
A binary protocol packs a 3-bit version, 13-bit type, 20-bit length and further non-byte-aligned fields into a 64-bit header. Write pack and unpack code, and explain how you would make it correct on both big- and little-endian machines.
Sample Answer
The idea in plain words
There are two separate problems. The first is the bit layout: which bits of a 64-bit number belong to which field. That is shifts and masks (a mask is a number with 1s in the positions you want to keep, ANDed with a value to cut everything else off). The second is byte order (endianness): a 64-bit integer occupies eight bytes in memory, and a little-endian machine stores the least significant byte first while a big-endian machine stores the most significant byte first. A protocol fixes one order on the wire (the sequence of bytes actually sent over the network or written to a file), and code that copies the integer's memory straight into the packet gets the right bytes on one kind of machine and the reversed bytes on the other.
The fix for the second problem is to never look at how the host stores the integer. Build the 64-bit value with shifts, which operate on the number and not on its memory image, and write the bytes out one at a time with a shift per byte. The same source then produces the same bytes on every machine.
The layout
The question names three fields (3, 13 and 20 bits) and "further non-byte-aligned fields" that fill the other 28 bits. Here those further fields are flags (5 bits), channel (11 bits) and sequence (12 bits). The wire order is most significant byte first (big-endian, also called network byte order, the convention most internet protocols use), and the first field sits in the top bits.
| Field | Width | Bits (63 is the top) | Largest value |
|---|---|---|---|
| version | 3 | 63..61 | 7 |
| type | 13 | 60..48 | 8191 |
| length | 20 | 47..28 | 1,048,575 |
| flags | 5 | 27..23 | 31 |
| channel | 11 | 22..12 | 2047 |
| sequence | 12 | 11..0 | 4095 |
3 + 13 + 20 + 5 + 11 + 12 = 64. Fields such as type and length straddle byte boundaries (type covers the last 5 bits of byte 0 and all 8 bits of byte 1), which is why you cannot just copy bytes.
Approach
- Pack: reject any field that does not fit its width (otherwise an oversized value spills into its neighbour). Widen each field to
uint64_tfirst, because shifting a 16-bit or 32-bit value left by 48 or 61 would otherwise happen in a narrower type and lose bits or be undefined. Shift each field to its position and OR them together. - Serialize: byte
iof the packet is(word >> (56 - 8*i)) & 0xFF, so byte 0 carries bits 63..56. - Unpack: rebuild the word with
w = (w << 8) | bytefor bytes 0 to 7, then for each field shift down and mask.
Because both directions use the value of the integer and never its memory layout, the result does not depend on the machine.
Code (C)
#include <stdint.h>
#include <stdio.h>
#include <string.h>
/* Wire layout, most significant bit first (bit 63 is the first bit on the wire):
version 3 | type 13 | length 20 | flags 5 | channel 11 | sequence 12 = 64 bits */
typedef struct {
uint8_t version; /* 3 bits */
uint16_t type; /* 13 bits */
uint32_t length; /* 20 bits */
uint8_t flags; /* 5 bits */
uint16_t channel; /* 11 bits */
uint16_t sequence; /* 12 bits */
} Header;
#define VERSION_SHIFT 61
#define TYPE_SHIFT 48
#define LENGTH_SHIFT 28
#define FLAGS_SHIFT 23
#define CHANNEL_SHIFT 12
#define SEQUENCE_SHIFT 0
#define MASK(bits) ((UINT64_C(1) << (bits)) - 1)
/* Returns 0 on success, -1 if any field does not fit its width. */
static int pack_header(const Header *h, uint8_t out[8]) {
if (h->version > MASK(3) || h->type > MASK(13) || h->length > MASK(20) ||
h->flags > MASK(5) || h->channel > MASK(11) || h->sequence > MASK(12))
return -1;
uint64_t w = ((uint64_t)h->version << VERSION_SHIFT)
| ((uint64_t)h->type << TYPE_SHIFT)
| ((uint64_t)h->length << LENGTH_SHIFT)
| ((uint64_t)h->flags << FLAGS_SHIFT)
| ((uint64_t)h->channel << CHANNEL_SHIFT)
| ((uint64_t)h->sequence << SEQUENCE_SHIFT);
for (int i = 0; i < 8; i++) /* byte 0 is the most significant byte */
out[i] = (uint8_t)(w >> (56 - 8 * i));
return 0;
}
static void unpack_header(const uint8_t in[8], Header *h) {
uint64_t w = 0;
for (int i = 0; i < 8; i++) w = (w << 8) | in[i];
h->version = (uint8_t)((w >> VERSION_SHIFT) & MASK(3));
h->type = (uint16_t)((w >> TYPE_SHIFT) & MASK(13));
h->length = (uint32_t)((w >> LENGTH_SHIFT) & MASK(20));
h->flags = (uint8_t)((w >> FLAGS_SHIFT) & MASK(5));
h->channel = (uint16_t)((w >> CHANNEL_SHIFT) & MASK(11));
h->sequence = (uint16_t)((w >> SEQUENCE_SHIFT) & MASK(12));
}
static int same(const Header *a, const Header *b) { /* field by field: struct padding is not compared */
return a->version == b->version && a->type == b->type && a->length == b->length &&
a->flags == b->flags && a->channel == b->channel && a->sequence == b->sequence;
}
static void print_bytes(const char *label, const uint8_t b[8]) {
printf("%-26s", label);
for (int i = 0; i < 8; i++) printf(" %02x", b[i]);
printf("\n");
}
static uint64_t xorshift64(uint64_t *s) {
uint64_t x = *s;
x ^= x << 13; x ^= x >> 7; x ^= x << 17;
return *s = x;
}
int main(void) {
Header h = {5, 0x1ABC, 0xABCDE, 0x15, 0x5A5, 0xF0F};
uint8_t wire[8];
pack_header(&h, wire);
print_bytes("wire bytes:", wire);
const uint8_t expected[8] = {0xba, 0xbc, 0xab, 0xcd, 0xea, 0xda, 0x5f, 0x0f};
printf("matches expected bytes: %s\n", memcmp(wire, expected, 8) == 0 ? "yes" : "no");
/* The tempting shortcut: copy the host's 64-bit integer into the buffer. */
uint64_t as_integer = 0xbabcabcdeada5f0fULL;
uint8_t naive[8];
memcpy(naive, &as_integer, 8);
print_bytes("memcpy of the integer:", naive);
Header back;
unpack_header(wire, &back);
printf("unpacked: v=%u type=0x%x len=0x%x flags=0x%x ch=0x%x seq=0x%x\n",
back.version, back.type, back.length, back.flags, back.channel, back.sequence);
Header too_big = h;
too_big.type = 1u << 13;
printf("type = 8192 rejected: %d\n", pack_header(&too_big, wire));
uint64_t seed = 7;
for (int n = 0; n < 100000; n++) {
Header a = {
(uint8_t)(xorshift64(&seed) & MASK(3)), (uint16_t)(xorshift64(&seed) & MASK(13)),
(uint32_t)(xorshift64(&seed) & MASK(20)), (uint8_t)(xorshift64(&seed) & MASK(5)),
(uint16_t)(xorshift64(&seed) & MASK(11)), (uint16_t)(xorshift64(&seed) & MASK(12))};
Header b;
uint8_t buf[8];
if (pack_header(&a, buf) != 0) return 1;
unpack_header(buf, &b);
if (!same(&a, &b)) { printf("FAIL at %d\n", n); return 1; }
}
printf("100000 random round trips: ok\n");
return 0;
}
Output on a little-endian machine (aarch64 Linux, GCC 14.2, flags as in the last section; the memcpy line differs on a big-endian CPU, as the second run shows):
wire bytes: ba bc ab cd ea da 5f 0f
matches expected bytes: yes
memcpy of the integer: 0f 5f da ea cd ab bc ba
unpacked: v=5 type=0x1abc len=0xabcde flags=0x15 ch=0x5a5 seq=0xf0f
type = 8192 rejected: -1
100000 random round trips: ok
The same program compiled and run on a big-endian machine (IBM s390x, run under an emulator, which is software that imitates that processor so a laptop can run its programs; the results are the same as on real hardware, only slower):
wire bytes: ba bc ab cd ea da 5f 0f
matches expected bytes: yes
memcpy of the integer: ba bc ab cd ea da 5f 0f
unpacked: v=5 type=0x1abc len=0xabcde flags=0x15 ch=0x5a5 seq=0xf0f
type = 8192 rejected: -1
100000 random round trips: ok
Worked trace
The test header has version = 5, type = 0x1abc, length = 0xabcde, flags = 0x15, channel = 0x5a5, sequence = 0xf0f. In binary, field by field:
| Field | Bits |
|---|---|
| version | 101 |
| type | 1101010111100 |
| length | 10101011110011011110 |
| flags | 10101 |
| channel | 10110100101 |
| sequence | 111100001111 |
Concatenated, the 64 bits are 1011101010111100101010111100110111101010110110100101111100001111. Cut that string into groups of eight bits, one group per wire byte, and read each group as hex. Fields that straddle a byte boundary are split across two rows:
| Byte | Bits | Hex | Which field bits it holds |
|---|---|---|---|
| 0 | 10111010 | ba | version 101, then the top 5 bits of type (11010) |
| 1 | 10111100 | bc | the low 8 bits of type |
| 2 | 10101011 | ab | the top 8 bits of length |
| 3 | 11001101 | cd | the next 8 bits of length |
| 4 | 11101010 | ea | the last 4 bits of length (1110), then the top 4 bits of flags (1010) |
| 5 | 11011010 | da | the last bit of flags (1), then the top 7 bits of channel (1011010) |
| 6 | 01011111 | 5f | the low 4 bits of channel (0101), then the top 4 bits of sequence (1111) |
| 7 | 00001111 | 0f | the low 8 bits of sequence |
So the word is 0xbabcabcdeada5f0f and the wire bytes are ba bc ab cd ea da 5f 0f, which is what both machines print for "wire bytes" and what the comparison against the expected bytes (computed independently from the table above) confirms.
The same integer sits in memory in two different byte orders. Addresses grow left to right, and the integer is 0xbabcabcdeada5f0f:
| Machine | addr+0 | +1 | +2 | +3 | +4 | +5 | +6 | +7 |
|---|---|---|---|---|---|---|---|---|
| big-endian (most significant byte first) | ba | bc | ab | cd | ea | da | 5f | 0f |
| little-endian (least significant byte first) | 0f | 5f | da | ea | cd | ab | bc | ba |
A reader without a big-endian machine can check this table with Python: (0xbabcabcdeada5f0f).to_bytes(8, 'big').hex(' ') and .to_bytes(8, 'little').hex(' ') print the two rows. The line "memcpy of the integer" is the endianness bug in action. Copying the memory of the 64-bit integer gives 0f 5f da ea cd ab bc ba on the little-endian machine, the bytes reversed, and the correct bytes on the big-endian machine. Code with this line passes every test on a developer laptop and fails when it meets a big-endian peer, and the other way round if it was only ever tested against a big-endian one.
Making it correct on both big- and little-endian machines
- Use shifts and masks on integer values and write bytes individually, as
pack_headerdoes. - Do not
memcpyastruct, an integer, or a C bit-field struct onto the wire. The struct has padding bytes (unused filler bytes the compiler inserts between members so each starts at a convenient address; the code compares fields one by one for that reason), a host byte order, and an implementation-defined bit-field layout. - The platform helpers (
htobe64on Linux and BSD,htonllwhere provided; both mean "convert a 64-bit host integer to big-endian") exist but are not in standard C, and their availability and spelling differ by platform. The shift loop needs nothing. - Test it on a big-endian target or an emulator, not only by reasoning: the run above shows the identical wire bytes from both. Add a fixed test vector (a known header and its eight bytes) to the unit tests so the check runs everywhere.
- Writing bytes one at a time also avoids unaligned 64-bit loads and stores (reading or writing 8 bytes at an address that is not a multiple of 8, which some processors fault on or run slowly), and avoids pointer casts that break the C aliasing rules (the rule that an object may only be accessed through a pointer of a compatible type, which lets the compiler assume otherwise-cast accesses do not overlap and can produce wrong code when you break it).
Complexity
Pack and unpack are O(1): six shifts and ORs plus an 8-iteration byte loop. No extra space beyond the 8-byte buffer.
Edge cases and common mistakes
- Oversized field values:
type = 8192is rejected (printed-1) instead of overwritinglength. - Shifting a narrow type:
h->type << 48on auint16_tis computed as anint, which is undefined or truncating; cast touint64_tfirst, as the code does. - Using
1 << nfor a mask whennis 32 or more: writeUINT64_C(1) << n. - Mixing up bit order and byte order. Byte order is about the eight bytes of the integer; the bit positions inside the integer are the same on every machine, which is why shifts are safe.
- Memcmp on structs compares padding; compare field by field.
- Reading a packet shorter than 8 bytes must be rejected before
unpack_headeris called; the function trusts its caller to supply 8 bytes. - Validation after unpack: a protocol usually also requires checking that
versionis one you support and thatlengthis not larger than the buffer you have.
Running the code
gcc -std=c11 -O2 -Wall -Wextra -fsanitize=undefined header.c -o header && ./header
Unlock Full Question Bank
Get access to all 9 Bit Manipulation interview questions and detailed answers.
Sign in to ContinueJoin thousands of developers preparing for their dream job.