Bit Manipulation and Math Checkpoint
A review of this module. Skip it if you feel confident; the next module does not need it.
Fix the mistakes
The slips that cost marks in this module. Spot each one, then check the fix.
This checkpoint mixes the whole module. For each task decide first which idea fits: a bit trick, a mask over subsets, a sieve, a GCD or a modular power. Then write it, and say what it costs.
Bit tricks at a glance
Population count, or popcount, is the number of 1 bits in an integer. In Python it is int.bit_count() from version 3.10.
Four quick facts about a number n: its bits, how many are set, its lowest set bit, and whether it is a power of two. Each is one expression.
n = 40print(bin(n), n.bit_count(), n & -n, (n & (n - 1)) == 0)Example 1 · Find the unpaired ticket
from functools import reducefrom operator import xor
tickets = [1042, 2210, 1042, 3307, 2210]print(reduce(xor, tickets))3307
What this code does
- Each ticket id was logged twice except one. XOR cancels the pairs.
- The answer is 3307, found in one pass with O(1) extra memory.
It prints 0b101000, 2 set bits, a lowest set bit of 8, and False, because 40 has two set bits and is not a power of two.
Masks over a small list
When a list has about 20 items or fewer and you must look at every subset, a mask loop is short. Here it counts the subsets of numbers whose GCD is 1.
import math
nums = [6, 10, 15]count = 0for mask in range(1, 1 << len(nums)): chosen = [nums[i] for i in range(len(nums)) if (mask >> i) & 1] if math.gcd(*chosen) == 1: count += 1print(count)Example 2 · Primes with exactly two set bits
import math
limit = 30flags = [True] * (limit + 1)flags[0] = flags[1] = Falsefor p in range(2, math.isqrt(limit) + 1): if flags[p]: for m in range(p * p, limit + 1, p): flags[m] = Falseprint([p for p in range(limit + 1) if flags[p] and p.bit_count() == 2])[3, 5, 17]
What this code does
- The sieve gives the primes, and
bit_countfilters them. - Primes that are the sum of two powers of two: 3 (2+1), 5 (4+1) and 17 (16+1).
Only the full set has GCD 1: every pair shares a factor, and no single number has GCD 1.
Big answers need a modulus
A sum of big powers is fine in Python, but problems ask for the answer modulo a number. Use three-argument pow for each power and reduce the total at the end.
MOD = 1_000_000_007primes = [p for p in range(2, 50) if all(p % d for d in range(2, p))]print(sum(pow(p, 50, MOD) for p in primes) % MOD)Example 3 · Divide under a prime modulus
MOD = 998_244_353print(84 * pow(12, -1, MOD) % MOD)7
What this code does
- Division becomes multiplication by the inverse of 12.
- Because 12 divides 84 exactly, the answer is the real quotient, 7.
The list holds the primes below 50. pow(p, 50, MOD) never builds the huge power, and the sum is reduced once at the end.
Module quiz
Questions from the whole module. Your first answer is your score.
Problems
Graded easy to hard, using everything from this module.
Try each one yourself first. Use the hint if you get stuck. Mark it as done when it works.
Exercise 1· Easy
For n = 2024 print its binary form, then its number of set bits, on two lines.
0b11111101000 7
Exercise 2· Easy
Print the GCD and the LCM of the three numbers 12, 18 and 30 on one line, separated by a space.
6 180
Exercise 3· Easy
In ids = [7, 3, 5, 3, 7] find the id that appears once, using XOR, and print it.
5
Exercise 4· Medium
Count the subsets of [1, 2, 3, 4, 5, 6] whose sum is divisible by 3, including the empty subset. Print the count.
24
Exercise 5· Medium
Use a sieve to print how many primes there are up to 100, and their sum, on one line separated by a space.
25 1060
Exercise 6· Medium
Print 7 to the power 10**12, modulo 1,000,000,007.
978283177
Exercise 7· Hard
Print how many integers from 1 to 100 are powers of two, then how many integers from 0 to 63 have exactly 3 set bits.
7 20
Exercise 8· Hard
Print the smallest power of two that is at least 1000, then the same for 1024, using bit_length and a shift, not a loop. Two lines.
1024 1024
Interview questions
Questions interviewers ask on this topic.
Finish up
Mark complete & continue
Next: Must-do problems: Bit Manipulation and Math