Skip to content
Tutorials Center
My learning

Topics

Lesson 176 of 225 ยท Math and Bit Manipulation

Bit Manipulation

Learn bit manipulation in Python: AND, OR, XOR, shifts, two's complement, set and clear bits, counting bits, power of two, single number and bitmask subsets.

Every integer in your computer is a row of bits, 0s and 1s. Bit manipulation means working on those bits directly, with operators that act on each bit position at once. It looks like a bag of party tricks, and some of it is, but it also gives real wins: a set of up to 64 items in one integer, a parity check without a loop, and some of the neatest interview solutions you will see.

This lesson starts from zero. You will learn the six operators, how negative numbers look inside, the handful of patterns that cover most problems, and then use them to find a lone number in a list and to list every subset with a bitmask.

Bits and binary

A number is written in base 2 by place value, just like base 10 but with powers of two:

TEXT
13 in binary:   1    1    0    1
place value:    8    4    2    1      ->  8 + 4 + 0 + 1 = 13
bit index:      3    2    1    0      (bit 0 is the rightmost, the "least significant")

Python writes binary literals with 0b, and shows them with bin() or the format spec b.

Python Reading numbers in binary

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The six operators

Each operator works bit by bit, on the numbers lined up by position.

Operator Name Rule 12 op 10 (1100 op 1010)
a & b AND 1 only if both bits are 1 1000 = 8
a | b OR 1 if at least one bit is 1 1110 = 14
a ^ b XOR 1 if the bits differ 0110 = 6
~a NOT flips every bit ~12 = -13
a << k left shift moves bits left, fills zeros 12 << 2 = 48
a >> k right shift moves bits right 12 >> 2 = 3

Shifting left by k multiplies by 2**k, and shifting right divides by 2**k, rounding down.

Python The operators on 12 and 10

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Negative numbers: two's complement in Python

In hardware with a fixed width such as 8 bits, a negative number is stored in two's complement: take the bits of the positive number, flip them, and add 1. That is why ~a == -a - 1.

TEXT
 5  = 00000101
~5  = 11111010   -> read as signed 8-bit: -6
-5  = ~5 + 1 = 11111011

Python integers are different. They have unlimited size and behave as if the sign bit were extended forever to the left, so -5 is "infinitely many 1s followed by 011". That means bin(-5) prints -0b101 (the sign and the magnitude), not a bit pattern, and ~x never overflows.

When you need fixed-width behavior (checksums, simulating 32-bit math, interview problems that say "32-bit integer"), apply a mask with &:

Python Masking to see two's complement

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In C, C++ or Java, right shift and overflow follow the machine word. In Python there is no overflow, so a problem that expects wrap-around (such as adding 1 to 2**31 - 1) needs an explicit mask. Forgetting it is the most common reason a bit solution works in one language and loops forever in Python.

Everyday bit patterns

Name a bit by its index i, counting from 0 at the right. The mask 1 << i has a single 1 at that position. Combine it with the operators:

Goal Expression
Test bit i (n >> i) & 1 or n & (1 << i) != 0
Set bit i to 1 n | (1 << i)
Clear bit i to 0 n & ~(1 << i)
Toggle bit i n ^ (1 << i)
Is n odd? n & 1
Clear the lowest set bit n & (n - 1)
Isolate the lowest set bit n & -n
Python Test, set, clear and toggle a bit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Counting set bits

How many 1s does a number have (its popcount or Hamming weight)?

Brute force: test every bit with a shift, O(log n) steps (one per bit).

Brian Kernighan's trick: n & (n - 1) clears the lowest set bit, because subtracting 1 flips that bit to 0 and all the zeros below it to 1s:

TEXT
n      = 101100
n - 1  = 101011
n&(n-1)= 101000     one 1 gone

Loop until n is 0, counting iterations. It does one step per set bit, not per bit position.

Python Three ways to count set bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Python 3.10 and newer has int.bit_count(), which is the idiomatic choice. The loops are worth knowing because they come up in interviews and the same trick drives other problems.

Power of two

A positive power of two has exactly one set bit: 1000...0. Subtracting 1 turns it into 0111...1, so the AND is 0.

