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 b

12. 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

PassDateGot itCloseBlankQuestions missed
1
2
3

↑ Back to Algorithms