Reverse Bits

▶

Steps

setup

Initialize Input Number

We start with the input number n = 43261596. Its 32-bit binary representation is displayed to establish the initial state.

💡 Seeing the original bits helps understand how the reversal transforms this exact pattern step-by-step.

Line:

def reverseBits(n: int) -> int:

💡 The input number's bits are the starting point for all subsequent bit manipulations.

expand

Swap Odd and Even Bits

Swap every pair of bits: odd bits are shifted right and masked, even bits are shifted left and masked, then combined with OR.

💡 This step reverses bits in pairs, the smallest unit of swapping, setting the foundation for larger swaps.

Line:

n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)

💡 Mask 0x55555555 isolates bits in odd positions to swap with even positions.

expand

Swap Bit Pairs

Swap every 2-bit pair: right shift by 2 and mask with 0x33333333, left shift by 2 and mask, then OR to combine.

💡 This step reverses bits in groups of two pairs, building on the previous pair swaps.

Line:

n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)

💡 Mask 0x33333333 isolates pairs of bits for swapping.

expand

Swap Nibbles (4-bit groups)

Swap every 4-bit nibble: right shift by 4 and mask with 0x0f0f0f0f, left shift by 4 and mask, then OR to combine.

💡 This step reverses bits in 8-bit groups by swapping nibbles, further reversing the bit order.

Line:

n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)

💡 Mask 0x0f0f0f0f isolates nibbles for swapping.

expand

Swap Bytes (8-bit groups)

Swap every byte: right shift by 8 and mask with 0x00ff00ff, left shift by 8 and mask, then OR to combine.

💡 This step reverses bits in 16-bit groups by swapping bytes, continuing the reversal process.

Line:

n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)

💡 Mask 0x00ff00ff isolates bytes for swapping.

expand

Swap 16-bit Halves

Swap the two 16-bit halves by right shifting 16 bits and left shifting 16 bits, then OR and mask to 32 bits.

💡 This final swap reverses the two halves, completing the full 32-bit reversal.

Line:

n = ((n >> 16) | (n << 16)) & 0xffffffff

💡 Swapping halves completes the bit reversal by moving the left half to the right and vice versa.

reconstruct

Return Final Reversed Number

The final reversed integer is returned as 964176192, matching the expected output.

💡 This step confirms the algorithm's correctness by producing the reversed bit integer.

Line:

return n

💡 The reversed bits correspond to the decimal output 964176192.

def reverseBits(n: int) -> int:
    # STEP 2: Swap odd and even bits
    n = ((n >> 1) & 0x55555555) | ((n & 0x55555555) << 1)
    # STEP 3: Swap pairs of bits
    n = ((n >> 2) & 0x33333333) | ((n & 0x33333333) << 2)
    # STEP 4: Swap nibbles (4 bits)
    n = ((n >> 4) & 0x0f0f0f0f) | ((n & 0x0f0f0f0f) << 4)
    # STEP 5: Swap bytes
    n = ((n >> 8) & 0x00ff00ff) | ((n & 0x00ff00ff) << 8)
    # STEP 6: Swap 16-bit halves
    n = ((n >> 16) | (n << 16)) & 0xffffffff
    # STEP 7: Return final reversed number
    return n

if __name__ == '__main__':
    print(reverseBits(43261596))  # Expected: 964176192

📊

Reverse Bits - Watch the Algorithm Execute, Step by Step

Watching each bit manipulation step reveals how masks and shifts rearrange bits efficiently without looping over each bit individually.

Initial input

A

1

0

0

1

1

1

0

0

=43261596

B

Swap odd and even bits

A

1

0

0

1

1

1

0

0

=43261596

B

────────────────

=

0

1

0

1

1

0

0

0

=22717728

💡 Pairs of bits are swapped using mask 0x55555555 and shifts.

Swap pairs of bits

A

0

1

0

1

1

0

0

0

=22717728

B

────────────────

=

0

0

1

1

0

1

0

0

=11874313

💡 Pairs of bits are swapped in 4-bit groups using mask 0x33333333.

Swap nibbles (4 bits)

A

0

0

1

1

0

1

0

0

=11874313

B

────────────────

=

0

0

1

1

0

1

0

1

=1185973

💡 Nibbles are swapped using mask 0x0f0f0f0f and shifts.

Swap bytes (8 bits)

A

0

0

1

1

0

1

0

1

=1185973

B

────────────────

=

0

0

1

1

0

1

0

1

=263526

💡 Bytes are swapped using mask 0x00ff00ff and shifts.

Swap 16-bit halves

A

0

0

1

1

0

1

0

1

=263526

B

────────────────

=

1

0

1

0

0

0

0

0

=964176192

💡 16-bit halves swapped to complete full bit reversal.

Return reversed bits

A

1

0

1

0

0

0

0

0

=964176192

B

────────────────

=

1

0

1

0

0

0

0

0

=964176192

💡 Final reversed bit pattern matches expected output.

Key Takeaways

✓ Bit reversal can be done efficiently by swapping bits in progressively larger groups using masks and shifts.

This insight is hard to see from code alone because the masks and shifts look like magic without visualizing their effect on bits.

✓ Masks like 0x55555555, 0x33333333, etc., isolate specific bit groups to enable targeted swaps.

