Topic notebook / 07
Bits & binary
Bit masks, shifts and XOR express work on the binary representation of integers.
What to look for
- State the bit width and signedness.
- Track carries and discarded bits.
- Distinguish numeric value from its representation.
Work through a question
5 availableAdd Two Byte Counters
Add two unsigned byte counters without + or - in the addition algorithm. Return their 8-bit wrapped sum, from 0 to 255. Variant: unsigned 8-bit arithmetic replaces the original signed-integer domain; overflow wraps modulo 256.
Medium / XOR sum and shifted carry / interactiveCount Enabled Byte Switches
A byte describes eight on/off switches. Return how many are enabled. Variant: the display and input use unsigned 8-bit values rather than a 32-bit word.
Easy / Clear the lowest set bit / interactiveBuild a Small Switch Lookup Table
Return the number of enabled bits for every counter value from 0 through the inclusive maximum. Original lookup-table scenario; the counting-bits contract is unchanged. The educational maximum is 31.
Easy / Bit-prefix dynamic programming / interactiveFind the Unscanned Ticket
Tickets were numbered 0 through n, but exactly one is absent from the n scanned IDs. Return the missing ID. Original ticket scenario; the task is unchanged. IDs must be distinct.
Easy / XOR cancellation / interactiveMirror an Eight-Switch Panel
Reverse all eight positions of an unsigned byte and return the resulting integer. Variant: exactly 8 bits, not 32; leading zeros are real positions and must be reversed too.
Easy / Shift and append bits / interactiveWhere this leads
Return to the roadmap to try a different kind of problem.