Reverse Bits

🏠 ⬅️ ➡️

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?

Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer(kind=4), parameter :: n = 0_4
    integer(kind=4), parameter :: expected = 964176192_4
    integer(kind=4), parameter :: result = reverseBits(n)

    if (result /= expected) then
        write (*,*) 'Test 1 failed!'
        stop 1
    end if

    integer(kind=4), parameter :: n2 = 11111111111111111111111111111101_4
    integer(kind=4), parameter :: expected2 = 3221225471_4
    integer(kind=4), parameter :: result2 = reverseBits(n2)

    if (result2 /= expected2) then
        write (*,*) 'Test 2 failed!'
        stop 1
    end if

    contains

    pure function reverseBits(n) result(r)
        implicit none
        integer(kind=4), intent(in) :: n
        integer(kind=4) :: r

        r = iand(n, 1_4) * 8_4 &
            + iand(n, 2_4) * 4_4 &
            + iand(n, 4_4) * 2_4 &
            + iand(n, 8_4) * 1_4 &
            + iand(n, 16_4) * 8_4 &
            + iand(n, 32_4) * 4_4 &
            + iand(n, 64_4) * 2_4 &
            + iand(n, 128_4) * 1_4 &
            + iand(n, 256_4) * 8_4 &
            + iand(n, 512_4) * 4_4 &
            + iand(n, 1024_4) * 2_4 &
            + iand(n, 2048_4) * 1_4 &
            + iand(n, 4096_4) * 8_4 &
            + iand(n, 8192_4) * 4_4 &
            + iand(n, 16384_4) * 2_4 &
            + iand(n, 32768_4) * 1_4 &
            + iand(n, 65536_4) * 8_4 &
            + iand(n, 131072_4) * 4_4 &
            + iand(n, 262144_4) * 2_4 &
            + iand(n, 524288_4) * 1_4 &
            + iand(n, 1048576_4) * 8_4 &
            + iand(n, 2097152_4) * 4_4 &
            + iand(n, 4194304_4) * 2_4 &
            + iand(n, 8388608_4) * 1_4 &
            + iand(n, 16777216_4) * 8_4 &
            + iand(n, 33554432_4) * 4_4 &
            + iand(n, 67108864_4) * 2_4 &
            + iand(n, 134217728_4) * 1_4 &
            + iand(n, 268435456_4) * 8_4 &
            + iand(n, 536870912_4) * 4_4 &
            + iand(n, 1073741824_4) * 2_4 &
            + iand(n, -2147483648_4) * 1_4
    end function reverseBits
❌ Compiled
❌ Executed
❌ Correct 
! This program reverses the bits of a given 32-bit unsigned integer.

program bit_reverse

implicit none

integer :: n, i, j, k, l, m, n_reversed
character(len=32) :: input_string, output_string

! Read the input from the command line
call get_command_argument(1, input_string)
read(input_string,*) n

! Initialize the output string
output_string = ""

! Reverse the bits of the input integer
do i = 1, 32
    k = mod(n, 2)
    n = n / 2
    l = mod(n, 2)
    n = n / 2
    m = mod(n, 2)
    n = n / 2
    j = mod(n, 2)
    n = n / 2
    i = mod(n, 2)
    n = n / 2
    output_string = char(ichar(output_string) + k) // char(ichar(output_string) + l) // char(ichar(output_string) + m) // char(ichar(output_string) + j) // char(ichar(output_string) + i)
end do

! Print the output
write(*,*) "The reversed bits of the input integer are: ", output_string

end program bit_reverse
🌐 Data from online sources 
def reverse_bits(n: int) -> int:
    res = 0
    for _ in range(32):
        res <<= 1
        res |= n & 1
        n >>= 1
    return res

The algorithm iterates through all 32 bits of the given unsigned 32-bit integer, and for each bit, it shifts the result variable res one position to the left, and then performs a bitwise OR with the given number n ANDed with 1. This operation adds the least significant bit of n to the most significant bit of res. Then, the given number n is shifted one position to the right. The process is repeated for all 32 bits, and in each step, the result variable res accumulates the reversed bits of the input number.

🌐 Data from online sources 
unsigned int reverseBits(unsigned int n) {
    unsigned int res = 0;
    for (int i = 0; i < 32; ++i) {
        res <<= 1;
        res |= n & 1;
        n >>= 1;
    }
    return res;
}

The algorithm iterates through all 32 bits of the given unsigned 32-bit integer, and for each bit, it shifts the result variable res one position to the left, and then performs a bitwise OR with the given number n ANDed with 1. This operation adds the least significant bit of n to the most significant bit of res. Then, the given number n is shifted one position to the right. The process is repeated for all 32 bits, and in each step, the result variable res accumulates the reversed bits of the input number.