ITPEC FE Morning October 2021 Question 2

Bitwise AND as modulo — find the remainder of division by a power of 2.

To get x mod 2ⁿ, perform x AND (2ⁿ - 1):

• •8 = 2³, so the mask is 2³ - 1 = 7 (00000111 in binary)
• •x AND 7 keeps only the lowest 3 bits — exactly the remainder of x ÷ 8

Example: x = 19 → 10011 AND 00111 = 00011 = 3, and 19 mod 8 = 3 ✓

Why not others:
- (b) AND 248 — 248 = 11111000, clears the low 3 bits instead of keeping them (gives the rounded-down multiple of 8)
- (c) OR 8 — OR sets bits, result is always ≥ 8, but remainder must be < 8
- (d) OR 15 — OR only adds 1-bits, result is always ≥ 15

Key rule: x mod 2ⁿ = x AND (2ⁿ - 1) — AND with a bitmask extracts the remainder for any power-of-2 divisor.

AI-generated — may contain errors