Understanding how masks select bits clarifies why each step swaps exactly the intended bit groups.

✓ The final swap of 16-bit halves completes the reversal, showing how the algorithm builds from small to large bit groups.

Seeing the final step visually confirms the cumulative effect of all previous swaps.

Practice

1. You are given an array containing n-2 distinct integers from the range 1 to n. Exactly two numbers are missing from the array. Which algorithmic approach guarantees finding these two missing numbers in O(n) time and O(1) extra space?

easy

A. Use XOR partitioning to separate numbers based on a set bit and find missing numbers.

B. Use a greedy approach to pick missing numbers by scanning the array once.

C. Use dynamic programming to build a table of sums and identify missing numbers.

D. Use a brute force nested loop to check all pairs of missing numbers.

Solution

1. Step 1: Understand problem constraints

   We have an array missing exactly two numbers from 1 to n, and need an efficient solution.

2. Step 2: Identify suitable algorithm

   XOR partitioning leverages bitwise properties to find missing numbers in linear time and constant space, unlike brute force or DP which are slower or use extra space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   XOR partitioning runs in O(n) time and O(1) space [OK]

Hint: XOR partitioning splits numbers by set bit efficiently [OK]

Common Mistakes:

• Assuming brute force is efficient enough
• Confusing DP with sum-based methods
• Thinking greedy can find missing pairs

2. You are given an array where exactly two elements appear only once and all the other elements appear exactly twice. Which approach guarantees finding these two unique elements in linear time and constant space?

easy

A. Use XOR of all elements, then partition the array by a set bit of the XOR result and XOR partitions separately.

B. Sort the array and scan linearly to find the two unique elements.

C. Use a hash map to count occurrences and then collect elements with count one.

D. Use a greedy approach to pick elements that appear once by checking neighbors.

Solution

1. Step 1: Understand the problem constraints

   Two unique elements appear once, others appear twice. We want O(n) time and O(1) space.

2. Step 2: Identify the approach that uses XOR partitioning

   XOR all elements to get xor = num1 ^ num2. Find a set bit in xor to partition elements into two groups, each containing one unique number. XOR each group separately to find the unique numbers.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting is O(n log n), hash map uses extra space, greedy fails on duplicates [OK]

Hint: XOR partitioning splits unique numbers by differing bit [OK]

Common Mistakes:

• Assuming sorting is linear time
• Using hash map violates O(1) space
• Greedy fails on duplicates

3. Given the following code and input, what is the final returned list?

easy

A. [2, 5]

B. [5, 4]

C. [4, 5]

D. [2, 4]

Solution

1. Step 1: Compute xor of all elements

   xor = 2 ^ 4 ^ 2 ^ 5 = (2 ^ 2) ^ 4 ^ 5 = 0 ^ 4 ^ 5 = 1 (binary 0001)

2. Step 2: Find rightmost set bit and partition

   set_bit = xor & (-xor) = 1 & (-1) = 1. Partition nums by bit 1: group1 (bit set): 5, group2 (bit not set): 2,4,2. XOR group1 = 5, XOR group2 = 4.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches unique elements [OK]

Hint: Rightmost set bit partitions unique numbers correctly [OK]

Common Mistakes:

• Mixing order of output
• Incorrect xor calculation
• Miscomputing set bit

4. Suppose you want to generate all permutations of n elements but now elements can be reused any number of times (i.e., permutations with repetition). Which modification to the bitmask DP approach is correct?

hard

A. Use iterative DP over sequence length without bitmask since visited state is irrelevant

B. Keep bitmask DP but allow setting bits multiple times to reuse elements

C. Remove bitmask tracking and use simple recursion with repeated choices allowed

D. Use bitmask DP but reset dp states after each iteration to allow reuse

Solution

1. Step 1: Understand reuse means no visited tracking needed

   Since elements can be reused, the visited bitmask is no longer meaningful.

2. Step 2: Use DP over sequence length only

   Iterative DP over length with choices from all elements at each step correctly generates permutations with repetition.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmask DP is unnecessary when elements can be reused [OK]

Hint: Reuse means no visited bitmask needed; track length only [OK]

Common Mistakes:

• Trying to reuse bitmask DP without modification
• Allowing bits to be set multiple times breaks bitmask logic

5. If the input array can contain negative numbers and the bit counting approach is used, what modification is necessary to correctly find the single number?

hard

A. Use a 32-bit mask and handle sign bit separately to avoid sign extension errors.

B. Use a hash map instead, as bit counting cannot handle negatives.

C. Convert all numbers to positive before bit counting and restore sign later.

D. No modification needed; bit counting works the same for negatives.

Solution

1. Step 1: Understand bit counting with negative numbers

   Negative numbers use two's complement; sign bit must be handled carefully to avoid incorrect counts.

2. Step 2: Apply 32-bit mask and handle sign bit

   Counting bits with a mask ensures correct accumulation; sign bit handled separately prevents sign extension issues.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Proper masking ensures correct bit counts for negatives [OK]

Hint: Mask bits to handle sign bit correctly in negative numbers [OK]

Common Mistakes:

• Ignoring sign bit causes wrong results
• Assuming negatives behave like positives