Python Bit Operations: XOR, Masks, bit_count, and Submasks

Why This Matters

Bit operations are a compact way to represent sets, parity, flags, and subset states. Python makes them easy to write, but the code only stays readable when every bit has a named meaning.

Use this page after Bit manipulation when you want Python-specific drills rather than only the abstract pattern.

Core Idea

An integer can be treated as a row of bits. Each bit position can encode membership, a boolean flag, or a small piece of state.

Need	Python move	Cost intuition
Count set bits	`int.bit_count()`	proportional to integer size
Measure width	`int.bit_length()`	number of bits needed for magnitude
Toggle duplicate parity	`XOR` with `^`	identical values cancel
Build a mask	`1 << i`	bit `i` becomes active
Test bit `i`	`mask & (1 << i)`	nonzero means present
Clear lowest set bit	`x & (x - 1)`	common loop for set bits
Isolate lowest set bit	`x & -x`	used in Fenwick trees

Non-Example or Failure Mode

Do not use a mask when a normal set is clearer and the state is not small. Bitmasks work best when indexes are dense, stable, and limited enough that 2^n state is acceptable.

Python also uses arbitrary-precision integers. That is useful, but it means negative-number bit behavior does not match fixed-width unsigned arithmetic unless you explicitly mask to a width.

Worked Example

Suppose bit 0 means "seen read permission", bit 1 means "seen write permission", and bit 2 means "seen execute permission".

READ = 1 << 0
WRITE = 1 << 1
EXECUTE = 1 << 2

flags = READ | EXECUTE
has_write = bool(flags & WRITE)
flags ^= EXECUTE

The integer is not magic. It is just a compact flag set with named bits.

Prefix XOR

Prefix XOR works like prefix sums, but the operation is XOR instead of addition. If px[i] is the XOR of values before index i, then the XOR of values[left:right] is:

px[right] ^ px[left]

This works because duplicated prefixes cancel.

Common Mistakes

Mistake	Correction
Writing bit tricks without naming bit positions.	Define constants or document the index-to-meaning map.
Confusing `^` with exponentiation.	In Python, `^` is XOR. Exponentiation is `**`.
Forgetting parentheses in bit tests.	Prefer `if mask & (1 << i):` or `bool(mask & (1 << i))`.
Assuming Python negatives are fixed-width.	Mask explicitly with `(1 << width) - 1` when width matters.
Using subset masks for large `n`.	`2^n` states grow quickly. Check constraints before coding.

Diagnostic Questions

Question type	Question	Answer signal
Definition	What does `int.bit_count()` return?	The number of one bits in the integer's binary representation.
Example / non-example	Is `2 ^ 5` exponentiation in Python?	No. It is XOR. `2 ** 5` is exponentiation.
Computation	What does `x & (x - 1)` do when `x > 0`?	It clears the lowest set bit.
Transfer	Why does prefix XOR answer range XOR queries?	The shared prefix cancels because `a ^ a = 0`.

Runnable Drill

Python bit operation drill

Checks bit_count, bit_length, XOR cancellation, prefix XOR, flags, and submask iteration.

Output will appear here.

Exercises

Beginner:

Use int.bit_count() to count active flags.
Print the binary form of 37 with bin and format.
Explain why x ^ x disappears in a longer XOR chain.

Intermediate:

Implement prefix XOR range queries.
Enumerate all submasks of a mask and explain why the loop terminates.

Challenge:

Implement a small permission system using named bit flags, then write tests for set, clear, toggle, and membership.

Diagram Recommendation

Type: bit-position map.

Caption: "A Python integer used as named flags: bit 0 read, bit 1 write, bit 2 execute."

Purpose: Keep the state mapping visible so bit code does not become opaque.

Next Topics

References

Python documentation. Bitwise operations: https://docs.python.org/3/reference/expressions.html#binary-bitwise-operations
Python documentation. Integer methods: https://docs.python.org/3/library/stdtypes.html#int.bit_count
Python documentation. Built-in functions bin and format: https://docs.python.org/3/library/functions.html