These are the notes for Competitive Programming episode 17. We go one level below numbers, to the bits inside them. A hostel light switch explains XOR, and we build the bit operators &, |, ^, <<, >> from zero and watch them run. Then an original problem, Odd Bits, asks how many pairs of numbers have an XOR with an odd number of 1 bits. The brute force over every pair is correct but gets Time Limit Exceeded on 2·10^5 numbers. A small table shows the pattern, a short proof explains it (XOR cancels shared 1s two at a time), and the answer becomes odd × (n − odd) in O(n). After that: bitmasks (every subset of n items is a number), the __builtin toolbox (popcount, ctz, clz, popcountll, x & -x, x & (x - 1)), and three bugs with their real outputs. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.
The real-life hook: the hostel corridor switch
A hostel corridor has one light and a switch at each end. At night the light is off: call that 0.
- Press a switch: the light comes on. Press again: it goes off. A press does not set the light on or off. It toggles it.
- Three friends walk through and each presses a switch, in any order: Ravi, Amit, Neha, or Neha first. The final state is the same. Order doesn't matter.
- Only one thing decides the result: is the number of presses odd (light on) or even (light off)?
This toggle is called XOR in programming. Keep the switch in mind: almost every XOR trick is this picture.
Bits from zero
- A bit is one tiny switch inside the computer:
0or1. Anintis a row of 32 bits; along longhas 64. - Binary writes a number with powers of two. Reading from the right, the bits are worth 1, 2, 4, 8, … So
12 = 8 + 4 = 1100and10 = 8 + 2 = 1010.
The bit operators work on every bit position separately:
| Operator | Name | Rule for each bit | 12 with 10 |
|---|---|---|---|
a & b |
AND | 1 only if both bits are 1 | 1100 & 1010 = 1000 = 8 |
a | b |
OR | 1 if at least one bit is 1 | 1100 | 1010 = 1110 = 14 |
a ^ b |
XOR | 1 if the bits are different | 1100 ^ 1010 = 0110 = 6 |
1 << k |
shift left | moves bits k places left: 2^k | 1 << 3 = 1000 = 8 |
x >> k |
shift right | moves bits k places right: x / 2^k, remainder dropped | 12 >> 2 = 11 = 3 |
XOR is the light switch on every bit at once: a 1 in b toggles that bit of a, a 0 leaves it alone. That gives the three XOR facts you will use all the time:
x ^ x = 0(pressing twice puts you back)x ^ 0 = x(no press, no change)- order doesn't matter:
a ^ b ^ c = c ^ a ^ b(XOR is commutative and associative)
bitset<4>(x) prints the last 4 bits of x, and __builtin_popcount(x) counts its 1 bits (the popcount: popcount(12) = 2).
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int a = 12, b = 10;
cout << bitset<4>(a) << " a = 12\n";
cout << bitset<4>(b) << " b = 10\n";
cout << bitset<4>(a & b) << " a & b = " << (a & b) << "\n";
cout << bitset<4>(a | b) << " a | b = " << (a | b) << "\n";
cout << bitset<4>(a ^ b) << " a ^ b = " << (a ^ b) << "\n";
cout << (a ^ b ^ b) << " a ^ b ^ b\n";
cout << (1 << 3) << " 1 << 3\n";
cout << (a >> 2) << " a >> 2\n";
cout << __builtin_popcount(a) << " popcount(12)\n";
return 0;
}
Real output:
1100 a = 12
1010 b = 10
1000 a & b = 8
1110 a | b = 14
0110 a ^ b = 6
12 a ^ b ^ b
8 1 << 3
3 a >> 2
2 popcount(12)
a ^ b ^ b gives back 12: XOR with b twice cancels.
The problem: Odd Bits
Problem Q · Odd Bits (written for this course). You are given an array
aofnintegers,0 ≤ a[i] < 2^30. Count the pairsi < jsuch thata[i] ^ a[j]has an odd number of 1 bits.
1 ≤ t ≤ 10^4test cases,1 ≤ n ≤ 2·10^5, the sum ofnover all tests is at most2·10^5.
| Sample input | Sample output |
|---|---|
331 2 345 5 5 520 7 |
201 |
Check the first test by hand:
| Pair | XOR | Binary | 1 bits | Counted? |
|---|---|---|---|---|
| 1, 2 | 3 | 11 |
2 (even) | no |
| 1, 3 | 2 | 10 |
1 (odd) | yes |
| 2, 3 | 1 | 01 |
1 (odd) | yes |
Two odd pairs, so the answer is 2. Four equal fives give XOR 0 every time (0 bits, even): answer 0. 0 ^ 7 = 7 = 111 has 3 bits: answer 1.
The answer can be large: with n = 2·10^5 there are about 2·10^10 pairs, far more than an int holds (about 2.1·10^9). Use long long.
Brute force: every pair (Time Limit Exceeded)
Try every pair, XOR the two numbers, count the bits with __builtin_popcount, and check whether the count is odd.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
ll ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (__builtin_popcount(a[i] ^ a[j]) % 2 == 1)
ans++;
cout << ans << "\n";
}
return 0;
}
On the sample it prints 2 0 1: correct. But n can be 2·10^5. We can't paste that many numbers, so this version builds the worst case itself:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 200000; // worst case, built here
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = i * 7 + 3;
ll ans = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (__builtin_popcount(a[i] ^ a[j]) % 2 == 1)
ans++;
cout << ans << "\n";
return 0;
}
| Input | Output |
|---|---|
| the sample | 2 0 1 |
| no input (the program builds n = 2·10^5) | Time Limit Exceeded (it was still running after 8 seconds) |
Why: n²/2 = (2·10^5)² / 2 = 2·10^10 pairs, twenty billion. A judge does roughly 10^8 simple steps per second. O(n²) is hopeless here.
Step 1: print a small table
Same trick as episode 16: when you are stuck, print small cases and stare at them. For every pair a < b below 4, print the bit counts of a and b and of a ^ b:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
for (int a = 0; a < 4; a++)
for (int b = a + 1; b < 4; b++) {
int pa = __builtin_popcount(a), pb = __builtin_popcount(b);
int px = __builtin_popcount(a ^ b);
cout << a << "^" << b << " bits " << pa << "+" << pb
<< " xor bits " << px << (px % 2 ? " ODD" : "") << "\n";
}
return 0;
}
Real output:
0^1 bits 0+1 xor bits 1 ODD
0^2 bits 0+1 xor bits 1 ODD
0^3 bits 0+2 xor bits 2
1^2 bits 1+1 xor bits 2
1^3 bits 1+2 xor bits 1 ODD
2^3 bits 1+2 xor bits 1 ODD
In every ODD row one number has an even bit count and the other an odd one (0 + 1, 1 + 2). In 1^2 (1 + 1) and 0^3 (0 + 2) both counts have the same parity and the XOR is even.
Parity means "odd or even". The guess: popcount(a ^ b) is odd exactly when popcount(a) and popcount(b) have different parities.
Step 2: the proof
Take a = 12 and b = 10, bit by bit:
| bit 3 | bit 2 | bit 1 | bit 0 | 1 bits | |
|---|---|---|---|---|---|
a = 12 |
1 | 1 | 0 | 0 | 2 |
b = 10 |
1 | 0 | 1 | 0 | 2 |
a & b (shared 1s) |
1 | 0 | 0 | 0 | 1 |
a ^ b |
0 | 1 | 1 | 0 | 2 |
Together a and b have 2 + 2 = 4 ones. XOR keeps a 1 only where the bits differ. Where both bits are 1 (bit 3 here), both ones vanish together: always two at a time. So
popcount(a ^ b) = popcount(a) + popcount(b) − 2 · popcount(a & b)
2 = 2 + 2 − 2 · 1
Subtracting an even number never changes odd/even. So popcount(a ^ b) has the same parity as popcount(a) + popcount(b), and
- odd + even = odd,
- even + even = even, odd + odd = even.
Proved: the pair counts exactly when one number has an odd bit count and the other an even one.
From pairs to counting
Call a number ODD if its popcount is odd and EVEN otherwise. A pair counts ⇔ it has one ODD and one EVEN number. So we never need to look at pairs:
- Count the ODD numbers: call it
odd. The othern − oddare EVEN. - Every ODD number pairs with every EVEN number:
answer = odd × (n − odd)
Check on [1, 2, 3]: 1 and 2 have one bit each (ODD), 3 has two (EVEN). 2 × 1 = 2. Matches.
Step 3: the O(n) solution
__builtin_popcount(x) & 1 is the last bit of the count: 1 if the count is odd.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
ll odd = 0;
for (int x : a)
if (__builtin_popcount(x) & 1) odd++;
cout << odd * (n - odd) << "\n";
}
return 0;
}
| Input | Output | Why |
|---|---|---|
| the sample | 2 0 1 |
as computed above |
31921 251 2 4 8 16 |
000 |
one number has no pairs; 1 and 2 are both ODD (their XOR 11 has 2 bits); every power of two has exactly one bit, so there is no EVEN partner |
And the worst case that timed out:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 200000; // worst case, built here
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = i * 7 + 3;
ll odd = 0;
for (int x : a)
if (__builtin_popcount(x) & 1) odd++;
cout << odd * (n - odd) << "\n";
return 0;
}
Real output: 9999970759, instantly. Almost ten billion odd pairs, counted in 2·10^5 steps instead of 2·10^10.
Stress test
We proved the rule, but a stress test checks that the code matches the proof: run the brute force and the fast formula on many random small arrays and compare. mt19937 is C++'s random number generator; a fixed seed (17) makes the run repeatable.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll brute(vector<int> &a) {
ll ans = 0;
for (int i = 0; i < (int)a.size(); i++)
for (int j = i + 1; j < (int)a.size(); j++)
ans += __builtin_popcount(a[i] ^ a[j]) % 2;
return ans;
}
ll fast(vector<int> &a) {
ll odd = 0;
for (int x : a) odd += __builtin_popcount(x) & 1;
return odd * ((ll)a.size() - odd);
}
int main() {
mt19937 rng(17);
for (int it = 1; it <= 1000; it++) {
int n = rng() % 10 + 1;
vector<int> a(n);
for (auto &x : a) x = rng() % 1000;
if (brute(a) != fast(a)) {
cout << "DIFF on test " << it << "\n";
return 0;
}
}
cout << "OK: 1000 random tests agree\n";
return 0;
}
Real output: OK: 1000 random tests agree.
Part 2: bitmasks, subsets as numbers
Real-life example: a tick-box tiffin order. An office tiffin form lists 4 dishes (dal, rice, roti, salad), each with a tick box.
| Tiffin form | In code |
|---|---|
| a row of tick boxes | a mask: bit i = 1 ⇔ dish i is ticked |
| every possible way to fill the form (2^4 = 16) | for (mask = 0; mask < (1 << n); mask++): every subset, once |
| how many dishes were ordered | __builtin_popcount(mask): the subset's size |
A subset is any selection of items from a set, including none or all. With n items there are 2^n subsets, and the numbers 0 … 2^n − 1 list them all. A mask is a number used this way, each bit saying yes or no. To test bit i: mask >> i & 1 (shift bit i down to the last place, keep only that bit).
Problem: 4 dishes cost 30, 50, 70, 20 rupees. How many ways are there to pick exactly k = 2 dishes for at most B = 100 rupees?
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 4, k = 2, B = 100;
int price[] = {30, 50, 70, 20};
int ways = 0;
for (int mask = 0; mask < (1 << n); mask++) {
if (__builtin_popcount(mask) != k) continue;
int sum = 0;
for (int i = 0; i < n; i++)
if (mask >> i & 1) sum += price[i];
if (sum <= B) {
ways++;
cout << bitset<4>(mask) << " sum = " << sum << "\n";
}
}
cout << "ways = " << ways << "\n";
return 0;
}
Real output:
0011 sum = 80
0101 sum = 100
1001 sum = 50
1010 sum = 70
1100 sum = 90
ways = 5
Read each mask from the right: 0011 is dishes 0 and 1, 30 + 50 = 80. There are 6 pairs of dishes; the missing one, 0110 (dishes 1 and 2), costs 50 + 70 = 120 > 100.
The loop does 2^n · n steps: fine up to n ≈ 20 (about 2·10^7), hopeless beyond.
The builtin toolbox
GCC (the compiler behind g++) has built-in functions that work on bits in one step:
| Function / expression | What it gives | x = 40 = 00101000 |
|---|---|---|
__builtin_popcount(x) |
number of 1 bits | 2 |
__builtin_ctz(x) |
ctz, "count trailing zeros": zeros at the end (right) | 3 |
__builtin_clz(x) |
clz, "count leading zeros": zeros at the front of all 32 bits | 26 |
x & -x |
the lowest set bit (the rightmost 1) alone | 8 |
x & (x - 1) |
x with its lowest set bit removed |
32 |
__builtin_popcountll(y) |
popcount for a 64-bit long long |
1LL << 40 → 1 |
Why x & -x works: computers store -x as ~x + 1 (two's complement: flip every bit, add 1). The +1 carries through the trailing zeros of ~x and stops at the lowest 1 of x, so x and -x share exactly that one bit. Why x & (x - 1) works: subtracting 1 turns the lowest 1 into 0 and the zeros below it into 1s; AND with x wipes them all.
ctz and clz are undefined for 0: there is no 1 bit to find, so the result is meaningless. Check x != 0 first.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
unsigned x = 40;
cout << bitset<8>(x) << " x = 40\n";
cout << __builtin_popcount(x) << " popcount\n";
cout << __builtin_ctz(x) << " ctz (zeros at the end)\n";
cout << __builtin_clz(x) << " clz (zeros at the front)\n";
cout << (x & -x) << " x & -x (lowest 1 bit)\n";
cout << (x & (x - 1)) << " x & (x - 1) (drop it)\n";
long long y = 1LL << 40;
cout << __builtin_popcountll(y) << " popcountll(2^40)\n";
return 0;
}
Real output:
00101000 x = 40
2 popcount
3 ctz (zeros at the end)
26 clz (zeros at the front)
8 x & -x (lowest 1 bit)
32 x & (x - 1) (drop it)
1 popcountll(2^40)
clz is 26 because 40's highest 1 is bit 5, and 31 − 5 = 26. Each builtin also has an ll version for 64 bits: __builtin_ctzll, __builtin_clzll, __builtin_popcountll.
Solutions in C++, Java and Python
The full Odd Bits solution: count numbers with an odd popcount, print odd × (n − odd).
C++: the O(n) program in Step 3 above.
Java (tested: 2 0 1 on the sample, 0 0 0 on the edge cases, and 9999970759 on the 2·10^5-number worst case). Integer.bitCount is Java's popcount.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
int t = (int) st.nval;
StringBuilder out = new StringBuilder();
while (t-- > 0) {
st.nextToken();
int n = (int) st.nval;
long odd = 0;
for (int i = 0; i < n; i++) {
st.nextToken();
int x = (int) st.nval;
if ((Integer.bitCount(x) & 1) == 1) odd++;
}
out.append(odd * (n - odd)).append('\n');
}
System.out.print(out);
}
}
Python (tested with the same three inputs, same outputs). bin(x).count("1") is the popcount; on Python 3.10+ you can also write x.bit_count(). Python integers never overflow.
import sys
def main():
data = sys.stdin.buffer.read().split()
t = int(data[0])
pos = 1
out = []
for _ in range(t):
n = int(data[pos]); pos += 1
odd = 0
for i in range(pos, pos + n):
odd += bin(int(data[i])).count("1") & 1
pos += n
out.append(str(odd * (n - odd)))
print("\n".join(out))
main()
Brute force vs optimal
| Brute force (all pairs) | Parity count | Masks (all subsets) | |
|---|---|---|---|
| Time | O(n²) | O(n) (popcount is one machine instruction on modern CPUs) | O(2^n · n) |
| Extra memory | O(n) | O(n) (O(1) if you count while reading) | O(1) |
| n = 2·10^5 | ≈ 2·10^10 pair checks: TLE | 2·10^5 steps: instant | impossible |
| n = 20 | 190 pairs | 20 steps | ≈ 2·10^7 steps: fine |
Common mistakes (and the real outputs)
Bug 1: operator precedence. A friend counts the EVEN numbers instead (the answer is the same, even × (n − even)):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<int> a(n);
for (auto &x : a) cin >> x;
ll even = 0;
for (int x : a)
if (__builtin_popcount(x) & 1 == 0) even++;
cout << even * (n - even) << "\n";
}
return 0;
}
On the sample it prints 0 0 0 instead of 2 0 1, with no compiler warning. Operator precedence is the order in which C++ applies operators, and == binds tighter than &. So the condition is popcount(x) & (1 == 0) = popcount(x) & 0 = always 0. Write (__builtin_popcount(x) & 1) == 0.
Bug 2: overflow. The worst-case program with int odd instead of ll odd:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
int n = 200000; // worst case, built here
vector<int> a(n);
for (int i = 0; i < n; i++) a[i] = i * 7 + 3;
int odd = 0;
for (int x : a)
if (__builtin_popcount(x) & 1) odd++;
cout << odd * (n - odd) << "\n";
return 0;
}
Real output: 1410036167 instead of 9999970759. About 10^5 × 10^5 = 10^10 does not fit in an int (max 2147483647), so the product overflows: it wraps around (here, exactly 9999970759 − 2·2^32). No error, just a wrong answer. (Signed overflow is officially undefined behaviour in C++, so don't count on any particular wrong value.)
Bug 3: popcount on a long long. The toolbox program with one line changed:
cout << __builtin_popcount(y) << " popcount(2^40)\n";
Real output for that line: 0 popcount(2^40) (the other six lines are unchanged). __builtin_popcount takes a 32-bit unsigned int, so the 1 at bit 40 is cut off before counting. Use __builtin_popcountll.
| Mistake | What you see | Why | Fix |
|---|---|---|---|
if (__builtin_popcount(x) & 1 == 0) |
0 0 0 instead of 2 0 1 |
== binds tighter than & |
(__builtin_popcount(x) & 1) == 0 |
int odd; … odd * (n - odd) |
1410036167 instead of 9999970759 |
10^10 overflows int |
ll odd |
__builtin_popcount(1LL << 40) |
0 instead of 1 |
the argument is cut to 32 bits | __builtin_popcountll |
__builtin_ctz(0), __builtin_clz(0) |
a meaningless number, no error | undefined for 0 | check x != 0 first |
Rule of thumb: brackets around every bit operation, ll for big answers, ll builtins for 64-bit values, and never ctz/clz of zero.
Mini project
Build a bit inspector: read a number x (up to 10^18) and print its binary form (bitset<64>), popcount, parity, ctz, clz (only if x != 0), lowest set bit, x with that bit removed, and whether x is a power of two. Then treat x as a mask and list every subset of its 1 bits with for (ll s = x; s > 0; s = (s - 1) & x). Use ll and the ll builtins throughout, and test it on 0, 1, 40 and 1LL << 40.
Practice
-
(Homework 1) Every value in an array appears twice except one. Find it in O(n) time and O(1) extra memory.
Answer
XOR all the values. Each pair cancels (<code>x ^ x = 0</code>), order doesn't matter, and <code>0 ^ y = y</code>, so only the single value survives. For <code>{4, 7, 1, 7, 4}</code> the program <code>int x = 0; for (int v : a) x ^= v;</code> prints <code>1</code> (run and checked). -
(Homework 2) Count the pairs
i < jwhose XOR has an even number of 1 bits.Answer
A pair is even ⇔ both numbers are ODD or both are EVEN. With <code>even = n − odd</code>: answer = <code>odd·(odd − 1)/2 + even·(even − 1)/2</code> (equivalently, all n(n − 1)/2 pairs minus <code>odd·(n − odd)</code>). Use <code>long long</code>. Run on the sample it prints <code>1 6 0</code>; on the edge cases <code>0 1 10</code>. -
(Homework 3) Find the total number of 1 bits in all numbers from 1 to n, for n ≤ 10^18.
Answer
Count bit by bit. Bit k repeats a pattern of 2^k zeros then 2^k ones, every 2^(k+1) numbers. Among 0 … n there are <code>full = (n + 1) / 2^(k+1)</code> complete blocks giving <code>full · 2^k</code> ones, plus <code>max(0, (n + 1) % 2^(k+1) − 2^k)</code> from the leftover part. Sum over k = 0 … 59: O(log n). n = 10 gives 17, n = 7 gives 12, and n = 10^18 gives <code>29761222783429247000</code>, which is larger than the <code>long long</code> maximum (≈ 9.22·10^18), so the total must be kept in <code>__int128</code> (or Python). Checked against a brute force for every n below 5000. -
(Homework 4) With masks: n ≤ 20 weights; count the subsets whose sum is exactly S.
Answer
Loop <code>mask</code> from 0 to <code>(1 << n) − 1</code>, add <code>w[i]</code> for every bit <code>mask >> i & 1</code>, count the masks with sum == S. O(2^n · n). For weights <code>{2, 3, 5, 7, 8}</code> and S = 10 it prints <code>3</code>: {2, 8}, {3, 7}, {2, 3, 5}. -
How can you check in O(1) whether a positive integer is a power of two?
Answer
A power of two has exactly one 1 bit, and <code>x & (x − 1)</code> removes the lowest one, so: <code>x > 0 && (x & (x - 1)) == 0</code> (note the brackets!). Run on 1, 6, 64, 96 it prints YES, NO, YES, NO. <code>__builtin_popcount(x) == 1</code> also works.
Quick quiz
a = {3, 5, 6, 7}. How many Odd Bits pairs? (Bits: 3 = 011, 5 = 101, 6 = 110, 7 = 111.)
A) 0 · B) 2 · C) 3 · D) 4
Answer
C. 3, 5 and 6 have two 1 bits (EVEN), 7 has three (ODD). odd = 1, so the answer is 1 × 3 = 3. Both the brute force and the O(n) program print 3.
Interview questions
- What are the main properties of XOR?
x ^ x = 0,x ^ 0 = x, and it is commutative and associative, so a list of XORs can be done in any order and equal values cancel in pairs. - How do you find a unique or missing element with XOR? XOR everything: duplicates cancel. For "the missing number from 0 … n", XOR all of 0 … n together with all array values; every present number appears twice and cancels.
- How do you test, set, clear and toggle bit i? Test
(x >> i) & 1, setx | (1 << i), clearx & ~(1 << i), togglex ^ (1 << i)(use1LLfor i ≥ 31). - What does
x & (x - 1)do, and what is it used for? It removes the lowest set bit: checking powers of two, or counting bits by loopingwhile (x) { x &= x - 1; cnt++; }. - When are bitmask subsets a good idea? When n is about 20 or less: 2^20 ≈ 10^6 masks. For n ≈ 40, split in halves (meet in the middle, next episode).
- Why is
__builtin_ctz(0)dangerous? It is undefined behaviour: there is no 1 bit, so the result is meaningless and differs between machines.
Glossary
| Term | Meaning | Example |
|---|---|---|
| Bit | One binary digit, a switch that is 0 or 1 | an int has 32 bits |
| Binary | Writing numbers with powers of two (1, 2, 4, 8, … from the right) | 12 = 1100 |
AND (&) |
Bit is 1 only if both bits are 1 | 12 & 10 = 8 |
OR (|) |
Bit is 1 if at least one bit is 1 | 12 | 10 = 14 |
XOR (^) |
Bit is 1 if the bits differ: a toggle | 12 ^ 10 = 6, x ^ x = 0 |
| Toggle | Switch between two states | light off → on → off |
Shift left (<<) |
Move bits left; 1 << k = 2^k |
1 << 3 = 8 |
Shift right (>>) |
Move bits right; divides by 2^k, dropping the remainder | 12 >> 2 = 3 |
bitset<k>(x) |
Prints the last k bits of x | bitset<4>(12) → 1100 |
| Popcount | Number of 1 bits | __builtin_popcount(12) = 2 |
| Parity | Whether a number is odd or even | popcount 3: odd parity |
| ODD / EVEN number (this episode) | A number whose popcount is odd / even | 7 is ODD, 3 is EVEN |
| Commutative, associative | Order and grouping do not change the result | a ^ b ^ c = c ^ a ^ b |
| Mask | An integer whose bits mean yes/no for each item | 0011 = dishes 0 and 1 |
| Subset | Any selection of items (none, some or all) | 4 items → 16 subsets |
mask >> i & 1 |
Tests whether bit i of mask is 1 | 5 >> 2 & 1 = 1 |
| ctz | Count trailing zeros (zeros at the end) | __builtin_ctz(40) = 3 |
| clz | Count leading zeros (zeros at the front of 32 bits) | __builtin_clz(40) = 26 |
popcountll, ctzll, clzll |
The 64-bit (long long) versions |
__builtin_popcountll(1LL << 40) = 1 |
| Lowest set bit | The rightmost 1 bit, alone: x & -x |
40 & -40 = 8 |
x & (x - 1) |
x with its lowest set bit removed | 40 & 39 = 32 |
| Two's complement | How negatives are stored: -x = ~x + 1 |
why x & -x works |
unsigned |
An integer type with no negative values | unsigned x = 40; |
| Overflow | A value too big for its type wraps around | int product → 1410036167 |
long long (ll) |
64-bit integer, up to about 9.2·10^18 | ll odd |
__int128 |
128-bit integer in g++, for even bigger values | homework 3's total |
| Operator precedence | The order operators are applied in | x & 1 == 0 means x & (1 == 0) |
| Undefined behaviour | C++ makes no promise about the result | __builtin_ctz(0) |
| Brute force | Try every possibility; slow but surely correct | all n²/2 pairs |
| Time Limit Exceeded (TLE) | The program ran longer than the judge allows | brute force at n = 2·10^5 |
| Observation | A fact about the problem that makes it easy | "only parities matter" |
| Stress test | Compare a fast solution with a brute force on many random inputs | 1000 random arrays |
mt19937 |
C++ random number generator | mt19937 rng(17) |
| Sum of n constraint | A limit on the total size of all test cases | sum n ≤ 2·10^5 |
Summary
- Bits from zero:
&(both),|(either),^(different),<<(×2^k),>>(÷2^k), checked live withbitset. - XOR is a toggle:
x ^ x = 0,x ^ 0 = x, order doesn't matter. - Odd Bits: the O(n²) brute force got TLE at n = 2·10^5.
- A small table and a proof:
popcount(a ^ b) = popcount(a) + popcount(b) − 2·popcount(a & b), so parity survives XOR. - Answer
odd × (n − odd)in O(n):9999970759instantly; 1000 random tests agreed with the brute force. - A mask is a subset: loop to
1 << n, size = popcount, fine up to n ≈ 20. - Builtins:
popcount,ctz,clz,popcountll,x & -x,x & (x - 1). - Real bugs:
& 1 == 0(0 0 0),intoverflow (1410036167), popcount onlong long(0).
Next episode: Meet in the middle.