Reverse Bits of a Number in DSA Javascript

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 from the end of the row to the start, flipping the order of switches in your mind.

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 to result

result = 1, number shifts right to 00000110

Why: We start building reversed bits from right to left

Step 2: Shift result left by 1, extract next bit (0), add to result

result = 10 (binary 2), number shifts right to 00000011

Why: Make room for next bit and add it

Step 3: Shift result left by 1, extract next bit (1), add to result

result = 101 (binary 5), number shifts right to 00000001

Why: Continue reversing bits

Step 4: Shift result left by 1, extract next bit (1), add to result

result = 1011 (binary 11), number shifts right to 00000000

Why: Add last bit from original number

Step 5: Shift result left by 1, add 0 (no more bits left)

result = 10110 (binary 22)

Why: Fill remaining bits with zeros to complete 8 bits

Step 6: Shift result left by 1, add 0

result = 101100 (binary 44)

Why: Continue filling zeros

Step 7: Shift result left by 1, add 0

result = 1011000 (binary 88)

Why: Continue filling zeros

Step 8: Shift result left by 1, add 0

result = 10110000 (binary 176)

Why: Complete 8-bit reversal

Result:

10110000 (binary) = 176 decimal

Annotated Code

DSA Javascript

class BitReverser {
  static reverseBits(num, bitSize = 8) {
    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

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 in original number

Output

176

Complexity Analysis

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

Space: O(1) because we use a fixed number of variables regardless of input size

vs Alternative: This is more efficient than converting to string and reversing, which uses extra space and time for string operations

Edge Cases

number is 0

result is 0 since all bits are zero

DSA Javascript

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

number has all bits set (e.g., 255 for 8 bits)

result is the same number since reversing all ones stays all ones

DSA Javascript

result |= (num & 1);

bitSize larger than actual bits in number

leading zeros are added in reversed result

DSA Javascript

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

When to Use This Pattern

When you need to reverse the order of bits in a number, use bitwise shifts and masks to build the reversed number bit by bit.

Common Mistakes

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

Mistake: Shifting the original number left instead of right, losing bits
Fix: Shift the original number right to process bits from least significant to most

Summary

Reverses the bits of a number by shifting and masking each bit.

Use when you need the mirror image of a number's bits, such as in low-level data processing.

The key is to build the reversed number by shifting left and adding bits from right to left.

Practice

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

easy

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

B. Changing all 0 bits to 1 bits

C. Adding 1 to the number

D. Multiplying the number by 2

Solution

1. Step 1: Understand bits as binary digits

   Bits are the 0s and 1s that make up a number in binary form.

2. Step 2: Define reversing bits

   Reversing bits means reading the bits from right to left instead of left to right.

3. Final Answer:

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

4. Quick Check:

   Reverse bits = flip order [OK]

Hint: Think of bits like beads on a string flipped end to end [OK]

Common Mistakes:

• Confusing reversing bits with flipping bits (0 to 1)
• Thinking reversing bits changes the number by adding or multiplying
• Assuming reversing bits means reversing digits in decimal

2. Which of the following JavaScript code snippets correctly reverses the bits of an 8-bit number n?

easy

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

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

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

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

Solution

1. Step 1: Analyze the loop and bit operations

   let result = 0; for(let i=0; i<8; i++) { result <<= 1; result |= (n & 1); n >>= 1; } shifts result left, adds least significant bit of n, then shifts n right. This reverses bits correctly.

2. Step 2: Check other options for errors

   let result = 0; for(let i=0; i<8; i++) { result |= (n & 1) << i; n >>= 1; } does not reverse bits, it copies bits in same order. let result = 0; for(let i=7; i>0; i--) { result |= (n & 1) << i; n >>= 1; } shifts bits incorrectly. let result = 0; for(let i=0; i<8; i++) { result += (n & 1) << i; n <<= 1; } shifts n left, which is wrong.

3. Final Answer:

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

4. Quick Check:

   Shift result left + add bit from n right [OK]

Hint: Shift result left, add n's right bit, shift n right [OK]

Common Mistakes:

• Shifting n left instead of right
• Not shifting result before adding bit
• Using wrong loop direction or bit positions

3. What is the output of the following code snippet?

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

console.log(reverseBits(13));

medium

A. 14

B. 11

C. 7

D. 13

Solution

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

   13 in binary (4 bits) is 1101.

2. Step 2: Reverse bits step-by-step

   Loop 4 times: result builds as follows:
   i=0: result=0<<1=0 + (13&1=1) =1
   n=13>>1=6 (0110)
   i=1: result=1<<1=2 + (6&1=0) =2
   n=6>>1=3 (0011)
   i=2: result=2<<1=4 + (3&1=1) =5
   n=3>>1=1 (0001)
   i=3: result=5<<1=10 + (1&1=1) =11

3. Final Answer:

   11 -> Option B

4. Quick Check:

   Reverse 1101 = 1011 (binary 11 decimal) [OK]

Hint: Trace bit shifts and OR operations carefully [OK]

Common Mistakes:

• Confusing decimal and binary values
• Not shifting result before OR
• Looping wrong number of times

4. Find the error in this bit reversal function and choose the corrected version:

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

medium

A. Change loop to run 16 times

B. Shift n left instead of right

C. Initialize result with 1 instead of 0

D. Swap the order: shift result left before OR operation

Solution

1. Step 1: Identify order of operations

   Current code ORs bit then shifts result left, causing last bit to be lost.

2. Step 2: Correct by shifting result left before OR

   Shift result left first, then OR with current bit to build reversed bits correctly.

3. Final Answer:

   Swap the order: shift result left before OR operation -> Option D

4. Quick Check:

   Shift before OR to keep all bits [OK]

Hint: Always shift result left before adding new bit [OK]

Common Mistakes:

• Shifting result after OR loses last bit
• Shifting n left instead of right
• Wrong loop count for bit size

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 check if reversed number equals its own reverse

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

C. Reverse bits using a loop, then compare reversed number with original

D. Reverse bits using a loop, then convert to decimal and check if even

Solution

1. Step 1: Reverse bits of the number

   Use a loop to reverse all 16 bits correctly.

2. Step 2: Check palindrome by comparing reversed number with its own reverse

   If reversed number equals its reverse, it is a binary palindrome.

3. Final Answer:

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

4. Quick Check:

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

Hint: Check palindrome by comparing reversed number to its reverse [OK]

Common Mistakes:

• Comparing reversed number directly to original (wrong for palindrome)
• Checking decimal evenness instead of binary palindrome
• Reversing bits twice unnecessarily