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.

Bitwise Operators: AND, OR, XOR, NOT, Shifts is a free DSA Interview Prep lesson on CoddyKit — lesson 1 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.

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}')

OR Operator: Setting Bits

The OR operator (|) outputs 1 if at least one input bit is 1. Its primary use is setting a specific bit to 1 without affecting others. To set bit k in number n, use n | (1 << k). The 1 shifted to position k turns that bit on; all other bits remain unchanged because anything OR'd with 0 stays the same.

OR is also used for combining flags: if you represent feature flags as individual bits, you enable multiple flags with OR. For example, READ | WRITE | EXECUTE combines three permission bits into one integer.

# Set bit k in n
def set_bit(n, k):
    return n | (1 << k)

n = 0b1000  # 8
print(f'Original: {bin(n)}')
print(f'Set bit 1: {bin(set_bit(n, 1))}')  # 1010
print(f'Set bit 0: {bin(set_bit(n, 0))}')  # 1001

# Flag combination example
READ    = 0b001  # 1
WRITE   = 0b010  # 2
EXECUTE = 0b100  # 4

perms = READ | EXECUTE
print(f'READ|EXECUTE permissions: {bin(perms)} = {perms}')
print(f'Has READ:    {bool(perms & READ)}')
print(f'Has WRITE:   {bool(perms & WRITE)}')
print(f'Has EXECUTE: {bool(perms & EXECUTE)}')

XOR Operator: Toggle and Difference

The XOR operator (^) outputs 1 when the input bits differ. XOR has three powerful algebraic properties: a ^ a = 0 (same inputs cancel), a ^ 0 = a (zero is the identity), and XOR is both commutative and associative. These properties make XOR the go-to tool for finding unique elements.

XOR is also used to toggle a specific bit: n ^ (1 << k) flips bit k while leaving others unchanged. If bit k was 0, it becomes 1; if it was 1, it becomes 0.

# XOR properties
print(5 ^ 5)    # 0 — same values cancel
print(5 ^ 0)    # 5 — zero is identity
print(5 ^ 3 ^ 3)  # 5 — 3 cancels itself

# Toggle bit k
def toggle_bit(n, k):
    return n ^ (1 << k)

n = 0b1010
print(f'Toggle bit 3: {bin(toggle_bit(n, 3))}')  # 0010 (was 1)
print(f'Toggle bit 0: {bin(toggle_bit(n, 0))}')  # 1011 (was 0)

# XOR swap without temp variable
a, b = 7, 13
a = a ^ b
b = a ^ b   # b now gets original a
a = a ^ b   # a now gets original b
print(f'After XOR swap: a={a}, b={b}')  # a=13, b=7

NOT Operator and Two's Complement

The NOT operator (~) inverts all bits. In Python, ~n equals -(n+1) due to two's-complement representation. This surprises many people: ~5 = -6, not the naively expected 0b11111010. Python integers have infinite precision, so flipping all bits of a positive number gives a negative result in two's complement.

In practice, you rarely use ~ alone in Python for bit manipulation. Instead, use it in combination with AND to clear specific bits, or compute ~n & mask where mask limits the width to a specific number of bits (e.g., & 0xFFFFFFFF for 32-bit).

# NOT in Python: ~n = -(n+1)
for n in [0, 1, 5, 127]:
    print(f'~{n} = {~n}')   # all give -(n+1)

# Clear bit k using NOT
def clear_bit(n, k):
    return n & ~(1 << k)

n = 0b1111
print(f'Clear bit 2: {bin(clear_bit(n, 2))}')  # 1011
print(f'Clear bit 0: {bin(clear_bit(n, 0))}')  # 1110

# Limiting to 32-bit with mask
def bitwise_not_32(n):
    return ~n & 0xFFFFFFFF

print(f'32-bit NOT of 5: {bin(bitwise_not_32(5))}')  # 32 zeros then ones

Left Shift: Multiply by Powers of Two

The left shift operator (<<) shifts all bits to the left by k positions, filling the vacated right positions with zeros. This is equivalent to multiplying by 2^k. Left shifting by 1 doubles the value; left shifting by k multiplies by 2^k.

