Reverse Bits

📋

Problem

Imagine you are working on a low-level networking protocol where you need to reverse the bits of a 32-bit integer to interpret data correctly from a different endian system.

Given a 32-bit unsigned integer, reverse its bits and return the resulting integer. Input: A single 32-bit unsigned integer n. Output: The 32-bit unsigned integer that results from reversing the bits of n.

The input is guaranteed to be a 32-bit unsigned integer.You must treat the input as a 32-bit number regardless of language integer size.

Edge cases: n = 0 → output = 0 (all bits zero)n = 1 → output = 2147483648 (only least significant bit set)n = 4294967295 → output = 4294967295 (all bits set)

</>

IDE

def reverseBits(n: int) -> int:public int reverseBits(int n)int reverseBits(int n)function reverseBits(n)

def reverseBits(n: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int reverseBits(int n) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int reverseBits(int n) {
    // Write your solution here
    return 0;
}

function reverseBits(n) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Loop runs zero times or result never updated; initial result not set or loop missing.✅ Ensure loop runs exactly 32 times and result initialized to 0 before loop.

Wrong: 1Loop runs only once or shifts missing; only least significant bit processed.✅ Run loop 32 times, shifting result left and OR with bit each iteration.

Wrong: 2863311530Swapping bytes or nibbles instead of reversing all bits individually.✅ Process each bit individually in a 32-iteration loop, shifting and ORing bits.

Wrong: 2147483648Off-by-one error causing MSB not to be shifted correctly to LSB or vice versa.✅ Run loop exactly 32 times and shift result left before OR in each iteration.

Wrong: Inefficient algorithm causing time limit exceeded (TLE).✅ Implement O(1) bit reversal using masks or byte-wise lookup table.

✓

Test Cases

Try testing your code on inputs with all bits zero or all bits set to catch base case bugs.

Test with alternating bit patterns to catch subtle bit reversal mistakes.

Consider the time complexity of your approach; optimize to O(1) using bit tricks or caching.

t1_01basic

Input{"n":43261596}

Expected964176192

⏱ Performance - must finish in 2000ms

Binary of input: 00000010100101000001111010011100; reversed bits: 00111001011110000010100101000000; decimal output: 964176192

💡 Think about shifting bits one by one and building the reversed number.

💡 Use a loop that extracts the least significant bit and appends it to the result shifted left.

💡 For each iteration, shift result left by 1 and OR with n's least significant bit, then shift n right by 1.

Why it failed: Output incorrect - likely forgot to shift result left before OR or did not process all 32 bits. Fix by ensuring loop runs 32 times and shifts result left before OR.

✓ Correctly reverses bits by processing all 32 bits with proper shifts.

t1_02basic

Input{"n":1}

Expected2147483648

⏱ Performance - must finish in 2000ms

Input binary: 00000000000000000000000000000001; reversed bits: 10000000000000000000000000000000; decimal output: 2147483648

💡 Check how the least significant bit moves to the most significant position after reversal.

💡 Ensure the loop runs 32 times to shift the single set bit all the way to the left.

💡 Shift result left and OR with bit each iteration; after 32 iterations, the bit is at the highest position.

Why it failed: Output incorrect - likely loop runs fewer than 32 times or shifts incorrectly. Fix by running loop exactly 32 times and shifting result left before OR.

✓ Correctly handles single bit set at LSB moving to MSB after reversal.

t2_01edge

Input{"n":0}

Expected0

⏱ Performance - must finish in 2000ms

All bits zero; reversed bits also all zero; output 0.

💡 Consider the case where input has no bits set.

💡 Reversing zero bits should still yield zero.

💡 Ensure your code handles zero input without errors and returns zero.

Why it failed: Output incorrect - likely not handling zero input properly or returning uninitialized result. Fix by initializing result to 0 and processing all bits.

✓ Correctly returns 0 when input is zero.

t2_02edge

Input{"n":4294967295}

Expected4294967295

⏱ Performance - must finish in 2000ms

All 32 bits set (binary all ones); reversed bits also all ones; output same as input.

💡 Check behavior when all bits are set to 1.

💡 Reversing all ones should yield the same number.

💡 Ensure no bits are lost or zeroed during reversal.

Why it failed: Output incorrect - likely losing bits due to incorrect masking or shifting. Fix by ensuring 32-bit processing and no truncation.

✓ Correctly returns input when all bits are set.

t2_03edge

Input{"n":2147483648}

Expected1

⏱ Performance - must finish in 2000ms

Input binary: 10000000000000000000000000000000; reversed bits: 00000000000000000000000000000001; output 1.

💡 Consider the case where only the most significant bit is set.

💡 Reversing should move this bit to the least significant position.

💡 Ensure shifting and bit extraction logic correctly handles MSB.

Why it failed: Output incorrect - likely not processing MSB correctly or loop ends early. Fix by running loop 32 times and shifting result left before OR.

✓ Correctly reverses MSB to LSB.

t3_01corner

Input{"n":2863311530}

Expected1431655765

⏱ Performance - must finish in 2000ms

Input binary: 10101010101010101010101010101010; reversed bits: 01010101010101010101010101010101; decimal output: 1431655765

💡 Test input with alternating bits to catch bit order mistakes.

💡 Check if your code reverses each bit correctly, not just swaps bytes.

💡 Ensure bit-by-bit reversal, not just byte-wise or nibble-wise swapping.

Why it failed: Output incorrect - likely swapping bytes or nibbles instead of reversing all bits. Fix by processing each bit individually in a loop.

✓ Correctly reverses alternating bit pattern bit-by-bit.

t3_02corner

Input{"n":2147483647}

Expected4294967294

⏱ Performance - must finish in 2000ms

Input binary: 01111111111111111111111111111111; reversed bits: 11111111111111111111111111111110; decimal output: 4294967294

💡 Check handling of numbers with MSB zero and all other bits set.

💡 Ensure no off-by-one errors in loop or bit shifts.

💡 Verify that the highest bit is handled correctly and not lost.

Why it failed: Output incorrect - likely off-by-one in loop or missing last bit. Fix by running loop exactly 32 times and shifting result left before OR.

✓ Correctly reverses bits with MSB zero and others set.

t3_03corner

Input{"n":1431655765}

Expected2863311530

⏱ Performance - must finish in 2000ms

Input binary: 01010101010101010101010101010101; reversed bits: 10101010101010101010101010101010; decimal output: 2863311530

💡 Test the reverse of the alternating bit pattern to catch symmetry errors.

💡 Check if your code is consistent in reversing bits both ways.

💡 Ensure no caching or partial reversal shortcuts that fail on this pattern.

Why it failed: Output incorrect - likely caching or partial reversal logic error. Fix by fully reversing all 32 bits bit-by-bit.

✓ Correctly reverses alternating bit pattern back.

t4_01performance

Input{"n":4294967295}

Expectednull

⏱ Performance - must finish in 2000ms

Input n=4294967295 (all bits set); must complete in O(1) or O(32) time within 2 seconds.

💡 Consider using bit manipulation tricks or byte-wise cache for O(1) time.

💡 Avoid naive bit-by-bit loops if possible for performance.

💡 Use divide and conquer masks or precomputed lookup tables to speed up.

Why it failed: TLE - likely using exponential or inefficient approach. Fix by implementing O(1) bit manipulation or lookup table method.

✓ Efficient bit reversal confirmed within time limit.

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. Given a list of words, you want to find two words that share no common letters and whose lengths' product is maximized. Which approach guarantees an optimal solution efficiently?

easy

A. Represent each word as a bitmask of characters and check pairs using bitwise AND to find the maximum product.

B. Use dynamic programming to build up solutions based on prefixes of words.

C. Use a greedy algorithm that picks the two longest words without checking letter overlap.

D. Sort words by length and use a sliding window to find the maximum product without character checks.

Solution

1. Step 1: Understand the problem constraints

   The problem requires checking if two words share any common letters, which is efficiently done using bitmasks representing character sets.

2. Step 2: Identify the optimal approach

   Bitmasking allows constant-time checks for common characters using bitwise AND, enabling efficient pairwise comparisons and maximum product calculation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitmasking is the standard approach for character set overlap checks [OK]

Hint: Bitmasking enables O(1) character overlap checks [OK]

Common Mistakes:

• Assuming greedy length selection without overlap checks works
• Trying DP on prefixes which doesn't fit this problem
• Using sliding window without character set validation

3. Suppose the input array can contain duplicate numbers and missing numbers may appear multiple times (i.e., numbers can be reused). Which modification to the XOR partitioning approach correctly finds the two missing numbers?

hard

A. Use frequency counting with a hash map instead of XOR to handle duplicates.

B. Use the same XOR partitioning approach since duplicates cancel out in XOR.

C. Modify XOR approach to XOR each number multiple times equal to its frequency.

D. Sort the array and scan for missing numbers instead of XOR.

Solution

1. Step 1: Understand impact of duplicates

   Duplicates break XOR approach because XOR assumes each number appears exactly once.

2. Step 2: Choose correct approach

   Frequency counting with a hash map correctly tracks counts and identifies missing numbers even with duplicates.

3. Step 3: Why other options fail

   Same XOR approach fails due to duplicates; modifying XOR by frequency is not feasible; sorting is O(n log n) and less efficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Frequency counting handles duplicates correctly [OK]

Hint: XOR fails with duplicates; frequency map handles counts [OK]

Common Mistakes:

• Assuming XOR works with duplicates
• Trying to XOR multiple times per frequency
• Ignoring complexity of sorting

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 number n can be negative or zero, and you want to check if its absolute value is a power of four, which modification to the optimal logarithm-based approach is correct?

hard

A. Remove the check for n <= 0 and directly compute log2(n)/2

B. Add a check to return False if n is zero or negative before applying logarithm on abs(n)

C. Use the brute force iterative division approach instead, as logarithm fails for negative inputs

D. Take the absolute value of n before the logarithm check and keep the rest unchanged

Solution

1. Step 1: Consider input domain

   Since n can be zero or negative, these are not powers of four, so must return False immediately.

2. Step 2: Apply logarithm check on absolute value

   After filtering invalid inputs, apply logarithm on abs(n) to check power of four.

3. Step 3: Finalize correct approach

   Adding a check to return False for zero or negative inputs before log check ensures correctness and avoids math domain errors.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Zero and negatives are filtered out before log check on abs(n) [OK]

Hint: Filter invalid inputs before log check on abs(n)

Common Mistakes:

• Removing input validation
• Applying log on negative numbers causing errors