190. Reverse Bits

Problem Statement

LeetCode: https://leetcode.com/problems/reverse-bits

What we have to do: Given 32-bit integer, we need to reverse 32 bits.

Solution

This problem can be simple, and easy to solve. But what we need to learn is how to use bitwise logic to solve this problem. There are 4 methods to solve this problem:

1. The bitwise way
2. String reverse
3. Simple and standard way
4. CPU efficient way

Code Repo at: https://github.com/mrunalnshah/Algorithms/tree/main/00_Bits-and-Computers/Arena/0190_Reverse-Bits

Python Solution

Python Solution: https://github.com/mrunalnshah/Algorithms/tree/main/00_Bits-and-Computers/Arena/0190_Reverse-Bits/Python

Method 1: The Bitwise way Code

class Solution:
    def reverseBits(self, n: int) -> int:  
        result = 0
 
        for _ in range(32):
            result = result << 1
            result += (n & 1)
            n = n >> 1
 
        return result

Explanation:

Method 2: String Reverse Code

class Solution:
    def reverseBits(self, n: int) -> int:  
        bin_n = format(n & 0xFFFFFFFF, '032b')
        bin_list = list(bin_n)
 
        i = 0
        j = len(bin_list) - 1
 
        while i <= j:
            temp = bin_list[i]
            bin_list[i] = bin_list[j]
            bin_list[j] = temp
            
            i += 1
            j -= 1
 
        return int(''.join(bin_list), 2)

Method 3: Pythonic Way Code

class Solution:
    def reverseBits(self, n: int) -> int:  
        n &= 0xFFFFFFFF
 
        return int(f'{n:032b}'[::-1], 2)

Method 4: Efficient, and the CPU way (bit reversal by parallel bit swaps) Code

class Solution:
    def reverseBits(self, n: int) -> int:  
        n &= 0xFFFFFFFF
  
 
        n &= 0xFFFFFFFF
        n = ((n >> 1)  & 0x55555555) | ((n & 0x55555555) << 1)
        n = ((n >> 2)  & 0x33333333) | ((n & 0x33333333) << 2)
        n = ((n >> 4)  & 0x0F0F0F0F) | ((n & 0x0F0F0F0F) << 4)
        n = ((n >> 8)  & 0x00FF00FF) | ((n & 0x00FF00FF) << 8)
        n = ( n >> 16)               | ( n               << 16)
 
        return n & 0xFFFFFFFF