Binary & bitwise operators
In one line
Every integer is a row of bits, and the operators AND, OR, XOR, NOT and shifts let you read, set, clear and flip those bits directly in constant time.
What it is
Computers store integers in binary: each position is a power of two. The number 13 is 1101 in binary, which means 8 + 4 + 0 + 1. Bit 0 is the rightmost bit (worth 1), bit 1 is worth 2, bit 2 is worth 4, and so on.
Bitwise operators work on every bit position at once. AND (&) gives 1 only where both bits are 1. OR (|) gives 1 where either bit is 1. XOR (^) gives 1 where the bits differ. NOT (~) flips every bit. Left shift (x << k) moves bits k places left, which multiplies by 2^k; right shift (x >> k) moves them right, which divides by 2^k and rounds down.
Negative numbers are stored in two's complement: to get -x, flip all bits of x and add 1. That is why ~x equals -x - 1, and why the highest bit of a fixed-width integer acts as the sign bit.
Why interviewers ask
Bit questions test whether you understand how numbers really live in memory. They also unlock short, fast solutions to problems that would otherwise need extra space, such as finding a unique element or representing a set as one integer. Interviewers look for confident use of masks like 1 << i and awareness of language details such as Python's unlimited-size integers versus 32-bit integers in Java or C++.
How it works
- 1Build a mask with a single 1 at position i using 1 << i. For i = 3 that is 1000 in binary, which is 8.
- 2Check bit i: (x >> i) & 1 is 1 if the bit is set and 0 otherwise. Equivalently, x & (1 << i) is non-zero when the bit is set.
- 3Set bit i with x | (1 << i), clear it with x & ~(1 << i), and flip it with x ^ (1 << i).
- 4Shift to multiply or divide by powers of two: x << 1 doubles x, x >> 1 halves it and rounds toward negative infinity (so -7 >> 1 is -4 in Python, Java and most C++ compilers).
- 5In Python, integers grow without limit and act as if they have infinitely many sign bits, so ~5 is -6 and there is no overflow. To mimic a 32-bit integer, mask with 0xFFFFFFFF.
Worked example · Applying each operator to 13 (1101) and 11 (1011)
- 13 & 11: line up 1101 and 1011. Only bit 3 and bit 0 are 1 in both, giving 1001 = 9.
- 13 | 11: a bit is 1 if either has it, giving 1111 = 15.
- 13 ^ 11: a bit is 1 where they differ (bits 2 and 1), giving 0110 = 6.
- 13 << 1: 1101 becomes 11010 = 26, which is 13 times 2.
- 13 >> 2: 1101 becomes 11 = 3, which is 13 divided by 4 rounded down.
- Set bit 1 of 13: 1101 | 0010 = 1111 = 15. Clear bit 0: 1101 & ~0001 = 1100 = 12. Check bit 2: (13 >> 2) & 1 = 3 & 1 = 1, so it is set.
Picture it
Think of an integer as a row of light switches on a wall. OR with a mask turns chosen switches on, AND with a mask keeps only chosen switches as they are and turns the rest off, XOR flips the chosen switches, and shifting slides the whole row left or right.
Reference code
def get_bit(x, i):
# 1 if bit i of x is set, else 0
return (x >> i) & 1
def set_bit(x, i):
return x | (1 << i)
def clear_bit(x, i):
return x & ~(1 << i)
def toggle_bit(x, i):
return x ^ (1 << i)
def to_unsigned32(x):
# Python ints never overflow; mask to see the 32-bit pattern
return x & 0xFFFFFFFF
x = 13 # 0b1101
print(get_bit(x, 2)) # 1
print(bin(set_bit(x, 1))) # 0b1111 (15)
print(bin(clear_bit(x, 0))) # 0b1100 (12)
print(bin(toggle_bit(x, 3)))# 0b101 (5)
print(hex(to_unsigned32(-1))) # 0xffffffff
The four helpers are the building blocks of nearly every bit trick. Each runs in O(1). The last helper shows how to view a Python integer as a 32-bit pattern, since Python itself never overflows.
Key patterns
Get, set, clear, toggle
When: Any problem that treats an integer as a set of flags
How: Use (x >> i) & 1, x | (1 << i), x & ~(1 << i) and x ^ (1 << i). Memorise these four; most bit problems are built from them.
Shifts as fast multiply and divide
When: Halving or doubling, or computing midpoints and powers of two
How: x << k is x times 2^k and x >> k is floor(x / 2^k). Use 1 << n for 2^n.
Fixed-width emulation in Python
When: A problem says 32-bit integers, or you reverse or rotate bits
How: Mask with 0xFFFFFFFF after each step, and convert back to signed with x - (1 << 32) if bit 31 is set.
Extract a field
When: Several small values are packed into one integer
How: Shift the field down to bit 0, then AND with a mask of its width, like (x >> 8) & 0xFF for the second byte.
Real-world use
Unix file permissions
Linux stores read, write and execute as bits 4, 2 and 1 for owner, group and others. chmod 755 means rwx (7 = 111) for the owner and r-x (5 = 101) for everyone else, and the kernel checks access with a bitwise AND.
System call flags
POSIX open() takes flags combined with OR, for example O_WRONLY | O_CREAT | O_TRUNC, and the kernel tests each one with AND. One integer carries many independent options.
Network subnet masks
A router decides whether an IP address is in 192.168.1.0/24 by ANDing the address with the mask 255.255.255.0 and comparing the result to the network address.
Colour values in graphics
A 32-bit ARGB colour packs four 8-bit channels into one integer. Code extracts red with (color >> 16) & 0xFF and builds a colour with shifts and OR, as image libraries and game engines do.
In a project
You are building a role-based access system for an internal admin dashboard with about 20 permissions (view users, edit users, refund orders, export data and so on), checked on every API request.
- Assign each permission a bit position, for example VIEW_USERS = 1 << 0, EDIT_USERS = 1 << 1, REFUND = 1 << 2.
- Store each role as one integer: an admin role is the OR of all its permission bits.
- Check a request with (role_bits & REQUIRED) == REQUIRED, which also handles endpoints that need several permissions at once.
- Grant or revoke with OR and AND NOT, and keep permission bit positions fixed forever so stored values stay valid.
Impact: Each permission check becomes a single AND and compare instead of a database join or a set lookup, roles fit in one database column, and adding a role combination is a one-line change. Discord's API uses this same approach for its permission values.
Trade-offs
Use it when
- You need many yes/no flags stored compactly and checked fast
- Values are small sets of positions (up to 64 fits in one machine word)
- You need multiply or divide by a power of two, or exact control over a binary format
Avoid it when
- A clear named boolean or set would be easier to read and speed does not matter
- Shifting by an amount at or beyond the type width in C or C++, which is undefined behaviour
- Relying on right shift of negative numbers in a language where its behaviour is implementation-defined
Cost: Each bitwise operation is O(1) on fixed-width integers. In Python, operations on very large integers cost O(number of bits).
Common mistakes
- Getting operator precedence wrong: in Python and C, x & 1 == 0 is not (x & 1) == 0. Add parentheses.
- Confusing logical and bitwise operators, such as using and instead of & in Python or && instead of & in Java.
- Assuming Python integers are 32-bit, which breaks problems involving negative numbers or overflow; mask with 0xFFFFFFFF.
- Counting bit positions from the left instead of from bit 0 on the right.
- Forgetting that ~x in Python is -x - 1, not a 32-bit unsigned value.
Interview questions
Quick revision
- Bit i is worth 2^i; bit 0 is the rightmost.
- AND keeps common bits, OR combines bits, XOR marks differences, NOT flips all.
- Check: (x >> i) & 1. Set: x | (1 << i). Clear: x & ~(1 << i). Toggle: x ^ (1 << i).
- x << k = x * 2^k; x >> k = floor(x / 2^k).
- Two's complement: -x = ~x + 1, so ~x = -x - 1.
- Python ints never overflow; use & 0xFFFFFFFF for 32-bit behaviour.
- Always parenthesise bit expressions next to == or +.
Check yourself
1. What is 6 & 3?
2. Which expression clears bit i of x?
3. What does ~5 evaluate to in Python?
4. What is 13 >> 2?
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.