Reverse Bit Order
Problem
Treat a non-negative whole number as a fixed field of 32 binary digits, padded with zeros on the left. Return the value you get by reversing the order of those 32 digits, so the lowest digit becomes the highest and vice versa. The width is always 32, whatever the size of the input.
Examples
Input: value = 1
Output: 2147483648
Why: the single low digit moves all the way to the top of the fieldInput: value = 3
Output: 3221225472
Why: the two low digits become the two highest onesInput: value = 0
Output: 0
Why: edge case, a field of zeros reads the same in either directionHints
0 / 3
Turning the number into text, reversing the text and reading it back works, but the whole point here is to do it with arithmetic on the number itself.
Build the answer digit by digit. Reading the input from its lowest digit upwards produces exactly the order in which the answer needs its digits appended.
Repeat 32 times: make room in the result by shifting it one place up, copy the lowest digit of the input into that room, then shift the input one place down. Exactly 32 rounds are what fixes the field width.
Solution
Reading the input from the bottom up and writing the result from the bottom up produces the reversal for free, because the first digit read ends up pushed the furthest left by the later shifts. Each round shifts the result up to open a slot, copies the input's lowest digit into it with a mask and an or, then discards that digit from the input. Running exactly 32 rounds is what pads a small number out to the full field width instead of stopping early. Time is O(32), which is constant, and space is O(1).
def reverse_bits(value):
result = 0
for _ in range(32): # a fixed width, whatever the input size
result = (result << 1) | (value & 1) # open a slot, copy the low digit
value >>= 1 # drop the digit just consumed
return result
print(reverse_bits(1)) # -> 2147483648
print(reverse_bits(3)) # -> 3221225472
print(reverse_bits(0)) # -> 0Stuck on the idea rather than the code? Binary and Bitwise Ops covers it.