Reverse Bits of a Number in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does it mean to reverse the bits of a number?

Reversing the bits means flipping the order of all bits in the binary form of the number, so the first bit becomes the last, the second becomes the second last, and so on.

beginner

How many bits are typically considered when reversing bits of a 32-bit integer?

Usually, all 32 bits of the integer are considered, including leading zeros, to maintain the fixed size of the number.

intermediate

What is the main operation used to reverse bits one by one?

The main operations are bit shifting and bit masking: shifting bits to the right to extract them, and shifting bits to the left to build the reversed number.

beginner

Why do we use a loop of fixed length (like 32) when reversing bits?

Because the number has a fixed bit size (e.g., 32 bits), and we need to process each bit exactly once to reverse the entire bit sequence.

intermediate

What is the time complexity of reversing bits of a fixed-size integer?

The time complexity is O(1) because the number of bits is fixed (e.g., 32 or 64), so the operation takes constant time.

What is the first step when reversing bits of a number?

A Add 1 to the number

B Shift the number left by one

C Extract the least significant bit using bitwise AND

D Convert the number to decimal

We first extract the least significant bit by using bitwise AND with 1 to get the current bit to reverse.

How do you add the extracted bit to the reversed number?

A Multiply reversed number by 2

B Shift reversed number right by 1, then AND with extracted bit

C Add extracted bit directly without shifting

D Shift reversed number left by 1, then OR with extracted bit

We shift the reversed number left by 1 to make space, then add the extracted bit using OR.

How many times do you repeat the bit extraction and addition to reverse a 32-bit number?

A 16 times

B 32 times

C 64 times

D Until the number becomes zero

You repeat 32 times to process all bits of a 32-bit number.

What happens if you forget to shift the reversed number before adding the new bit?

A Bits will overlap and the reversed number will be incorrect

B The reversed number will be doubled

C The reversed number will be zero

D The reversed number will be unchanged

Without shifting, new bits overwrite existing bits causing incorrect reversal.

Which bitwise operator is used to extract the least significant bit?

A AND (&)

B OR (|)

C XOR (^)

D NOT (~)

Bitwise AND with 1 extracts the least significant bit.

Explain step-by-step how to reverse the bits of a 32-bit number using bitwise operations.

Think about how to build the reversed number bit by bit.

Why is reversing bits useful in programming or computer science?

Consider applications involving binary data.

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