Skip to content
Tech Interview Prep
Technical interview guide

Bit Manipulation

Working directly on a number's binary representation with AND/OR/XOR/shifts: for O(1) tricks and memory-efficient state.

Read
40 min
Practice MCQs
25
Interview Q&A
25
Edition
v7
Editorial status
Reviewed

Scope: Language-neutral, with integer semantics cited from CPython 3.14, java.util as of Java 21, and the C++ standard library.

Curated: · Written: · Reviewed:

25 questions

MCQ-1A telemetry protocol defines one byte as a signed 8-bit temperature delta. A capture shows that byte as 0xF6. What value does a receiver that interprets the field as a signed integer report?
MCQ-2A BFS over a 6-node graph (IDs 0–5) keeps the frontier and visited sets as bitmasks, node k at bit (1 << k). At one step `frontier = 0b101001` and `visited = 0b011010`. The code must compute the set of frontier nodes that have not yet been visited, so it can enqueue them. Which mask is that set?
MCQ-8A scheduler picks the lowest-numbered active shard from a 64-bit bitmap with `low = x & -x`. A refactor replaced that with `low = x & (x - 1)`. For a host whose bitmap is 0x0000_0000_0000_00D6, what does the refactored expression return?
MCQ-22A dedup service compares 64-bit SimHash fingerprints and flags a pair as a near-duplicate when the Hamming distance is ≤ 3. It computes the distance with the Kernighan loop: ```c int distance(uint64_t a, uint64_t b) { uint64_t x = a ^ b; int n = 0; while (x) { x &= x - 1; n++; } return n; } ``` The service compares a = 0x000000000000000F with b = 0x0000000000000003. How many times does the loop body execute, what distance is returned, and is the pair flagged?
MCQ-14A routine must call `visit` once for each set bit of a 64-bit word `x`, which starts at `0x000000000000002C` (bits 2, 3 and 5 set). The routine runs: ```c while (x) { uint64_t low = x & -x; x &= low; visit(low); } ``` What does this loop do?
MCQ-7A slab allocator tracks free slots in an 8-bit mask: bit i set means slot i is free. To hand out the next slot it runs this Python 3 code: ```python slot = (mask & -mask).bit_length() - 1 mask &= mask - 1 ``` With `mask = 0b10110100`, which slot index is handed out and what is the mask afterwards?
MCQ-6A job scheduler stores a 64-bit `state` word per job, with bit 5 as the paused flag; monitoring reports a job paused when `state & (1 << 5)` is nonzero. The resume handler runs `state ^= (1 << 5)`. After a deploy, monitoring reports a handful of jobs as paused that were never paused. What explains it?
MCQ-3A Java service scales a signed 32-bit ADC reading before packing it into a byte stream: `int scaled = reading >> 3;` with `reading = -25`. A reviewer signs off on the change, writing that `reading >> 3` is equivalent to `reading / 8`. What does the shift produce, and is the reviewer right?
MCQ-13A routine enumerates the submasks of a nonzero mask m with `for (int sub = m; ; sub = (sub - 1) & m)`, running the body once per submask. Which statement about what the loop visits, when it must stop, and why the update yields the next value is correct?
MCQ-5An algorithm iterates through every bitmask m from 0 up to (1 << n) - 1, and for each mask executes the inner loop `for (int sub = m; sub > 0; sub = (sub - 1) & m)` to visit all of its submasks. What is the total time complexity across all masks, and why?
MCQ-12A permissions service packs each role's grants into a 64-bit mask over a fixed universe of 64 permissions, and a request is allowed only when the caller's mask a is a subset of the role's mask b. Which expression tests that condition, and what makes it correct?
MCQ-10A log-verification job XORs the key column of a batch to find records whose commit marker was lost; each record normally writes its key twice. For one batch the column is 34, 17, 34, 51, 17, 51, 88, 99 and the job reports 59. What does the report mean?
MCQ-11A function returns the two values that occur exactly once in an array where every other value occurs exactly twice. For `a = [2, 3, 5, 3, 2, 9]` it computes `x = 2 ^ 3 ^ 5 ^ 3 ^ 2 ^ 9`, sets `bit = x & -x`, XORs into `g1` every element `v` with `v & bit` set, and returns `(g1, x ^ g1)`. What does it return?
MCQ-19A Go service on x86-64 writes a 4-byte length prefix with binary.LittleEndian, then the payload. A Java consumer reads the prefix with DataInputStream.readInt(). For a 1-byte payload the consumer logs a length of 16777216 and then blocks waiting for 16 MiB that never arrives. What is the cause?
MCQ-16A service stores permissions as integers from a Python `enum.Flag` that uses `auto()`. After adding `SHARE = auto()` between `WRITE` and `DELETE`, a user whose stored permission integer is 8 can now delete records. What is the cause?
MCQ-4A Java service (OpenJDK 17, HotSpot) builds a cache key with `long key = (shardId << 32) | sequence;`, where shardId and sequence are both int. The comment above the line says it packs the shard id into the high 32 bits so that keys from different shards never collide. With shardId = 7 and sequence = 100, what does the expression evaluate to?
MCQ-21A Python service must emit a signed 16-bit protocol field: the low 16 bits of the product of two signed 16-bit inputs, read back as a signed 16-bit integer. The current code is `(a * b) & 0xFFFF`. For a = 500 and b = 500, what must the function return?
MCQ-15A C99 hot loop computes `int q = x / 8;` where x is a signed int that takes both negative and positive values. An engineer replaces it with `int q = x >> 3;`, arguing the shift avoids a division. The code is built with gcc -O2 on x86-64. Which assessment is correct?
MCQ-25A log pipeline processes 400 million events per batch. Each event's eight severity levels are stored as a `uint8_t` bitmask, and a filter keeps events matching any requested level with `(event.mask & filter.mask) != 0`. In the same pipeline a hot loop computes `bucket = id / 8`, where `id` is a `uint64_t`. A performance engineer proposes two edits: (1) replace the severity bitmask with a `std::array<bool, 8>`, and (2) replace `id / 8` with `id >> 3`. Which of the two edits should the team apply?
MCQ-17A service tracks membership over a fixed universe of 10,000,000 account IDs. About 8,000,000 are active at any moment, the set is updated continuously, and the hot path repeatedly intersects and unions two of these sets. Which structure do you specify?
MCQ-24A C file defines this function and is compiled with `gcc -O2` in a separate translation unit without link-time optimization: ```c void xor_swap(int *a, int *b) { *a ^= *b; *b ^= *a; *a ^= *b; } ``` Another file calls `xor_swap(&arr[3], &arr[3]);` where `arr[3]` is 40. What is `arr[3]` after the call, and why?
MCQ-9A hash table sizes its bucket array with this function: ```python def next_pow2(n): n -= 1 n |= n >> 1 n |= n >> 2 n |= n >> 4 n |= n >> 8 n |= n >> 16 return n + 1 ``` A stress test constructs the table with `initial_capacity = 2**32 + 1`. The constructor calls `next_pow2(initial_capacity)` and allocates that many buckets. What capacity does the table allocate?
MCQ-18A 4096-bucket hash table indexes 64-bit keys with `bucket = (key * 0x9E3779B97F4A7C15) & 4095`. The keys are byte offsets of 4 KiB pages, so every key is a multiple of 4096. Where do the keys land?
MCQ-20A C service is built with gcc -O2 for x86-64. `int32_t` is 32-bit two's complement, and gcc -O2 assumes signed overflow does not occur. It parses an attacker-controlled 32-bit big-endian length: ```c int32_t len = (int32_t)ntohl(hdr->len); int32_t total = len + 16; if (total < len) return -EINVAL; /* intended overflow guard */ uint8_t *buf = malloc(total); if (!buf) return -ENOMEM; memcpy(buf, payload, len); ``` A fuzzer sends len = 0x7FFFFFFF. What does the function do?
MCQ-23A routing service solves TSP with Held-Karp: `dp[mask][last]` holds one 8-byte cost per (subset, last stop), and the whole table is allocated before the first query. At n = 20 the table is 160 MiB and the service runs in a 512 MiB container. The team wants the largest n that still fits in that container. Which n do they ship?