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.

Practice

1. What is the result of the bitwise AND operation between 5 and 3? (5 = 0101, 3 = 0011 in binary)

easy

A. 1

B. 7

C. 6

D. 0

Solution

1. Step 1: Convert numbers to binary

   5 in binary is 0101, 3 in binary is 0011.

2. Step 2: Perform bitwise AND

   0101 AND 0011 = 0001 (only bits set in both numbers remain set).

3. Final Answer:

   1 -> Option A

4. Quick Check:

   5 & 3 = 1 [OK]

Hint: AND keeps bits set in both numbers only [OK]

Common Mistakes:

• Confusing AND with OR operation
• Not converting numbers to binary before operation
• Assuming decimal addition instead of bitwise AND

2. Which of the following is the correct syntax to perform a left shift by 2 bits on variable x in Python?

easy

A. x <<< 2

B. x >> 2

C. x << 2

D. x >>| 2

Solution

1. Step 1: Understand left shift operator in Python

   Left shift is done using << operator, shifting bits to the left.

2. Step 2: Check syntax options

   Only x << 2 correctly shifts bits left by 2 places.

3. Final Answer:

   x << 2 -> Option C

4. Quick Check:

   Left shift uses << operator [OK]

Hint: Use << for left shift, >> for right shift [OK]

Common Mistakes:

• Using >>> which is not valid in Python
• Confusing left shift with right shift operator
• Using invalid operators like >>|

3. What is the output of the following Python code?

num = 12  # binary 1100
result = num >> 2
print(result)

medium

A. 6

B. 0

C. 48

D. 3

Solution

1. Step 1: Convert number and apply right shift

   12 in binary is 1100. Right shifting by 2 bits removes last two bits: 1100 >> 2 = 0011.

2. Step 2: Convert shifted binary back to decimal

   0011 in binary is 3 in decimal.

3. Final Answer:

   3 -> Option D

4. Quick Check:

   12 >> 2 = 3 [OK]

Hint: Right shift divides number by 2^shift count [OK]

Common Mistakes:

• Confusing right shift with left shift
• Not converting binary back to decimal
• Assuming shift multiplies instead of divides

4. Identify the error in the following code snippet:

value = 10
result = ~value << 1
print(result)

medium

A. Result is -22 due to operator precedence

B. RuntimeError due to invalid shift

C. Result is 21 due to incorrect bitwise NOT

D. SyntaxError due to incorrect operator usage

Solution

1. Step 1: Evaluate bitwise NOT and shift

   ~10 equals -11 (because ~x = -x-1). Then shifting left by 1 bit multiplies by 2: -11 << 1 = -22.

2. Step 2: Check operator precedence and final value

   Because ~ has higher precedence, ~10 is evaluated first, then shifted. So result is -22, but print shows -22.

3. Final Answer:

   Result is -22 due to operator precedence -> Option A

4. Quick Check:

   ~10 << 1 = -22 [OK]

Hint: Bitwise NOT flips bits, watch operator precedence [OK]

Common Mistakes:

• Assuming ~10 is positive
• Ignoring operator precedence between ~ and <<
• Expecting shift to apply before NOT

5. Given two integers a = 9 and b = 14, which expression will toggle the bits where a and b differ?

hard

A. a | b

B. a ^ b

C. a & b

D. ~a

Solution

1. Step 1: Understand toggling bits where numbers differ

   Toggling bits means flipping bits that are different between two numbers.

2. Step 2: Identify bitwise XOR operation

   XOR (^) returns 1 where bits differ and 0 where bits are same, effectively toggling differing bits.

3. Final Answer:

   a ^ b -> Option B

4. Quick Check:

   XOR toggles differing bits [OK]

Hint: XOR flips bits where inputs differ [OK]

Common Mistakes:

• Using AND or OR which do not toggle bits
• Confusing NOT (~) with XOR
• Assuming OR toggles bits