Bit Manipulation Practice Test for Competitive Programming
A timed 45-minute check on bitmasks: set, clear, toggle and test bits, XOR pairs, popcount, subset masks, and a per-bit counting problem in C++.
- Course: Competitive Programming study plan
- Module: Bit manipulation
- Kind: Checkpoint — cleared at 70%
- Reading time: 45 min
- Runtime: Clang 18 · C++20
Checkpoint — Bit manipulation is the checkpoint that closes the Bit manipulation module: a graded quiz and whole-program exercises, passed at 70%.
Instructions
The bit manipulation checkpoint. It is timed: 45 minutes from when you start it.
What it covers. Setting, clearing, toggling and testing bits; x & (x − 1) and x & −x; 1LL << i past bit 30; XOR's cancelling pairs; popcount; and walking every subset as a mask.
How it works. Eleven questions and one program. Clear 70% of the questions and get the program accepted. Its hidden cases hold thousands of numbers, so comparing every pair is far slower than counting one bit position at a time.
Before you start, make sure you can say from memory:
- the expression for each of set, clear, toggle and test;
- which elements mask 13 selects;
- how many pairs differ in a bit where c of the n numbers have a 1.
Common questions
What does the bit manipulation checkpoint test?
The one-line bit operations and their pitfalls, XOR cancelling pairs, popcount and the lowest-bit tricks, reading a mask as a subset, and one program — the total Hamming distance of every pair — judged at contest limits.
Exercise
Total Hamming distance
The Hamming distance of two numbers is the number of bit positions where they differ — popcount(x ^ y). Print the sum of the Hamming distances over all pairs i < j.
Constraints: 1 ≤ n ≤ 2·10⁵, 0 ≤ aᵢ < 2³⁰.
Input: n, then the n numbers. Output: the total.
3
4 14 2prints
6(4 and 14 differ in 2 bits, 4 and 2 in 2, 14 and 2 in 2.)
Every pair is O(n²) = 2·10¹⁰ at the limits — think per bit instead.
In this module: Bit manipulation
← Bit tricks for contests · Binary search on the answer — guess, check, halve →