In interview problems, left shifts are most commonly used to create bitmasks: 1 << k creates a number with only bit k set. This is the foundation of all bit-manipulation operations — setting, clearing, toggling, and checking individual bits all start with 1 << k.

# Left shift = multiply by 2^k
n = 1
for k in range(8):
    print(f'1 << {k} = {1 << k}')   # 1,2,4,8,16,32,64,128

# Practical use: creating bitmasks
def bit_mask(k):
    return 1 << k

print(f'\nBitmask for bit 0: {bin(bit_mask(0))}')  # 1
print(f'Bitmask for bit 3: {bin(bit_mask(3))}')  # 1000
print(f'Bitmask for bit 7: {bin(bit_mask(7))}')  # 10000000

# Fast exponentiation: 2^10 = 1024
print(f'2^10 = {1 << 10}')  # 1024

Right Shift: Divide by Powers of Two

The right shift operator (>>) shifts all bits to the right by k positions, discarding the rightmost k bits. This is equivalent to integer division by 2^k. Python's right shift is always arithmetic: the leftmost bits are filled with the sign bit (0 for positive, 1 for negative).

A common interview trick: to extract bit k from number n, use (n >> k) & 1. This shifts bit k down to position 0 and masks off all other bits. It is the cleanest way to check any specific bit without needing to compute and compare a full mask.

# Right shift = integer division by 2^k
n = 64
for k in range(7):
    print(f'{n} >> {k} = {n >> k}')   # 64,32,16,8,4,2,1

# Extract bit k from n
def get_bit(n, k):
    return (n >> k) & 1

n = 0b10110101  # 181
print(f'\nBits of {n} ({bin(n)}):')
for k in range(8):
    print(f'  Bit {k}: {get_bit(n, k)}')

# Negative number right shift (arithmetic)
print(f'-8 >> 1 = {-8 >> 1}')   # -4 (fills with sign bit 1)

Practical Bit Tricks Cheatsheet

Here is a collection of the most common bit manipulation idioms you will encounter in interviews. Memorise these patterns — they appear repeatedly across dozens of problems:

n & 1 — check if n is odd
n & (n-1) — clear the lowest set bit
n & -n — isolate the lowest set bit
n | (1 << k) — set bit k
n & ~(1 << k) — clear bit k
n ^ (1 << k) — toggle bit k
(n >> k) & 1 — check bit k

# Bit trick cheatsheet — all at once
n = 0b10110100  # 180

print(f'n = {bin(n)} = {n}')
print(f'n & 1       (odd check)         = {n & 1}')          # 0: even
print(f'n & (n-1)   (clear lowest bit)  = {bin(n & (n-1))}')
print(f'n & -n      (isolate lowest bit) = {bin(n & -n)}')
print(f'n | (1<<1)  (set bit 1)          = {bin(n | (1<<1))}')
print(f'n & ~(1<<2) (clear bit 2)        = {bin(n & ~(1<<2))}')
print(f'n ^ (1<<5)  (toggle bit 5)       = {bin(n ^ (1<<5))}')
print(f'(n>>4) & 1  (check bit 4)        = {(n>>4) & 1}')

Counting Set Bits (Popcount)

Counting the number of 1 bits in an integer is called population count (popcount). The naive approach iterates over all bits. The Brian Kernighan trick is faster: repeatedly clear the lowest set bit with n &= n - 1, counting iterations until n becomes 0. Each iteration removes exactly one 1 bit, so the loop runs exactly as many times as there are 1 bits.

Python 3.10+ provides int.bit_count() which returns the count directly. For older versions, the Kernighan trick is the standard manual approach. This technique also solves the 'Hamming Weight' problem on LeetCode.

# Method 1: naive O(log n)
def count_bits_naive(n):
    count = 0
    while n:
        count += n & 1
        n >>= 1
    return count

# Method 2: Brian Kernighan O(k) where k = number of set bits
def count_bits_fast(n):
    count = 0
    while n:
        n &= n - 1   # clear lowest set bit
        count += 1
    return count

# Method 3: Python built-in (3.10+)
# n.bit_count()

