Understanding and Solving the Circular Shift Problem

Objective

By the end of this lesson, students will:

1. Understand the difference between bitwise shift operators (<<, >>) and circular shifts (rotate).
2. Learn how to implement circular left and right shifts in Python to ensure the bits wrap around instead of being replaced by zeros.

Part 1: Introduction to Shift Operations

1. What are Bitwise Shift Operators?

• Left Shift (<<): Moves all bits to the left by a given number of positions, adding zeros to the right.
  • Example: 0b1111 << 2 → 0b111100
• Right Shift (>>): Moves all bits to the right, adding zeros to the left.
  • Example: 0b1111 >> 2 → 0b11

2. Problem with Normal Shifts

• Bits that “fall off” are lost and replaced with zeros.
• Goal: We want these “fallen-off” bits to wrap around to the other side.

Part 2: Understanding Circular Shifts

1. Circular Left Shift

• Moves all bits to the left.
• The bits that “fall off” on the left are added back to the right side.

2. Circular Right Shift

• Moves all bits to the right.
• The bits that “fall off” on the right are added back to the left side.

Part 3: Python Implementation

Here’s the code that solves the problem of circular shifts.

def left_rotate(x, n):
    """
    Circular left shift.
    Shifts bits to the left and wraps the fallen bits to the right.
    Args:
        x (int): The input number.
        n (int): The number of positions to shift.
    Returns:
        int: The circularly shifted number.
    """
    return ((x << n) | (x >> (8 - n))) & 0xFF

def right_rotate(x, n):
    """
    Circular right shift.
    Shifts bits to the right and wraps the fallen bits to the left.
    Args:
        x (int): The input number.
        n (int): The number of positions to shift.
    Returns:
        int: The circularly shifted number.
    """
    return ((x >> n) | (x << (8 - n))) & 0xFF

Part 4: Example

Let’s walk through an example:

x = 0b11110111  # Input binary number (247 in decimal)
n = 3           # Number of positions to shift

print(f"Original: {bin(x)}")
print(f"Left rotated: {bin(left_rotate(x, n))}")
print(f"Right rotated: {bin(right_rotate(x, n))}")

Output

Original:      0b11110111
Left rotated:  0b10111111
Right rotated: 0b11111110

Part 5: How It Works

1. Left Rotate

1. Step 1: Perform the left shift: (x << n).
2. Step 2: Wrap the fallen bits using right shift: (x >> (8 - n)).
3. Step 3: Combine the two using bitwise OR (|).
4. Step 4: Mask with 0xFF to ensure the result stays in 8 bits.

2. Right Rotate

1. Step 1: Perform the right shift: (x >> n).
2. Step 2: Wrap the fallen bits using left shift: (x << (8 - n)).
3. Step 3: Combine the two using bitwise OR (|).
4. Step 4: Mask with 0xFF to ensure the result stays in 8 bits.

Part 6: Exercises

1. Rotate x = 0b10101100 left by n = 2 and right by n = 3. Verify your result.
2. Modify the functions to handle 16-bit numbers (use 0xFFFF as the mask).
3. What happens if n is greater than the number of bits (e.g., n = 10)? How can you optimize the code for this case?

Part 7: Key Takeaways

1. Regular shifts replace fallen bits with zeros, but circular shifts wrap them around.
2. Circular shifts are useful in cryptography, data compression, and low-level bit manipulations.
3. Python’s bitwise operators make implementing these operations efficient.