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

Time Complexity: Left shift and right shift behavior

O(1)

Understanding Time Complexity

We want to understand how the time taken by left and right shift operations changes as the number of bits shifted grows.

How does shifting more bits affect the work done by the program?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

unsigned int shift_left(unsigned int x, unsigned int n) {
    return x << n;
}

unsigned int shift_right(unsigned int x, unsigned int n) {
    return x >> n;
}
    

This code shifts bits of a number left or right by n positions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Bit shifting by n positions.
• How many times: The shift moves bits one position at a time internally, repeated n times.

How Execution Grows With Input

Shifting by more bits means the processor moves bits more times.

Input Size (n)	Approx. Operations
1	1 bit move
8	8 bit moves
32	32 bit moves

Pattern observation: The work grows linearly with the number of bits shifted.

Final Time Complexity

Time Complexity: O(1)

This means the time to shift is constant and does not depend on how many bits you shift.

Common Mistake

[X] Wrong: "Bit shifts happen instantly no matter how many bits are shifted."

[OK] Correct: Internally, shifting moves bits step by step, so shifting more bits takes more time.

Interview Connect

Understanding how bit shifts scale helps you reason about low-level code performance and embedded system efficiency.

Self-Check

"What if the processor supports shifting multiple bits at once? How would that change the time complexity?"

Practice

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

easy

A. Divides the number by powers of two

B. Inverts all bits of the number

C. Multiplies the number by powers of two

D. Leaves the number unchanged

Solution

1. Step 1: Understand left shift operation

   The left shift operator moves bits to the left, adding zeros on the right.

2. Step 2: Effect on unsigned integer value

   Shifting left by 1 bit multiplies the number by 2, shifting by n bits multiplies by 2^n.

3. Final Answer:

   Multiplies the number by powers of two -> Option C

4. Quick Check:

   Left shift = multiply by 2^n [OK]

Hint: Left shift multiplies by 2 for each shift [OK]

Common Mistakes:

• Thinking left shift divides the number
• Confusing left shift with bitwise NOT
• Assuming left shift leaves number unchanged

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

easy

A. x >>3

B. x << 3;

C. x >>> 3;

D. x >> 3;

Solution

1. Step 1: Identify right shift operator syntax

   In embedded C, right shift is done using >> operator with spaces optional.

2. Step 2: Check options for correct syntax

   The correct syntax is x >> 3; using the right shift operator >>, shift amount 3, and semicolon to form a valid statement. Lacking semicolon, using left shift <<, or invalid operator like >>> are incorrect.

3. Final Answer:

   x >> 3; -> Option D

4. Quick Check:

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

Hint: Right shift uses >> operator with semicolon [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 code snippet?

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

medium

A. 16

B. 8

C. 1

D. 32

Solution

1. Step 1: Understand initial value and shift

   Variable x is 4 (binary 100). Left shifting by 2 bits moves bits left twice.

2. Step 2: Calculate shifted value

   4 << 2 = 4 * 2^2 = 4 * 4 = 16.

3. Final Answer:

   16 -> Option A

4. Quick Check:

   4 << 2 = 16 [OK]

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

Common Mistakes:

• Confusing left shift with right shift
• Calculating 4 << 2 as 8 instead of 16
• Ignoring unsigned type behavior

4. Consider this code snippet:

int x = -16;
int y = x >> 2;
printf("%d", y);

What is the likely output assuming arithmetic right shift?

medium

A. -4

B. 4

C. -1

D. 0

Solution

1. Step 1: Understand signed right shift behavior

   For signed integers, right shift usually preserves the sign bit (arithmetic shift).

2. Step 2: Calculate shifted value

   -16 in binary (two's complement) is shifted right by 2 bits, dividing by 4 but keeping sign, so -16 >> 2 = -4.

3. Final Answer:

   -4 -> Option A

4. Quick Check:

   Signed right shift divides and keeps sign [OK]

Hint: Signed right shift divides and keeps sign bit [OK]

Common Mistakes:

• Assuming right shift always fills with zeros
• Confusing signed and unsigned shift results
• Expecting positive result from negative input

5. You want to multiply an unsigned 8-bit integer val by 8 using bit shifts without overflow. Which code snippet is correct?

unsigned char val = 20;
unsigned char result = val << 3;

What should you check before shifting to avoid overflow?

hard

A. Ensure val <= 8 before shifting

B. Ensure val <= 31 before shifting

C. Ensure val <= 20 before shifting

D. No check needed, shifting never overflows

Solution

1. Step 1: Understand shift and overflow risk

   Shifting left by 3 multiplies by 8. For 8-bit unsigned, max value is 255.

2. Step 2: Calculate max safe value

   To avoid overflow: val * 8 <= 255 -> val <= 31.875, so val must be ≤ 31.

3. Final Answer:

   Ensure val <= 31 before shifting -> Option B

4. Quick Check:

   Max val before shift = 255 / 8 = 31 [OK]

Hint: Check max value before shift to prevent overflow [OK]

Common Mistakes:

• Ignoring overflow risk on left shift
• Assuming shifting never causes overflow
• Using wrong max value for 8-bit unsigned