Reverse bits

Given an integer, reverse the bits in it.

Solution

• Test each LSB bit in the given num and push appropriate bit into the result
• Ensure we're moving in the opposite order while constructing result to make the result is reversed.

Code

def reverse_bits(num)
    return 0 if num == 0
    return 1 if num == 1

    result = 0
    while (num > 0)
        value = num & 1
        result << 1
        result = result ^ 1 if value == 1 # Injects 1 at the LSB
        num = num >> 1
    end
end

Complexity

O(n) time, where n is the number of bits in the number.