Bit Manipulation Basics AND OR XOR NOT Left Right Shift in DSA Python

Mental Model

Bit manipulation changes numbers by flipping or moving their tiny on/off switches called bits.

Analogy: Imagine a row of light switches where each switch can be on (1) or off (0). Bit operations flip, combine, or shift these switches to get new patterns.

Number 6 in bits (8 bits):
0 0 0 0 0 1 1 0
Positions:          ↑ ↑ ↑ ↑ ↑ ↑ ↑ ↑
                    7 6 5 4 3 2 1 0

Dry Run Walkthrough

Input: numbers: a = 6 (00000110), b = 3 (00000011)

Goal: Show how AND, OR, XOR, NOT, left shift, and right shift change bits of a and b

Step 1: Calculate AND of a and b

a = 00000110 (6)
b = 00000011 (3)
a AND b = 00000010 (2)

Why: AND keeps bits on only if both bits are on

Step 2: Calculate OR of a and b

a = 00000110 (6)
b = 00000011 (3)
a OR b = 00000111 (7)

Why: OR turns bits on if at least one bit is on

Step 3: Calculate XOR of a and b

a = 00000110 (6)
b = 00000011 (3)
a XOR b = 00000101 (5)

Why: XOR turns bits on only if bits differ

Step 4: Calculate NOT of a (invert bits)

a = 00000110 (6)
NOT a = 11111001 (in 8-bit, equals -7 in two's complement)

Why: NOT flips every bit from on to off or off to on

Step 5: Left shift a by 1 (move bits left)

a = 00000110 (6)
a << 1 = 00001100 (12)

Why: Left shift moves bits left, doubling the number

Step 6: Right shift a by 1 (move bits right)

a = 00000110 (6)
a >> 1 = 00000011 (3)

Why: Right shift moves bits right, halving the number

Result:

Final results:
AND: 2 (00000010)
OR: 7 (00000111)
XOR: 5 (00000101)
NOT a: 249 (11111001 unsigned) or -7 signed
Left shift a: 12 (00001100)
Right shift a: 3 (00000011)

Annotated Code

DSA Python

class BitManipulation:
    @staticmethod
    def bit_and(a: int, b: int) -> int:
        return a & b  # AND operation keeps bits on only if both are on

    @staticmethod
    def bit_or(a: int, b: int) -> int:
        return a | b  # OR operation turns bits on if at least one is on

    @staticmethod
    def bit_xor(a: int, b: int) -> int:
        return a ^ b  # XOR turns bits on only if bits differ

    @staticmethod
    def bit_not(a: int) -> int:
        return ~a  # NOT flips every bit

    @staticmethod
    def left_shift(a: int, n: int) -> int:
        return a << n  # Left shift moves bits left, multiplies by 2^n

    @staticmethod
    def right_shift(a: int, n: int) -> int:
        return a >> n  # Right shift moves bits right, divides by 2^n


def main():
    a = 6  # 00000110
    b = 3  # 00000011

    print(f"AND: {BitManipulation.bit_and(a, b)}")
    print(f"OR: {BitManipulation.bit_or(a, b)}")
    print(f"XOR: {BitManipulation.bit_xor(a, b)}")
    print(f"NOT a: {BitManipulation.bit_not(a)}")
    print(f"Left shift a by 1: {BitManipulation.left_shift(a, 1)}")
    print(f"Right shift a by 1: {BitManipulation.right_shift(a, 1)}")


if __name__ == "__main__":
    main()

return a & b # AND operation keeps bits on only if both are on

perform AND to keep bits on only if both bits are 1

return a | b # OR operation turns bits on if at least one is on

perform OR to turn bits on if either bit is 1

return a ^ b # XOR turns bits on only if bits differ

perform XOR to turn bits on only if bits differ

return ~a # NOT flips every bit

flip all bits to get bitwise NOT

return a << n # Left shift moves bits left, multiplies by 2^n

shift bits left by n positions, multiplying by 2^n

return a >> n # Right shift moves bits right, divides by 2^n

shift bits right by n positions, dividing by 2^n

Output

AND: 2

OR: 7

XOR: 5

NOT a: -7

Left shift a by 1: 12

Right shift a by 1: 3

Complexity Analysis

Time: O(1) because bitwise operations work directly on fixed-size bits without loops

Space: O(1) because no extra memory is needed beyond input variables

vs Alternative: Bit manipulation is much faster and uses less memory than arithmetic operations or loops for similar tasks

Edge Cases

a = 0 (all bits off)

AND with any number results in 0; OR results in the other number; NOT flips all bits

DSA Python

return a & b  # AND operation keeps bits on only if both are on

left shift causing overflow beyond bit size

Bits shifted out are lost; result may wrap or become zero depending on language

DSA Python

return a << n  # Left shift moves bits left, multiplies by 2^n

right shift of negative numbers

Arithmetic right shift keeps sign bit; logical right shift fills with zero (language dependent)

DSA Python

return a >> n  # Right shift moves bits right, divides by 2^n

When to Use This Pattern

When you need to quickly check, flip, or move individual bits in numbers, reach for bit manipulation because it is fast and memory efficient.

Common Mistakes

Mistake: Confusing XOR with OR and expecting it to behave the same
Fix: Remember XOR only turns bits on if bits differ, unlike OR which turns bits on if either bit is on

Mistake: Using NOT without understanding two's complement representation leading to unexpected negative results
Fix: Understand that NOT flips all bits including sign bit, so result is negative in signed integers

Mistake: Shifting bits beyond the size of the integer without checking, causing data loss
Fix: Limit shift amount to less than bit width of the integer type

Summary

It changes numbers by flipping or moving their bits using AND, OR, XOR, NOT, and shifts.

Use it when you want fast, low-level control over individual bits in numbers.

The key is to think of numbers as rows of on/off switches that you can combine or move.