Reverse Bits of a Number in DSA Typescript - Deep Dive

Overview - Reverse Bits of a Number

What is it?

Reversing bits of a number means flipping the order of its binary digits. For example, if a number's binary form is 1011, reversing bits would make it 1101. This operation changes the number's value by rearranging its bits from right to left. It is a common task in low-level programming and algorithms.

Why it matters

Reversing bits is important in areas like cryptography, graphics, and network protocols where bit-level manipulation is needed. Without this concept, programmers would struggle to efficiently transform data at the binary level, leading to slower or more complex code. It helps optimize performance and solve problems that depend on bit patterns.

Where it fits

Before learning this, you should understand binary numbers and bitwise operations like AND, OR, and shifts. After mastering bit reversal, you can explore advanced bit manipulation techniques and algorithms that rely on bit patterns, such as Gray codes or fast multiplication.

Mental Model

Core Idea

Reversing bits flips the binary digits of a number so the leftmost bit becomes the rightmost, and vice versa.

Think of it like...

Imagine a row of light switches turned on or off. Reversing bits is like walking to the other end of the row and flipping the order of the switches exactly backwards.

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

Build-Up - 6 Steps

1

Foundation

Understanding Binary Representation

Concept: Learn how numbers are represented in binary form using bits.

Every number can be shown as a sequence of 0s and 1s called bits. For example, the number 13 in binary is 1101. Each bit represents a power of two, starting from the right with 2^0. Understanding this helps us manipulate numbers at the bit level.

Result

You can convert decimal numbers to binary and see their bit patterns.

Knowing binary representation is essential because reversing bits only makes sense when you understand what each bit means.

2

Foundation

Basics of Bitwise Operations

Concept: Introduce bitwise operators like AND, OR, XOR, and bit shifts.

Bitwise operations work directly on bits. For example, shifting bits to the right (>>) moves all bits one place to the right, dropping the last bit. AND (&) compares bits and returns 1 only if both bits are 1. These operations let us read and change bits individually.

Result

You can manipulate bits to isolate or change specific parts of a number.

Bitwise operations are the tools needed to reverse bits efficiently.

3

Intermediate

Reversing Bits by Shifting and Masking

🤔Before reading on: do you think reversing bits requires storing all bits first or can it be done on the fly? Commit to your answer.

Concept: Use a loop to extract bits from right to left and build the reversed number from left to right.

Start with a result of 0. For each bit in the original number, shift the result left by 1 to make space, then add the extracted rightmost bit of the original number. Shift the original number right by 1 to process the next bit. Repeat until all bits are processed.

Result

The reversed number has bits in the opposite order of the original.

This method shows how bitwise shifts and masks combine to reverse bits without extra storage.

4

Intermediate

Handling Fixed Bit Widths

🤔Before reading on: do you think reversing bits changes the number of bits or keeps it fixed? Commit to your answer.

Concept: Reverse bits assuming a fixed number of bits (like 8, 16, or 32) to keep consistent results.

Decide the bit width (e.g., 8 bits). Always process exactly that many bits, even if leading bits are zero. This ensures the reversed number fits the same size and behaves predictably.

Result

Reversed bits have the same length as the original number's bit width.

Fixing bit width avoids confusion and errors when reversing numbers with leading zeros.

5

Advanced

Optimizing Bit Reversal with Lookup Tables

🤔Before reading on: do you think reversing bits can be faster than looping through each bit? Commit to your answer.

Concept: Use precomputed tables to reverse small chunks of bits quickly and combine results.

Create a table that stores reversed values for all 8-bit numbers (0 to 255). To reverse a 32-bit number, split it into four 8-bit parts, reverse each using the table, then combine them in reverse order. This reduces computation time.

Result

Bit reversal runs faster by avoiding bit-by-bit loops.

Lookup tables trade memory for speed, a common optimization in performance-critical code.

6

Expert

Bit Reversal in Hardware and Algorithms

🤔Before reading on: do you think bit reversal is only a software trick or also used in hardware? Commit to your answer.

Concept: Bit reversal is used in hardware circuits and algorithms like Fast Fourier Transform (FFT) for efficient data reordering.

Hardware can reverse bits using wiring patterns or special instructions. In FFT algorithms, bit-reversed indexing rearranges data for faster computation. Understanding this helps optimize both software and hardware implementations.

Result

Bit reversal is a fundamental operation beyond simple coding tasks.

