Bitwise Mastery
AND, OR, XOR, shifts, flags, masks, tricks
- › Know exactly what AND, OR, XOR, NOT, and the shifts do, bit by bit
- › Build the four flag idioms: set, clear, toggle, and test a specific bit
- › Use shifts for fast multiply/divide by powers of two and for packing values
- › Read and write bit-manipulation code fluently, as a reflex
Treating a number as a row of switches
Everything since day 1 has said: a value is a row of bits. The bitwise operators let you work on those bits directly — set one, clear one, test one, pack several values into a single integer. This is everywhere in systems and security: permission flags, hardware registers, network protocols, compression, hashing, and countless exploit primitives. Today you make these idioms reflexive.
| Op | C | Rule (per bit) |
|---|---|---|
| AND | a & b | 1 only if BOTH bits are 1 — used to select/mask bits |
| OR | a | b | 1 if EITHER bit is 1 — used to set bits |
| XOR | a ^ b | 1 if the bits DIFFER — used to toggle/flip bits |
| NOT | ~a | flip every bit (one's complement) |
| shift left | a << n | move bits up n places (fills 0 at bottom) = ×2ⁿ |
| shift right | a >> n | move bits down n places = ÷2ⁿ (unsigned) |
&&/|| (logical, whole-value true/false, short-circuiting) are not &/|
(bitwise, per-bit). 1 && 2 is 1 (both truthy); 1 & 2 is 0 (no common bits: 01 & 10). Mixing
them up is a classic bug. Bitwise works on the bits; logical works on the truthiness of the whole
value.The four idioms — the heart of the lesson
A mask is a value with 1s in the positions you care about. To operate on "bit n", the mask is
1 << n (a single 1 shifted into position n). With that, the four essential operations:
mask = 1 << n (a 1 in position n, 0 elsewhere)
SET bit n: x = x | mask // force it to 1 (OR)
CLEAR bit n: x = x & ~mask // force it to 0 (AND with inverted mask)
TOGGLE bit n: x = x ^ mask // flip it (XOR)
TEST bit n: (x >> n) & 1 // -> 0 or 1 (the day-1 idiom)Read the logic, don't memorize the lines. Set: OR with a 1 forces that bit to 1 and leaves
others alone (OR with 0 is a no-op). Clear: ~mask is all 1s except position n; ANDing keeps
every other bit and forces n to 0. Toggle: XOR with 1 flips, XOR with 0 leaves alone. Test:
shift the bit down to position 0 and mask with 1 — exactly the (b >> i) & 1 you wrote on day 1.
These four cover almost all bit work.
1enum { READ = 1<<0, WRITE = 1<<1, EXEC = 1<<2 }; // 1, 2, 4 — one bit each2 3int perms = 0;4perms |= READ | WRITE; // set READ and WRITE -> 0b011 = 35int can_exec = (perms >> 2) & 1; // test EXEC -> 06perms &= ~WRITE; // clear WRITE -> 0b001 = 17perms ^= EXEC; // toggle EXEC on -> 0b101 = 5That's a permission set packed into one integer — precisely how Unix file modes, page-table entries,
and countless config flags work. Each flag is a distinct power of two (one bit), so they combine with
OR and are tested with AND. You've probably seen chmod numbers; now you know they're bitmasks.
Shifts are multiply and divide by powers of two
Shifting left by n multiplies by 2ⁿ; shifting right by n divides by 2ⁿ (for unsigned / non-negative).
x << 3 is x * 8; x >> 1 is x / 2. The CPU does shifts in a single fast instruction, which is
why compilers turn x * 8 into x << 3 (you may have seen this on day 7's stretch). Shifts also
pack: to store two 16-bit values in a 32-bit int, (hi << 16) | lo; to unpack, (v >> 16) for
hi and v & 0xFFFF for lo.
x = 0b0110 (6). Compute, one at a time: x | (1<<0), then from the original x & ~(1<<1), then
from the original x ^ (1<<2). Give each result in binary and decimal.a ^ a == 0 and a ^ 0 == a, so XOR is its own inverse — apply the same key
twice and you're back to the original. That's the seed of the simplest cipher, the xor eax, eax
zeroing idiom (day 10), and clever tricks like swapping two variables with no temporary. XOR's
"records the difference" nature makes it uniquely useful.Own the four idioms
In bits.c: write set_bit, clear_bit, toggle_bit, and test_bit functions (each taking a value and a bit index), using masks and the rules from this lesson — no if-statements. Test them by building a permissions integer from named flags (READ/WRITE/EXEC as 1<<0/1<<2), setting, clearing, toggling, and testing, printing the value in binary each step. Then add a pack/unpack pair that stores two bytes in a 16-bit int and recovers them. Predict every result before running. Uses only this lesson plus day 1.
$ gcc -Wall bits.c -o bits && ./bits- › set/clear/toggle/test each touch only the target bit
- › Your permissions example combines flags with | and tests with &
- › Your pack/unpack round-trips two values through one integer
- › You predicted each result from the per-bit rules before running