0PricingLogin▼
DSA Interview Prep · Lesson

Bitwise Operators: AND, OR, XOR, NOT, Shifts

Review all six bitwise operators with truth tables and Python examples, and understand how left/right shifts relate to multiplication and division by two.

Why Bit Manipulation Matters

Bit manipulation lets you operate directly on the binary representation of integers. Many problems that seem complex become trivial with the right bitwise trick: finding a missing number in O(n) time and O(1) space, swapping variables without a temp, or encoding subsets compactly. Interviewers use these problems to test low-level understanding and creative thinking.

Python integers have arbitrary precision — they can be as large as memory allows — but bit operations always follow standard two's-complement semantics at the hardware level. All six operators work on integer binary representations bit by bit.

# All six bitwise operators in Python
a, b = 0b1010, 0b1100  # 10 and 12 in decimal
print(f'a = {bin(a)} = {a}')
print(f'b = {bin(b)} = {b}')
print(f'a & b  (AND) = {bin(a & b)} = {a & b}')   # 1000 = 8
print(f'a | b  (OR)  = {bin(a | b)} = {a | b}')   # 1110 = 14
print(f'a ^ b  (XOR) = {bin(a ^ b)} = {a ^ b}')   # 0110 = 6
print(f'~a     (NOT) = {~a}')                       # -11 (two's complement)
print(f'a << 1 (LSH) = {bin(a << 1)} = {a << 1}') # 10100 = 20
print(f'a >> 1 (RSH) = {bin(a >> 1)} = {a >> 1}') # 101 = 5

AND Operator: Bit Masking

The AND operator (&) outputs 1 only when both input bits are 1. Its primary use is masking: selecting specific bits of a number while zeroing out all others. To check if bit k is set in number n, evaluate n & (1 << k) — if the result is non-zero, bit k is 1.

AND is also used to clear the lowest set bit: n & (n - 1) removes the rightmost 1 bit. This is used in counting set bits efficiently and in checking if a number is a power of two (a power of two has exactly one set bit, so n & (n-1) == 0).

n = 0b10110100  # 180

# Check if bit 5 is set (0-indexed from right)
bit_5 = (n >> 5) & 1
print(f'Bit 5 of {n}: {bit_5}')  # 1

# Clear lowest set bit
print(f'n = {bin(n)}')
print(f'n & (n-1) = {bin(n & (n-1))}')  # 10110000, removed the '100'

# Check power of two
for x in [16, 15, 8, 6, 1, 0]:
    is_pow2 = x > 0 and (x & (x - 1)) == 0
    print(f'{x}: power of 2 = {is_pow2}')

All lessons in this course

  1. Bitwise Operators: AND, OR, XOR, NOT, Shifts
  2. Single Number and XOR Properties
  3. Bit Masks: Set, Clear, Toggle, Check
  4. Counting Bits, Missing Number, and Reverse Bits
← Back to DSA Interview Prep