Bit Manipulation in Python: Operators, Masks and Interview Tricks
Bit manipulation in Python uses six operators that work on the binary digits of integers: & (AND), | (OR), ^ (XOR), ~ (NOT), << (left shift) and >> (right shift). With a = 12 (0b1100) and b = 10 (0b1010), here is each one in a single line:
a, b = 12, 10 # 0b1100, 0b1010
print(a & b) # 8 0b1000 both bits set
print(a | b) # 14 0b1110 either bit set
print(a ^ b) # 6 0b0110 bits differ
print(~a) # -13 every bit flipped (-a - 1)
print(a << 2) # 48 shift left 2 = multiply by 4
print(a >> 2) # 3 shift right 2 = floor divide by 4
That is the answer most people are searching for. The rest of this page shows how to see the bits, how to check, set, clear and toggle a single bit, the n & (n - 1) and XOR tricks, why ~x is negative, and four interview problems that come up again and again in placement rounds.
See the bits: bin() and format()
You cannot manipulate bits you cannot see. bin() returns a string with a 0b prefix, format(n, 'b') drops the prefix, and a width like '08b' pads with zeros so the bits line up.
n = 45
print(bin(n)) # 0b101101
print(format(n, 'b')) # 101101
print(format(n, '08b')) # 00101101
print(f"{n:08b}") # 00101101
print(int('101101', 2)) # 45
print(0b101101) # 45
print(bin(-5)) # -0b101
Two things to notice. int(text, 2) converts a binary string back to a number, and 0b101101 is a binary literal you can type straight into code. And bin(-5) shows a minus sign, not a row of ones. We come back to negative numbers below.
Check, set, clear and toggle a bit
Bit positions are counted from the right, starting at 0. The number 1 << i has only bit i set, and it is the tool for all four operations:
n = 0b1010 # 10
print((n >> 1) & 1) # 1 bit 1 is set
print(bool(n & (1 << 2))) # False bit 2 is clear
print(bin(n | (1 << 2))) # 0b1110 set bit 2
print(bin(n & ~(1 << 1))) # 0b1000 clear bit 1
print(bin(n ^ (1 << 3))) # 0b10 toggle bit 3
A short way to remember it:
- Check bit
i:(n >> i) & 1gives 0 or 1. - Set bit
i:n | (1 << i). - Clear bit
i:n & ~(1 << i). - Toggle bit
i:n ^ (1 << i).
Bit masks: many flags in one integer
A mask is a number whose set bits mark the positions you care about. Bit masking in Python is common for permission flags, feature switches and packing small values into one integer.
READ, WRITE, EXEC = 1, 2, 4 # 0b001, 0b010, 0b100
perms = READ | WRITE
print(perms) # 3
print(bool(perms & EXEC)) # False
perms |= EXEC # grant EXEC
perms &= ~WRITE # revoke WRITE
print(bin(perms)) # 0b101
low4 = 0b1111
x = 0b10110110
print(x & low4) # 6 keep the last 4 bits
print((x >> 4) & low4) # 11 shift, then keep 4 bits
For named flags in real code, the standard library's enum.IntFlag gives you the same operators with readable names. In interviews, plain integers are what is expected.
The n & (n - 1) trick
Subtracting 1 from a number flips its lowest set bit to 0 and every bit below it to 1. So n & (n - 1) removes the lowest set bit. Two classic uses follow from that.
def is_power_of_two(n):
return n > 0 and n & (n - 1) == 0
print([x for x in range(1, 20) if is_power_of_two(x)]) # [1, 2, 4, 8, 16]
def count_set_bits(n):
count = 0
while n:
n &= n - 1 # drop the lowest set bit
count += 1
return count
print(count_set_bits(45)) # 4
print((45).bit_count()) # 4 Python 3.10+
print(bin(45).count("1")) # 4
print(12 & -12) # 4 lowest set bit on its own
print((45).bit_length()) # 6 bits needed to write 45
The loop version (Brian Kernighan's method) runs once per set bit rather than once per bit, which is the kind of detail the Big O notation lesson trains you to spot. In your own code, prefer int.bit_count(), added in Python 3.10.
XOR tricks: single number and swap
XOR has three properties worth memorising: x ^ x == 0, x ^ 0 == x, and the order does not matter. Put together, XOR-ing a list cancels every value that appears twice.
def single_number(nums):
result = 0
for x in nums:
result ^= x
return result
print(single_number([4, 1, 2, 1, 2])) # 4
a, b = 7, 12
a ^= b
b ^= a
a ^= b
print(a, b) # 12 7
The XOR swap is a famous interview answer, but in Python you would write a, b = b, a. It is clearer and works for any type. A hash set also solves the single-number problem in O(n) time; XOR does it with O(1) extra space, which is usually the follow-up question.
Negative numbers and why ~x is -x - 1
Python integers have arbitrary precision. There is no 32-bit or 64-bit limit, so shifting left never overflows:
print(1 << 100) # 1267650600228229401496703205376
print(~5, -5 - 1) # -6 -6
print(~-1) # 0
print(-5 >> 1) # -3
print(bin(-5 & 0xFF)) # 0b11111011
print(format(-5 & 0xFFFFFFFF, '032b')) # 11111111111111111111111111111011
For bitwise operators, Python treats a negative number as if it were written in two's complement with an endless row of 1s on the left. In two's complement, -x is "flip every bit of x, then add 1". So flipping every bit on its own gives -x - 1, which is why ~5 is -6.
Two consequences matter in practice:
>>on negatives rounds down.-5 >> 1is-3, the same as-5 // 2, not-2.- To see a fixed-width pattern, mask it.
-5 & 0xFFgives the 8-bit two's complement form. Problems written for 32-bit integers, such as "reverse bits" or "sum of two integers without +", need a& 0xFFFFFFFFmask in Python because the integer never runs out of bits.
Shifting by a negative amount is an error, not a shift in the other direction:
print(1 << -1)
# ValueError: negative shift count
Operator precedence: Python is not C
In Python, all bitwise operators bind more tightly than comparisons, so n & (n - 1) == 0 means (n & (n - 1)) == 0, which is what you want. In C and Java the same line compares first, so do not copy a C habit into Python or the other way round. The trap that does exist in Python is arithmetic: + and - bind more tightly than shifts, so 1 << n - 1 is 1 << (n - 1), and x & 1 + 1 is x & 2. When in doubt, add brackets.
Four classic interview problems
1. Missing number. A list holds every number from 0 to n except one. XOR the indices and the values together, and everything that appears twice cancels.
def missing_number(nums):
result = len(nums)
for i, x in enumerate(nums):
result ^= i ^ x
return result
print(missing_number([3, 0, 1])) # 2
print(missing_number([9, 6, 4, 2, 3, 5, 7, 0, 1])) # 8
2. Counting bits from 0 to n. The set bits of i equal the set bits of i >> 1 plus its last bit, so each answer reuses an earlier one.
def count_bits(n):
ans = [0] * (n + 1)
for i in range(1, n + 1):
ans[i] = ans[i >> 1] + (i & 1)
return ans
print(count_bits(5)) # [0, 1, 1, 2, 1, 2]
3. All subsets with a bitmask. Each number from 0 to 2**n - 1 is a pattern saying which items to take.
def subsets(items):
n = len(items)
return [[items[i] for i in range(n) if mask >> i & 1]
for mask in range(1 << n)]
print(subsets(["a", "b", "c"]))
# [[], ['a'], ['b'], ['a', 'b'], ['c'], ['a', 'c'], ['b', 'c'], ['a', 'b', 'c']]
4. Hamming distance. The number of positions where two numbers differ is the number of set bits in their XOR.
def hamming_distance(x, y):
return (x ^ y).bit_count()
print(hamming_distance(1, 4)) # 2
print(hamming_distance(93, 73)) # 2
Practise bit manipulation in the browser
The bit manipulation lesson on PyRun covers these operators with runnable examples and graded exercises. Python runs in the browser with no install, so you can paste any block above into the Python terminal or the practice editor, change a number, and watch the bits move. If you are preparing for placements, the Python interview questions for freshers post is a good next stop.