Knowing bit reversal's role in hardware and algorithms reveals its deep importance in computing.

Under the Hood

Reversing bits works by shifting bits out of the original number one by one from the right and inserting them into the result from the left. Internally, the CPU uses shift and mask instructions to isolate and move bits. The process involves bitwise AND to extract bits and bitwise OR to set bits in the result. This low-level manipulation is efficient because it uses simple CPU instructions.

Why designed this way?

This approach was chosen because CPUs natively support bit shifts and masks, making bit reversal fast and memory-efficient. Alternatives like converting to strings or arrays are slower and use more memory. Hardware implementations use wiring or dedicated instructions to speed up bit reversal for critical applications.

Original number bits:  [b7][b6][b5][b4][b3][b2][b1][b0]
Process:               Extract b0 -> place as new b7
                       Extract b1 -> place as new b6
                       ...
                       Extract b7 -> place as new b0
Result bits:            [b0][b1][b2][b3][b4][b5][b6][b7]

Myth Busters - 3 Common Misconceptions

Quick: Does reversing bits always produce the same decimal number? Commit to yes or no.

Common Belief: Reversing bits just flips the number but keeps its decimal value similar.

Reality: Reversing bits usually changes the decimal value drastically because bit positions represent different powers of two.

Why it matters: Assuming the decimal value stays similar leads to wrong expectations and bugs in calculations.

Quick: Do you think reversing bits requires converting the number to a string first? Commit to yes or no.

Common Belief: You must convert the number to a binary string to reverse bits.

Reality: Bit reversal can be done directly with bitwise operations without any string conversion.

Why it matters: Using strings is inefficient and unnecessary, causing slower code and higher memory use.

Quick: Is reversing bits the same as reversing the digits of the decimal number? Commit to yes or no.

Common Belief: Reversing bits is like reversing the decimal digits of a number.

Reality: Bits and decimal digits are different representations; reversing bits changes the binary pattern, not decimal digits.

Why it matters: Confusing these leads to incorrect implementations and misunderstandings of bit manipulation.

Expert Zone

1

Bit reversal can be combined with other bit tricks like counting set bits or parity checks for complex algorithms.

2

Endianness (byte order) affects how bit reversal results are interpreted in multi-byte numbers.

3

Some CPUs have special instructions for bit reversal, which can be leveraged for performance gains.

When NOT to use

Avoid bit reversal when working with floating-point numbers or data where bit order does not matter. Instead, use higher-level abstractions or libraries that handle data formats safely.

Production Patterns

Bit reversal is used in graphics shaders for pixel manipulation, network protocols for checksum calculations, and signal processing algorithms like FFT for data reordering.

Connections

Fast Fourier Transform (FFT)

Bit reversal is used to reorder input data in FFT algorithms.

Understanding bit reversal helps grasp how FFT rearranges data efficiently for fast computation.

Endianness in Computer Architecture

Both involve ordering of bits or bytes but at different scales.

Knowing bit reversal clarifies how data representation changes between systems with different endianness.

Mirror Symmetry in Geometry

Bit reversal mirrors the bit pattern just like symmetry mirrors shapes.

Recognizing this connection deepens understanding of symmetry concepts across math and computing.

Common Pitfalls

#1 Ignoring fixed bit width leads to incorrect reversed values.

Wrong approach:

function reverseBits(num: number): number {
let result = 0;
while (num > 0) {
result = (result << 1) | (num & 1);
num >>= 1;
}
return result;
}

Correct approach:

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

Root cause:

Not processing all bits causes loss of leading zeros, changing the bit width and final value.

#2 Using string conversion for bit reversal causes inefficiency.

Wrong approach:

function reverseBits(num: number): number {
const binStr = num.toString(2);
const reversedStr = binStr.split('').reverse().join('');
return parseInt(reversedStr, 2);
}

Correct approach:

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

Root cause:

Misunderstanding that bitwise operations are more efficient than string manipulation for bits.

Key Takeaways

Reversing bits flips the order of binary digits, changing the number's value significantly.

Bitwise operations like shifts and masks enable efficient bit reversal without extra memory.

Always consider fixed bit width to avoid errors with leading zeros during reversal.

Lookup tables and hardware instructions can optimize bit reversal for performance-critical tasks.

Bit reversal is fundamental in algorithms and hardware, linking low-level data manipulation to high-level computing.

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