Unit 11 — Number Systems, Bitwise & Number Theory

Slide 1 of 39

A light panel stores all of its on/off switches as one integer. How can you flip switch 3 without touching the rest? This unit reads the bits inside an integer, changes selected bits with masks, uses masks to represent subsets, and builds several number-theory tools by hand. Each idea is a short executable demo with a Notice, then a full stdin solver.
- Convert numbers between decimal, binary and hexadecimal by hand.
- Test, set, clear and flip single bits with &, |, ^, ~, << and >>.
- List every subset of a small set with one bitmask per subset.
- Compute a GCD and LCM, sieve for primes, and keep answers small with % m.
Lesson 1 — Write Numbers in Binary & Hex, and Work with Bits

Convert decimal to binary by hand: repeatedly take % 2 (the low bit) and // 2 (drop it), building the digits from the right (no bin()).

number = 42
digits = "0123456789ABCDEF"
binary = ""
remaining = number
while remaining > 0:
    binary = digits[remaining % 2] + binary
    remaining = remaining // 2
print(binary)

Output

42 → 101010; each step peels off one bit with % 2 and shrinks the number with // 2.

Convert binary back to decimal with a place-value loop: value = value * 2 + next_bit.

binary_text = "101010"
value = 0
position = 0
while position < len(binary_text):
    value = value * 2 + int(binary_text[position])
    position = position + 1
print(value)

Output

Reading left to right, doubling then adding each bit rebuilds 42.

HEXADECIMAL is base 16 with digits 0–9 then A–F for 10–15: build it with % 16 / // 16.

number = 687
digits = "0123456789ABCDEF"
hexadecimal = ""
remaining = number
while remaining > 0:
    hexadecimal = digits[remaining % 16] + hexadecimal
    remaining = remaining // 16
print(hexadecimal)

Output

2AF

687 → 2AF (2·16² + 10·16 + 15); the digit 10 prints as A, 15 as F. Reading hex back to decimal uses place value with base 16.

Store switches AS BITS. 1 << k masks bit k. TEST with & mask, SET with | mask, CLEAR with & (full_mask ^ mask), FLIP with ^ mask; complement within a width with ~x & full_mask; shift with << / >>.

state = 5
width = 4
full_mask = (1 << width) - 1
bit = 1 << 2
is_on = 0
if state & bit:
    is_on = 1
print("bit 2 on?", is_on)
print("set:", state | bit)
print("clear:", state & (full_mask ^ bit))
print("flip:", state ^ bit)
print("complement:", ~state & full_mask)
print("shift:", state << 1, state >> 1)
print("x ^ x:", state ^ state)

Output

bit 2 on? 1
set: 5
clear: 1
flip: 1
complement: 10
shift: 10 2
x ^ x: 0

state & bit is a NONZERO int when the bit is on — Python treats any nonzero int as True, so if state & bit: works. CLEAR keeps every OTHER bit via full_mask ^ bit; ~ alone would give an infinite-width negative, so the width mask is required. And x ^ x == 0, so XOR-ing paired values cancels them (used in Exercise 4).
Put it together: the program reads a decimal number plus a binary and a hex string, and prints the number in binary, in hex, and the two strings' decimal values.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
number = int(tokens[0])
binary_text = tokens[1]
hexadecimal_text = tokens[2]
digits = "0123456789ABCDEF"

if number == 0:
    binary = "0"
else:
    binary = ""
    remaining = number
    while remaining > 0:
        digit = remaining % 2
        binary = digits[digit] + binary
        remaining = remaining // 2

if number == 0:
    hexadecimal = "0"
else:
    hexadecimal = ""
    remaining = number
    while remaining > 0:
        digit = remaining % 16
        hexadecimal = digits[digit] + hexadecimal
        remaining = remaining // 16

binary_value = 0
position = 0
while position < len(binary_text):
    binary_value = binary_value * 2 + int(binary_text[position])
    position = position + 1

hexadecimal_value = 0
position = 0
while position < len(hexadecimal_text):
    character = hexadecimal_text[position]
    digit_value = 0
    while digits[digit_value] != character:
        digit_value = digit_value + 1
    hexadecimal_value = hexadecimal_value * 16 + digit_value
    position = position + 1
print(binary + "\n" + hexadecimal + "\n" + str(binary_value) + "\n" + str(hexadecimal_value))

Run the full solver from this unit folder:
```
python assets/l1.py < assets/l1/1.in
```
Repeated % base / // base builds each representation; a place-value loop reads each string back to decimal.

Complexity: O(log number) per conversion.
Lesson 2 — One Mask per Subset, GCD & LCM

Every subset of n items matches one integer mask in 0 .. (1<<n)-1: bit i set means item i is included.

values = [2, 4, 8]
n = 3
for mask in range(1 << n):
    subset_total = 0
    index = 0
    while index < n:
        if mask & (1 << index):
            subset_total = subset_total + values[index]
        index = index + 1
    print(mask, subset_total)

Output

The 8 masks 0..7 enumerate all subsets of 3 items; mask & (1 << i) tests membership.