TEXT
8      = 1000
8 - 1  = 0111
8 & 7  = 0000   -> power of two
6 & 5  = 0100   -> not
Python Power of two check

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The n > 0 guard matters: 0 & -1 == 0 would otherwise report zero as a power of two.

The XOR toolbox

XOR has three algebraic properties that make clever solutions possible:

  • a ^ a == 0 (a number cancels itself)
  • a ^ 0 == a
  • it is commutative and associative, so order does not matter

Single number

Every value in a list appears twice except one. Find it. Brute force counts with a dictionary (O(n) time, O(n) space). XOR all values: pairs cancel, and what remains is the lone value, using O(1) extra space.

TEXT
[4, 1, 2, 1, 2]:   4 ^ 1 ^ 2 ^ 1 ^ 2
                 = 4 ^ (1 ^ 1) ^ (2 ^ 2)
                 = 4 ^ 0 ^ 0 = 4
Python Find the single number with XOR

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Swapping and missing numbers

a ^= b; b ^= a; a ^= b swaps two integers without a temporary, but in Python a, b = b, a is clearer and just as fast. A more useful trick: for numbers 0..n with one missing, XOR the list with the full range; everything cancels except the missing value.

Python Missing number by XOR

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two single numbers

Now two values appear once and all others appear twice. XOR of everything gives x ^ y (the pairs cancel), which is nonzero because x != y. Any set bit in x ^ y is a position where x and y differ. Pick the lowest one with d & -d, split the numbers into two groups by that bit, and XOR each group separately: each group holds one of the singles plus complete pairs.

Python Two non-repeating numbers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Position of the only set bit

When n is a power of two it has exactly one set bit, and the bit position is log2(n). In Python n.bit_length() - 1 gives it in O(1); loop-based versions shift right until n becomes 0. Check the power-of-two condition first, otherwise the answer is meaningless.

Python Index of the only set bit

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bitmasks: a set in one integer

If your universe has up to a few dozen items, one integer can store any subset: bit i is 1 when item i is in the set. Set operations become single instructions.

Set operation Bit expression
Union a | b
Intersection a & b
Difference a & ~b
Contains i (a >> i) & 1
Size a.bit_count()

Enumerating all subsets

For n items there are 2**n subsets, and the integers 0 to 2**n - 1 each describe exactly one of them. So a simple loop lists every subset:

TEXT
items = [a, b, c]
mask  cba   subset
 0    000   {}
 1    001   {a}
 2    010   {b}
 3    011   {a, b}
 4    100   {c}
 5    101   {a, c}
 6    110   {b, c}
 7    111   {a, b, c}
Python All subsets with a bitmask

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

This runs in O(n * 2^n) time: 2^n masks, each scanned over n bits. It is the same count as the recursive version, and the bitmask loop is simple and iterative. Bitmasks also power bitmask dynamic programming and quick "visited set" encodings.

A related loop lists the submasks of a mask m without scanning every integer:

Python Enumerate submasks of a mask

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

More bit tricks: multiplying, rotating, byte order and subarray XOR

Multiply without *: the Russian peasant method

Write b in binary. Then a * b is the sum of a << i over every set bit i of b. Looping over the bits of b, doubling a each step, multiplies in O(log b) additions and shifts. Adding a % m inside the loop gives modular multiplication that never builds a huge intermediate number, which matters in languages with fixed-width integers.

Python Russian peasant multiplication

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Rotating bits

A shift throws bits away. A rotation moves bits that fall off one end back in at the other. Python integers have no fixed width, so choose one (32 here) and mask. Rotations are the building blocks of hash functions and ciphers.

Python Rotate left and right in 32 bits

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Byte order (endianness)

A 32-bit number occupies four bytes. Big-endian stores the most significant byte first (network order); little-endian stores the least significant first, as x86 and ARM machines do. Mixing them up is a classic bug when you read files or network packets. Python's int.to_bytes, int.from_bytes and the struct module let you choose.

Python Big-endian versus little-endian

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Maximum XOR of any subarray

