Micro-questions over the bit manipulation module. Answer in a full sentence before opening the toggle. Format explained in the arrays bank.
A. The mental model
1. Give the physical metaphor for an 8-bit integer.
Answer
A row of 8 light switches. Bit 0 is the least significant, bit 7 the most.
2. What operation turns a switch on, off, and flips it?
Answer
On: OR. Off: AND NOT. Flip: XOR.
3. Name four real applications.
Answer
Network subnet masks (IP & MASK); Linux file permissions as 3-bit groups (read=4, write=2, execute=1); 32 independent game state flags in one integer; XOR-based stream ciphers and hashes.
B. The operators
4. Define AND, OR and XOR by their output rule.
Answer
AND (&): 1 only if both inputs are 1. OR (|): 1 if either is 1. XOR (^): 1 only if the inputs differ.
5. What does ~x equal?
Answer
It flips every bit, which in two’s complement means . In Python ~5 = -6, not 2.
6. What do << and >> do arithmetically?
Answer
<< n multiplies by ; >> n divides by (floor), discarding the low bits.
C. XOR
7. Give the three properties of XOR.
Answer
(identity); (self-cancelling); commutative and associative — order does not matter.
8. What is the consequence for an array?
Answer
XOR everything together and every value appearing an even number of times cancels to 0, leaving only the odd-count survivor.
9. Trace [4,1,2,1,2].
Answer
.
10. What does that buy over a hash set?
Answer
time at space instead of .
11. Swap two integers using only XOR.
Answer
a = a ^ b
b = a ^ b # now b = original a
a = a ^ b # now a = original b12. When does the XOR trick fail?
Answer
When the unique element appears an even number of times, or when the duplicates appear 3 times rather than 2. Then you need bit-count-mod-3 tricks.
D. The idioms
13. Check whether bit is set.
Answer
(x >> i) & 1
14. Set, clear and toggle bit .
Answer
Set: x | (1 << i). Clear: x & ~(1 << i). Toggle: x ^ (1 << i).
15. Test even or odd.
Answer
x & 1 — 0 is even, 1 is odd.
16. Test whether x is a power of two.
Answer
x > 0 and (x & (x - 1)) == 0 — exactly one bit set.
17. Clear the lowest set bit, and isolate it.
Answer
Clear: x & (x - 1). Isolate: x & (-x).
E. Brian Kernighan
18. Why does x & (x - 1) clear exactly the lowest set bit?
Answer
Subtracting 1 flips the lowest set bit to 0 and all bits below it to 1. ANDing with the original then clears that bit and all below it.
19. Trace it on 12.
Answer
(cleared bit 2); (cleared bit 3). Count = 2.
20. What is the cost, and why is it better than the naive loop?
Answer
where is the number of set bits — rather than looping all 32 regardless.
F. Costs
21. Give the four complexity rows.
Answer
Single bit op: — a direct hardware instruction. Kernighan count: , space. XOR single-number: , space. Bitmask DP: time, space — for .
G. Traps
22. What is wrong with x & 1 == 0?
Answer
Bitwise operators bind looser than ==, so it evaluates as x & (1 == 0) = x & False = 0. Write (x & 1) == 0.
23. What breaks in Python for 32-bit problems?
Answer
Python integers have unlimited bit width with no natural overflow. Problems like “Reverse Bits” need explicit & 0xFFFFFFFF masking.
24. Summarise the module in one sentence.
Answer
Treat an integer as a row of switches — XOR cancels pairs, x & (x-1) erases the lowest set bit, and every idiom is one hardware instruction.
Scorecard
| Pass | Date | Got it | Close | Blank | Questions missed |
|---|---|---|---|---|---|
| 1 | |||||
| 2 | |||||
| 3 |
Related
Software engineering
Infrastructure & security
Computer science
Hardware & engineering