[Solved] Examine this Python function intended to generate an n-bit Gray code sequence:def gray_code(n): if n == 0:... | Bit Manipulation

Bit Manipulation - Gray Code

Examine this Python function intended to generate an n-bit Gray code sequence:

def gray_code(n):
     if n == 0:
         return [0]
     prev = gray_code(n - 1)
     add = 1 << n
     return prev + [x + add for x in reversed(prev)]

What is the subtle bug causing incorrect Gray code output?

AThe reversed list should not be used in concatenation

BThe base case should return an empty list instead of [0]

CThe bit shift uses n instead of n-1, causing incorrect bit addition

DThe function should use XOR instead of addition

Step-by-Step Solution

Solution:

Step 1: Analyze bit shift
The code uses add = 1 << n, but the highest bit for n-bit Gray code is at position n-1.
Step 2: Correct bit addition
It should be add = 1 << (n - 1) to correctly reflect the new bit position.
Step 3: Effect of bug
Using 1 << n adds a bit beyond the intended range, breaking Gray code property.
Final Answer:
Option C -> Option C
Quick Check:
Check bit shift index carefully. [OK]

Quick Trick: Highest bit index is n-1, not n, for n-bit Gray code [OK]

Common Mistakes:

MISTAKES

Using 1 << n instead of 1 << (n-1)
Returning empty list for base case
Ignoring reversed order in construction

Trap Explanation:

PITFALL

Option B looks plausible but base case [0] is correct for Gray code start.

Interviewer Note:

CONTEXT

Tests ability to spot subtle off-by-one bit errors in Gray code recursion.

Master "Gray Code" in Bit Manipulation

3 interactive learning modes - each teaches the same concept differently

Try It Solution Trace

More Bit Manipulation Quizzes

Examine this Python function intended to generate an n-bit Gray code sequence:

Step 1: Analyze bit shift

Step 2: Correct bit addition

Step 3: Effect of bug

Final Answer:

Quick Check:

Want More Practice?