Left shift and right shift in C - Time & Space Complexity

Time Complexity: Left shift and right shift

O(1)

Understanding Time Complexity

We want to see how fast the program runs when using left and right shift operations.

How does the number of steps change when we shift bits in a number?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int leftShift(int x, int n) {
    return x << n;
}

int rightShift(int x, int n) {
    return x >> n;
}
    

This code shifts the bits of an integer left or right by n positions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bit shifting done by the CPU in one step.
• How many times: The shift happens once per function call, no loops involved.

How Execution Grows With Input

Shifting bits is done in a single CPU instruction regardless of how many bits we shift.

Input Size (n)	Approx. Operations
1	1 operation
10	1 operation
100	1 operation

Pattern observation: The time to shift does not grow with the number of bits shifted.

Final Time Complexity

Time Complexity: O(1)

This means shifting bits takes the same amount of time no matter how many bits you shift.

Common Mistake

[X] Wrong: "Shifting by more bits means the program takes longer to run because it moves each bit one by one."

[OK] Correct: The CPU does the shift in one step, not bit by bit, so the time stays the same.

Interview Connect

Understanding that bit shifts are constant time helps you explain how low-level operations work efficiently in real programs.

Self-Check

"What if we replaced the shift operations with a loop that shifts one bit at a time? How would the time complexity change?"

Practice

1. What does the left shift operator << do to an integer in C?

easy

A. Moves bits to the left, multiplying the number by powers of two

B. Moves bits to the right, dividing the number by powers of two

C. Reverses the bits of the number

D. Sets all bits to zero

Solution

1. Step 1: Understand left shift operation

   The left shift operator moves all bits in the number to the left by the specified count.

2. Step 2: Effect on the number's value

   Each left shift multiplies the number by 2, so shifting left by n multiplies by 2^n.

3. Final Answer:

   Moves bits to the left, multiplying the number by powers of two -> Option A

4. Quick Check:

   Left shift = multiply by 2^n [OK]

Hint: Left shift multiplies by 2 to the power of shift count [OK]

Common Mistakes:

• Confusing left shift with right shift
• Thinking left shift divides the number
• Assuming left shift reverses bits

2. Which of the following is the correct syntax to shift the integer variable x right by 3 bits in C?

easy

A. x >>> 3;

B. x >> 3;

C. x << 3;

D. x >>3

Solution

1. Step 1: Identify the right shift operator in C

   The right shift operator is >> and requires spaces or no spaces around it.

2. Step 2: Check syntax correctness

   x >> 3; is correct syntax. x << 3; is left shift, x >>> 3; is invalid in C, and x >>3 is missing a semicolon.

3. Final Answer:

   x >> 3; -> Option B

4. Quick Check:

   Right shift syntax = x >> n; [OK]

Hint: Right shift uses >> with semicolon to end statement [OK]

Common Mistakes:

• Using >>> which is not valid in C
• Confusing left shift << with right shift >>
• Omitting semicolon at end

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

int x = 4;
int y = x << 2;
printf("%d", y);

medium

A. 0

B. 1

C. 8

D. 16

Solution

1. Step 1: Understand the initial value of x

   x is 4, which in binary is 00000100.

2. Step 2: Apply left shift by 2 bits

   Shifting left by 2 bits multiplies 4 by 2^2 = 4 * 4 = 16.

3. Final Answer:

   16 -> Option D

4. Quick Check:

   4 << 2 = 16 [OK]

Hint: Left shift by n multiplies by 2^n [OK]

Common Mistakes:

• Calculating 4 << 2 as 8 instead of 16
• Confusing left shift with right shift
• Ignoring the shift count

4. Find the error in this C code snippet:

int a = 32;
int b = a >> 2
printf("%d", b);

medium

A. Wrong operator used for right shift

B. Incorrect printf format specifier

C. Missing semicolon after right shift operation

D. Variable b is not declared

Solution

1. Step 1: Check syntax line by line

   The line int b = a >> 2 is missing a semicolon at the end.

2. Step 2: Verify other parts

   The operator >> is correct, printf uses %d for int, and b is declared properly.

3. Final Answer:

   Missing semicolon after right shift operation -> Option C

4. Quick Check:

   Every statement needs semicolon [OK]

Hint: Check for missing semicolons after shift operations [OK]

Common Mistakes:

• Assuming >> is invalid operator
• Thinking printf format is wrong
• Ignoring missing semicolon errors

5. Given int x = 1;, what is the value of y after this operation?

int y = (x << 3) >> 1;

hard

A. 4

B. 8

C. 16

D. 2

Solution

1. Step 1: Calculate left shift (x << 3)

   Left shifting 1 by 3 bits multiplies 1 by 2^3 = 8.

2. Step 2: Calculate right shift of result by 1

   Right shifting 8 by 1 bit divides 8 by 2^1 = 2, so 8 / 2 = 4.

3. Final Answer:

   4 -> Option A

4. Quick Check:

   (1 << 3) >> 1 = 8 >> 1 = 4 [OK]

Hint: Left shift then right shift: multiply then divide by powers of two [OK]

Common Mistakes:

• Calculating (1 << 3) as 16
• Ignoring right shift effect
• Mixing up shift directions