Reverse Bits of a Number in DSA Typescript

Mental Model

Flip the order of bits in a number so the last bit becomes first and the first becomes last.

Analogy: Imagine a row of light switches turned on or off. Reversing bits is like walking to the end of the row and flipping the switches in reverse order, so the last switch's state becomes the first's.

Original bits: 0 0 0 0 1 1 0 1
Reversed bits: 1 0 1 1 0 0 0 0

Dry Run Walkthrough

Input: number: 13 (binary 00001101), reverse all 8 bits

Goal: Get the number whose bits are reversed: 10110000 (binary) = 176 decimal

Step 1: Extract rightmost bit (1) and add it to result

result = 00000001, number shifts right to 00000110

Why: We start building reversed bits from the rightmost bit of the original number

Step 2: Shift result left and extract next bit (0) and add it to result

result = 00000010, number shifts right to 00000011

Why: Shift result left to make room for next bit, then add it

Step 3: Shift result left and extract next bit (1) and add it to result

result = 00000101, number shifts right to 00000001

Why: Continue reversing bits one by one

Step 4: Shift result left and extract next bit (1) and add it to result

result = 00001011, number shifts right to 00000000

Why: Finish reversing all bits since number is now zero

Step 5: Shift result left for remaining bits (4 more bits) to complete 8 bits

result = 10110000

Why: Fill remaining bits with zeros on right to complete 8-bit reversal

Result:

10110000 (binary) = 176 decimal

Annotated Code

DSA Typescript

class BitReverser {
  static reverseBits(num: number, bitSize: number = 8): number {
    let result = 0;
    for (let i = 0; i < bitSize; i++) {
      result <<= 1; // shift result left to make room for next bit
      result |= (num & 1); // add rightmost bit of num to result
      num >>= 1; // shift num right to process next bit
    }
    return result;
  }
}

// Driver code
const inputNumber = 13; // binary 00001101
const reversed = BitReverser.reverseBits(inputNumber, 8);
console.log(reversed);

result <<= 1; // shift result left to make room for next bit

Shift reversed bits left to add new bit at right

result |= (num & 1); // add rightmost bit of num to result

Extract rightmost bit of num and add to result

num >>= 1; // shift num right to process next bit

Move to next bit of num by shifting right

Output

176

Complexity Analysis

Time: O(b) because we process each of the b bits once

Space: O(1) because only a few variables are used regardless of input size

vs Alternative: Naive approach might convert to string and reverse, which uses extra space and is slower; bitwise approach is efficient and uses constant space

Edge Cases

number is 0

Result is 0 since all bits are zero

DSA Typescript

for (let i = 0; i < bitSize; i++) { ... }

number uses fewer bits than bitSize

Leading zeros are reversed correctly, filling higher bits in result

DSA Typescript

for (let i = 0; i < bitSize; i++) { ... }

bitSize larger than actual number bits

Extra bits are treated as zeros and reversed accordingly

DSA Typescript

for (let i = 0; i < bitSize; i++) { ... }

When to Use This Pattern

When asked to reverse bits or manipulate bits in a number, use bitwise shifts and masks to process bits one by one efficiently.

Common Mistakes

Mistake: Not shifting the result before adding the new bit, causing bits to overwrite
Fix: Always shift the result left before OR-ing the new bit

Mistake: Shifting the input number left instead of right, losing bits
Fix: Shift the input number right to process bits from right to left

Summary

Reverses the order of bits in a number using bitwise operations.

Use when you need to flip bits order for encoding, decoding, or bit manipulation tasks.

Shift the result left before adding each bit from the input shifted right.

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