Blind 75.15 - Reverse Bits

Reverse bits.

Problem description

Taken directly from LeetCode.

Reverse bits of a given 32 bits unsigned integer.

Note:

• Note that in some languages, such as Java, there is no unsigned integer type. In this case, both input and output will be given as a signed integer type. They should not affect your implementation, as the integer’s internal binary representation is the same, whether it is signed or unsigned.
• In Java, the compiler represents the signed integers using 2’s complement notation. Therefore, in Example 2 above, the input represents the signed integer -3 and the output represents the signed integer -1073741825.

Example 1:

Input: n = 00000010100101000001111010011100
Output: 964176192 (00111001011110000010100101000000)
Explanation: The input binary string 00000010100101000001111010011100 represents the unsigned integer 43261596, so return 964176192 which its binary representation is 00111001011110000010100101000000.

Example 2:

Input: n = 11111111111111111111111111111101
Output: 3221225471 (10111111111111111111111111111111)
Explanation: The input binary string 11111111111111111111111111111101 represents the unsigned integer 4294967293, so return 3221225471 which its binary representation is 10111111111111111111111111111111.

Constraints:

• The input must be a binary string of length 32

Follow up: If this function is called many times, how would you optimize it?

Solution type

Algorithmic - no specific category of solution.

Solution

The obvious solution is to mask each bit and OR it at the appropriate position: bit 0’s value is OR’d at output bit 31, bit 1’s value is OR’d at output bit 30, so on and so forth. It’s not the solution I am going to use because it feels too slow for the problem.

The question is how we can use bit operations to speed this up at all. It feels like you’re supposed to use the negation of the bitstring? But I don’t exactly get how; performing further bit operations on that bitstring is unhelpful.

It can’t be one single operation on the negation. Consider the 4-bit string 1110, whose reverse would be 0111. We cannot arrive at our solution by doing 1110 ? 0001 because this ? operator, given the same inputs (1,0), would have to map MSB 1 to 0 and then map the two middle 1 bits to 1. This isn’t a function. So either we cannot simply use the negation, or we cannot use bit operations alone and have to do some sort of traversal of the bitstring.

Yeah, I don’t see a second operand to a possible binary operation that makes the truth table work. Except for 0111 itself, but getting that operand requires solving the problem in the first place. I’m just going to go for the easy solution.

def reverseBits(self, n: int) -> int:
    out, mask_n, mask_out = 0, 1, 1 << 31
    for i in range(32):
        if n & mask_n:
            out |= mask_out
        mask_n, mask_out = mask_n << 1, mask_out >> 1
    return out

Umm…this is the efficient solution apparently? It makes perfect sense after following the reasoning about the lack of possible \(O(1)\) solutions (i.e. the fact that there’s no way for us to get a working truth table on a binary operation). \(O(\log w)\)¹ feels sensible; you need to do \(O(1)\) work per bit in the integer.

I guess this problem serves as a reminder not to look for solutions that aren’t there. If it seems too good to be true, ask whether or not it’s even possible in the first place. Establishing a lower bound would’ve been helpful for some of the other problems I’ve done.

1. The problem constraints suggest that we should think of this as a constant-time algorithm because we always have a 32-bit integer. I prefer saying \(O(\log w)\) because that generalizes better to integers of different widths. ↩