Reverse Bits of a Number in DSA Typescript - Time & Space Complexity

Time Complexity: Reverse Bits of a Number

O(1)

Understanding Time Complexity

We want to understand how the time needed to reverse bits changes as the number size grows.

How does the number of steps grow when we reverse bits of bigger numbers?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) {
    result <<= 1;
    result |= (n & 1);
    n >>= 1;
  }
  return result;
}
    

This code reverses the bits of a 32-bit number by shifting and masking each bit.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The for-loop runs 32 times, processing one bit each time.
• How many times: Exactly 32 times, once for each bit in the number.

How Execution Grows With Input

Since the loop runs a fixed 32 times, the number of operations stays the same no matter the number.

Input Size (n)	Approx. Operations
10 (32-bit number)	32
100 (32-bit number)	32
1000 (32-bit number)	32

Pattern observation: The operations count stays constant because the bit size is fixed.

Final Time Complexity

Time Complexity: O(1)

This means the time to reverse bits does not grow with the number's value because the bit length is fixed.

Common Mistake

[X] Wrong: "The time to reverse bits grows with the number's value."

[OK] Correct: The code always processes 32 bits, so the value size does not affect the steps.

Interview Connect

Understanding fixed-size bit operations helps you reason about low-level data tasks and shows you can analyze constant-time algorithms confidently.

Self-Check

"What if we changed the code to reverse bits of a number with variable bit length n? How would the time complexity change?"

Practice

1. What does reversing the bits of a number mean in simple terms?

easy

A. Changing all 0 bits to 1 bits

B. Flipping the order of all bits from left to right

C. Adding 1 to the number

D. Shifting bits to the left by one position

Solution

1. Step 1: Understand bit order

   Bits are arranged from left (most significant) to right (least significant).

2. Step 2: Reverse means flip order

   Reversing bits means the leftmost bit becomes rightmost, second leftmost becomes second rightmost, and so on.

3. Final Answer:

   Flipping the order of all bits from left to right -> Option B

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Reverse bits means flip their order from left to right [OK]

Common Mistakes:

• Thinking reversing bits means changing 0 to 1
• Confusing reversing bits with shifting bits
• Assuming reversing bits adds or subtracts from number

2. Which TypeScript code snippet correctly reverses the bits of an 8-bit number n?

easy

A. let result = 0; for(let i=0; i<8; i++) { result |= ((n >> i) & 1) << (7 - i); }

B. let result = 0; for(let i=0; i<8; i++) { result |= ((n << i) & 1) << i; }

C. let result = 0; for(let i=0; i<8; i++) { result += (n & 1) << i; n >>= 1; }

D. let result = 0; for(let i = 0; i < 8; i++) { result |= (n & 1) << i; n >>= 1; }

Solution

1. Step 1: Analyze bit extraction and placement

   let result = 0; for(let i=0; i<8; i++) { result |= ((n >> i) & 1) << (7 - i); } extracts each bit from right to left and places it reversed from left to right correctly.

2. Step 2: Check other options

   A extracts LSBs but places them starting from low bits (original order); B uses left shift for extraction which fails to get bits properly; C uses arithmetic + instead of bitwise | and builds original order.

3. Final Answer:

   let result = 0; for(let i=0; i<8; i++) { result |= ((n >> i) & 1) << (7 - i); } -> Option A

4. Quick Check:

   Right shift and left place = correct reverse [OK]

Hint: Shift right to extract bits, shift left to place reversed bits [OK]

Common Mistakes:

• Using left shift to extract bits instead of right shift
• Not reversing the bit position when placing
• Adding bits instead of using bitwise OR

3. What is the output of this TypeScript code?

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 4; i++) {
    result |= ((n >> i) & 1) << (3 - i);
  }
  return result;
}
console.log(reverseBits(6));

medium

A. 6

B. 9

C. 3

D. 12

Solution

1. Step 1: Convert 6 to 4-bit binary

   6 in binary (4 bits) is 0110.

2. Step 2: Reverse bits

   Bits from LSB: 0,1,1,0. Reversed positions yield 0,1,1,0 reversed is 0110 reversed to 0110 reversed is 0110? Actually reversed bits are 0110 reversed to 0110? Let's check carefully.

3. Step 3: Dry run code

   i=0: (6 >> 0) & 1 = 0 << 3 = 0
   i=1: (6 >> 1) & 1 = 1 << 2 = 4 (result=4)
   i=2: (6 >> 2) & 1 = 1 << 1 = 2 (result=6)
   i=3: (6 >> 3) & 1 = 0 << 0 = 0 (result=6)

4. Step 4: Check if output matches options

   Output is 6, but 9 is 9, 6 is 6.

5. Final Answer:

   6 -> Option A

6. Quick Check:

   Reverse bits of 6 (0110) = 6 [OK]

Hint: Trace bit shifts carefully to find reversed number [OK]

Common Mistakes:

• Confusing bit positions when reversing
• Assuming reversed bits always change the number
• Miscounting bits or loop range

4. Identify the bug in this TypeScript function that reverses 8-bit numbers:

function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i <= 8; i++) {
    result |= ((n >> i) & 1) << (7 - i);
  }
  return result;
}

medium

A. Variable result should be initialized to 1

B. Bitwise OR operator is used incorrectly

C. Shift amount is not adjusted for 8 bits

D. Loop runs one extra time causing incorrect bit shift

Solution

1. Step 1: Check loop range

   The loop runs from i = 0 to i = 8 inclusive, so 9 iterations total, but 8-bit numbers have bits 0 to 7 only.

2. Step 2: Effect of extra iteration

   At i=8, shifting by (7 - 8) = -1 is invalid and causes incorrect behavior or runtime error.

3. Final Answer:

   Loop runs one extra time causing incorrect bit shift -> Option D

4. Quick Check:

   Loop should run 8 times, not 9 [OK]

Hint: Loop from 0 to 7 for 8 bits, not 0 to 8 [OK]

Common Mistakes:

• Using <= instead of < in loop condition
• Ignoring negative shift values
• Initializing result incorrectly

5. You want to reverse the bits of a 16-bit number and then check if the reversed number is a palindrome in binary (reads same forwards and backwards). Which approach is correct?

hard

A. Reverse bits using a loop, then compare reversed number to original

B. Reverse bits using a loop, then reverse again and compare to original

C. Reverse bits using a loop, then check if reversed number equals its own reverse

D. Check if original number equals its own reverse without reversing bits

Solution

1. Step 1: Reverse bits of the number

   Use a loop to reverse bits of the 16-bit number to get reversedNum.

2. Step 2: Check palindrome property

   To check if reversedNum is palindrome, reverse reversedNum again and compare with reversedNum itself.

3. Step 3: Reasoning

   If reversedNum equals its own reverse, it is a palindrome in binary.

4. Final Answer:

   Reverse bits using a loop, then check if reversed number equals its own reverse -> Option C

5. Quick Check:

   Palindrome check = reversedNum == reverse(reversedNum) [OK]

Hint: Check palindrome by reversing reversed number and comparing [OK]

Common Mistakes:

• Comparing reversed number to original instead of itself
• Not reversing reversed number for palindrome check
• Assuming original number palindrome means reversed number palindrome