🚀Day 10/180 (Math) 190. Reverse Bits(Leetcode)

190. Reverse Bits

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

Code :

public class Solution {

    public int reverseBits(int num) {

        num = ((num & 0xffff0000) >>> 16) | ((num & 0x0000ffff) << 16);
        num = ((num & 0xff00ff00) >>> 8) | ((num & 0x00ff00ff) << 8);
        num = ((num & 0xf0f0f0f0) >>> 4) | ((num & 0x0f0f0f0f) << 4);
        num = ((num & 0xcccccccc) >>> 2) | ((num & 0x33333333) << 2);
        num = ((num & 0xaaaaaaaa) >>> 1) | ((num & 0x55555555) << 1);

        return num;

    }
}

Let's perform a dry run of the reverseBits function using an example integer.

Example Input:

Let's take num = 0b00000010100101000001111010011100 (which is 43261596 in decimal).

Step-by-Step Execution:

1. Initial value:

    num = 0b00000010100101000001111010011100
   

2. First operation:

    num = ((num & 0xffff0000) >>> 16) | ((num & 0x0000ffff) << 16)
   

   Breaking it down:

   • (num & 0xffff0000) >>> 16 isolates the higher 16 bits and shifts them right by 16 positions.

   • (num & 0x0000ffff) << 16 isolates the lower 16 bits and shifts them left by 16 positions. Result:

    num = 0b00001111010011100000000000000010

3. Second operation:

    num = ((num & 0xff00ff00) >>> 8) | ((num & 0x00ff00ff) << 8)
   

   Breaking it down:

   • (num & 0xff00ff00) >>> 8 isolates 8-bit groups and shifts them right by 8 positions.

   • (num & 0x00ff00ff) << 8 isolates the remaining 8-bit groups and shifts them left by 8 positions. Result:

    num = 0b10011100000000001111010000000010

4. Third operation:

    num = ((num & 0xf0f0f0f0) >>> 4) | ((num & 0x0f0f0f0f) << 4)
   

   Breaking it down:

   • (num & 0xf0f0f0f0) >>> 4 isolates 4-bit groups and shifts them right by 4 positions.

   • (num & 0x0f0f0f0f) << 4 isolates the remaining 4-bit groups and shifts them left by 4 positions. Result:

    num = 0b11110000000000001011100000001010

5. Fourth operation:

    num = ((num & 0xcccccccc) >>> 2) | ((num & 0x33333333) << 2)
   

   Breaking it down:

   • (num & 0xcccccccc) >>> 2 isolates pairs of bits and shifts them right by 2 positions.

   • (num & 0x33333333) << 2 isolates the remaining pairs and shifts them left by 2 positions. Result:

    num = 0b11000000000000001011000010101010

6. Fifth operation:

    num = ((num & 0xaaaaaaaa) >>> 1) | ((num & 0x55555555) << 1)
   

   Breaking it down:

   • (num & 0xaaaaaaaa) >>> 1 isolates individual bits and shifts them right by 1 position.

   • (num & 0x55555555) << 1 isolates the remaining individual bits and shifts them left by 1 position. Result:

    num = 0b00111001011110000010100101000000

Final Output:

The function returns:

0b00111001011110000010100101000000

Which is 964176192 in decimal.

Summary:

• Input: 0b00000010100101000001111010011100 (43261596 in decimal)

• Output: 0b00111001011110000010100101000000 (964176192 in decimal)