Euclid's algorithm: gcd(a, b) = gcd(b, a % b) until the remainder is 0.
```
a = 18
b = 24
while b != 0:
    a, b = b, a % b
print(a)
```
Scroll the code for more ↓
Output
```
6
```
18 and 24 reduce to 6 — the loop stops when b reaches 0 (written b != 0).
LCM from GCD: a // gcd * b (divide first to avoid a big intermediate).

a = 18
b = 24
x = a
y = b
while y != 0:
    x, y = y, x % y
gcd = x
print(a // gcd * b)

Output

18 // 6 * 24 = 72 — the least common multiple.

Put it together: the program reads a target and n values and prints how many SUBSETS sum to the target, by testing every mask.

Try it

import sys

data = sys.stdin.read()
tokens = data.split()
n = int(tokens[0])
target = int(tokens[1])
values = []
index = 0
while index < n:
    values.append(int(tokens[index + 2]))
    index = index + 1
matching_count = 0
for mask in range(1 << n):
    subset_total = 0
    index = 0
    while index < n:
        if mask & (1 << index):
            subset_total = subset_total + values[index]
        index = index + 1
    if subset_total == target:
        matching_count = matching_count + 1
print(str(matching_count))

Run the full solver from this unit folder:
```
python assets/l2.py < assets/l2/1.in
```
Iterate every mask 0..(1<<n)-1; sum the items whose bit is set; count the masks hitting the target.

Complexity: O(2^n · n) — only feasible for small n.
Lesson 3 — Sieve Many Primes & Reduce Modulo as You Go

The Sieve of Eratosthenes marks composites: start all True, then for each prime p, mark p*p, p*p+p, … as not prime.

n = 20
is_prime = []
i = 0
while i <= n:
    is_prime.append(True)
    i = i + 1
is_prime[0] = False
is_prime[1] = False
p = 2
while p * p <= n:
    if is_prime[p]:
        multiple = p * p
        while multiple <= n:
            is_prime[multiple] = False
            multiple = multiple + p
    p = p + 1
print(is_prime[7], is_prime[9])

Output

True False

7 stays prime (True) while 9 is marked composite (False) by p = 3.

Then collect the numbers still marked prime.

n = 20
is_prime = []
i = 0
while i <= n:
    is_prime.append(True)
    i = i + 1
is_prime[0] = False
is_prime[1] = False
p = 2
while p * p <= n:
    if is_prime[p]:
        multiple = p * p
        while multiple <= n:
            is_prime[multiple] = False
            multiple = multiple + p
    p = p + 1
primes = []
value = 2
while value <= n:
    if is_prime[value]:
        primes.append(value)
    value = value + 1
print(primes)

Output

[2, 3, 5, 7, 11, 13, 17, 19]

The survivors up to 20 are [2, 3, 5, 7, 11, 13, 17, 19].
Modular power: REDUCE % m after every multiply so the running value never grows large — squaring current and consuming one exponent bit each step.

base = 7
modulus = 13
exponent = 5
answer = 1 % modulus
current = base % modulus
while exponent > 0:
    if exponent & 1:
        answer = answer * current % modulus
    current = current * current % modulus
    exponent = exponent >> 1
print(answer)

Output

7^5 mod 13 stays small throughout; reducing as you go keeps every product under m (no astronomically large intermediate).

Put it together: the program reads N and prints how many primes are ≤ N, using one sieve.

Try it

import sys

data = sys.stdin.read()
n = int(data.strip())
is_prime = []
index = 0
while index <= n:
    is_prime.append(True)
    index = index + 1
if n >= 0:
    is_prime[0] = False
if n >= 1:
    is_prime[1] = False
p = 2
while p * p <= n:
    if is_prime[p]:
        multiple = p * p
        while multiple <= n:
            is_prime[multiple] = False
            multiple = multiple + p
    p = p + 1
prime_count = 0
value = 2
while value <= n:
    if is_prime[value]:
        prime_count = prime_count + 1
    value = value + 1
print(str(prime_count))

Run the full solver from this unit folder:
```
python assets/l3.py < assets/l3/1.in
```
Mark composites with a sieve, then count the True entries from 2 to N.

Complexity: O(N log log N).
A Number-Tools Checklist

(1) Convert by hand with % base / // base (no bin/hex); (2) read/set bits with & | ^ and 1 << k, complement within a width with ~x & ((1<<w)-1); (3) one mask per subset; (4) Euclid for GCD, a//gcd*b for LCM; (5) sieve for many primes; (6) reduce % m after every multiply.
- Repeated % base and // base builds the digits; a place-value loop reads them back.
- 1 << k is the mask for bit k; clear with & (full_mask ^ mask) and complement with ~x & full_mask.
- The masks 0 to (1 << n) - 1 list all subsets, and mask & (1 << i) tests whether item i is in.
- Euclid repeats a, b = b, a % b until b is 0; the LCM is a // gcd * b.
- A sieve crosses off multiples from p * p; reducing % m after every multiply keeps values small.
You can now use number systems, bitmasks and number-theory tools in contest problems.

Unit 11 — Number Systems, Bitwise & Number Theory

Lesson 1 — Write Numbers in Binary & Hex, and Work with Bits

Lesson 2 — One Mask per Subset, GCD & LCM

Lesson 3 — Sieve Many Primes & Reduce Modulo as You Go

A Number-Tools Checklist