The XOR of the subarray arr[i..j] equals prefix[j+1] ^ prefix[i], where prefix holds running XORs. So the best subarray is the best XOR of any pair of prefix values, which the bitwise trie from Trie Applications finds in O(n x bits): for each new prefix, walk the trie preferring the opposite bit at every level.

Python Maximum subarray XOR with a bit trie

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Summing over all pairs and subsets, bit by bit

Many "sum over every pair" problems look like they need O(nยฒ) work, but XOR works on each bit independently. That lets you count per bit position instead of per pair.

Sum of XOR over all pairs. For one bit position, suppose ones of the n numbers have that bit set. The pair (i, j) has that bit set in a[i] ^ a[j] only when exactly one of the two has it, so there are ones * (n - ones) such pairs, each contributing 2**bit. Add up all bit positions: O(n log max).

Total Hamming distance. The Hamming distance of two numbers is the number of bit positions where they differ, which is (a ^ b).bit_count(). The total over all pairs is the same per-bit count ones * (n - ones), summed over the bits, with no 2**bit weight.

Sum of XOR over all subsets. A bit appears in some subset's XOR only if at least one element has it. When it does, exactly half of the 2**n subsets have it set, so the answer is (OR of all elements) * 2**(n-1).

XOR of all subarray XORs. Element i lies in (i + 1) * (n - i) subarrays. Equal values cancel in pairs, so only elements with an odd count matter.

Count subarrays with XOR equal to k. Use prefix XORs (see prefix sums for the idea) and a dictionary: the subarray (i, j] has XOR k exactly when prefix[j] ^ prefix[i] == k, i.e. prefix[i] == prefix[j] ^ k.

Python Per-bit counting tricks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each line prints the fast answer and, where it is cheap to compute, a brute-force check next to it.

Common mistakes

  • Operator precedence. n & 1 == 0 parses as n & (1 == 0). Always write (n & 1) == 0. Comparisons bind tighter than &, | and ^ in Python.
  • Assuming fixed width. Python never overflows. Mask with & 0xFFFFFFFF when you need 32-bit behavior.
  • Using ~x as "flip within 8 bits". ~5 is -6, not 250. Use x ^ 0xFF or ~x & 0xFF.
  • Shifting by a negative amount. 1 << -1 raises ValueError.
  • Forgetting n > 0 in the power-of-two test.
  • Premature cleverness. A bit trick that saves one line but costs a comment is not always a win. Use it where it is a known idiom.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does n & (n - 1) do?

    Subtracting 1 flips the lowest 1 to 0 and the zeros below it to 1, so ANDing with n removes exactly that bit.
  2. 2. Why does XOR-ing all numbers solve 'every value appears twice except one'?

    XOR is commutative and associative, and a ^ a is 0 while a ^ 0 is a. All pairs vanish, leaving the unique number in O(1) space.
  3. 3. What is -5 & 0xFF in Python?

    Python integers act like they have infinitely many sign bits. Masking with 0xFF keeps the low 8 bits, giving the 8-bit two's complement pattern 11111011, which is 251.
  4. 4. How many subsets does the bitmask loop for mask in range(1 << n) generate?

    Each of the n bits is independently in or out, so there are 2^n masks, each describing exactly one subset.
  5. 5. Which expression correctly tests whether n is even?

    In Python, == binds tighter than &, so n & 1 == 0 means n & (1 == 0). Parentheses are needed.

Summary

  • Bit operators & | ^ ~ << >> act on all bit positions at once; << and >> multiply and divide by powers of two.
  • Python integers are unbounded and behave as if sign-extended; use masks such as 0xFFFFFFFF for fixed-width results.
  • Test, set, clear and toggle bit i with (n >> i) & 1, n | (1 << i), n & ~(1 << i), n ^ (1 << i).
  • n & (n - 1) clears the lowest set bit; it powers popcount (Kernighan's loop) and the power-of-two test. int.bit_count() is the built-in.
  • XOR cancels pairs, so it finds the single or missing number in O(n) time and O(1) space.
  • A bitmask stores a subset in an integer; range(1 << n) enumerates all 2^n subsets.
  • Always parenthesize bit expressions that mix with comparisons.

Next: Number Theory Basics