for x in [0, 1, 7, 255, 180, 1024]:
    naive = count_bits_naive(x)
    fast  = count_bits_fast(x)
    print(f'{x:4d} ({bin(x):10s}): naive={naive}, fast={fast}')

Bit Manipulation in Python: Important Gotchas

Unlike C/Java, Python integers are arbitrarily large — there is no 32-bit or 64-bit overflow. This means you must manually mask results to a fixed width when solving problems that expect 32-bit behaviour: use & 0xFFFFFFFF to keep only the low 32 bits.

The NOT operator ~n in Python returns -(n+1), not the bit-flipped version you might expect from C. For 32-bit problems, use ~n & 0xFFFFFFFF or compute 0xFFFFFFFF ^ n to get the expected 32-bit complement. These differences trip up many candidates who are used to C-style bit manipulation.

# Python vs C gotchas
# In C: unsigned 32-bit NOT of 5 = 4294967290
# In Python: ~5 = -6
print(f'Python ~5 = {~5}')              # -6
print(f'32-bit ~5 = {~5 & 0xFFFFFFFF}') # 4294967290

# No integer overflow in Python
big = 1 << 100   # 2^100: huge number, no overflow
print(f'2^100 = {big}')  # works fine

# Right shift on negatives: arithmetic (sign-extending)
print(f'-1 >> 3 = {-1 >> 3}')   # -1 (all ones shifted in)

# Safe 32-bit mask for problems expecting C/Java semantics
MASK32 = 0xFFFFFFFF
result = (5 + 0xFFFFFFFE) & MASK32  # simulates 32-bit overflow
print(f'5 + (-2) in 32-bit = {result}')  # 3

Shift Operators and Multiplication

Left and right shifts provide an extremely fast way to multiply or divide by powers of two. On hardware, bit shifts are single-instruction operations whereas multiplication and division are multi-cycle. In Python, integer multiplication is already efficient, but understanding the relationship helps you see bit patterns more clearly.

A useful identity: to check if n is a multiple of 2^k, use (n & (2^k - 1)) == 0. The mask 2^k - 1 has all lower k bits set to 1; ANDing with it gives the remainder when divided by 2^k. This is equivalent to n % (2^k) but faster in C-based languages.

# Shift vs arithmetic equivalence
for k in range(1, 5):
    n = 48
    print(f'{n} * 2^{k} = {n * (2**k)} = {n << k} (left shift)')
    print(f'{n} // 2^{k} = {n // (2**k)} = {n >> k} (right shift)')
    print()

# Check divisibility by power of 2
def divisible_by_power_of_2(n, k):
    mask = (1 << k) - 1   # 2^k - 1: lower k bits all 1
    return (n & mask) == 0

for n in [16, 24, 32, 15, 100]:
    print(f'{n} divisible by 4? {divisible_by_power_of_2(n, 2)}')

Quick Check

Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.

Lesson Recap

In this lesson you learned: AND masks bits, OR sets bits, XOR toggles and detects differences, NOT inverts (gives -(n+1) in Python), and shifts multiply/divide by powers of two, n & (n-1) clears the lowest set bit and is the basis for power-of-two checks and bit counting, and Python has no fixed-width overflow so 32-bit problems require explicit masking with & 0xFFFFFFFF. Next up we explore XOR's self-inverse property to solve the single-number problem family.

Frequently asked questions

Is the “Bitwise Operators: AND, OR, XOR, NOT, Shifts” lesson free?

Yes — the full text of “Bitwise Operators: AND, OR, XOR, NOT, Shifts” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.

What will I learn in “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. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.

Do I need any experience to start DSA Interview Prep?

No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 1 of 4, so you can start here or from the beginning and move at your own pace.

How long does the “Bitwise Operators: AND, OR, XOR, NOT, Shifts” lesson take?

Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.

Can I write and run code in this DSA Interview Prep lesson?

Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.

All lessons in this course

Bitwise Operators: AND, OR, XOR, NOT, Shifts
Single Number and XOR Properties
Bit Masks: Set, Clear, Toggle, Check
Counting Bits, Missing Number, and Reverse Bits

← Back to DSA Interview Prep