Reverse Bits

Prob:

Sol:
class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t output = 0;
        for (int i = 0; i < 32; i++) {
            output <<= 1;
            output |= (n & 1);
            n >>= 1;
        }
        return output;
    }
};

Other solution:

unsigned int reverseBits(unsigned int num)

{

    unsigned int count = sizeof(num) * 8 - 1;

    unsigned int reverse_num = num;

     

    num >>= 1;

    while(num)

    {

       reverse_num <<= 1;      

       reverse_num |= num & 1;

       num >>= 1;

       count--;

    }

    reverse_num <<= count;

    return reverse_num;

}

Method 3 – Lookup Table:
We can reverse the bits of a number in O(1) if we know the size of the number. We can implement it using look up table.




Method 4:

class Solution { public: uint32_t reverseBits(uint32_t n) { n = (n & 0xffff0000) >> 16 | (n & 0x0000ffff) << 16; n = (n & 0xff00ff00) >> 8 | (n & 0x00ff00ff) << 8; n = (n & 0xf0f0f0f0) >> 4 | (n & 0x0f0f0f0f) << 4; n = (n & 0xcccccccc) >> 2 | (n & 0x33333333) << 2; n = (n & 0xaaaaaaaa) >> 1 | (n & 0x55555555) << 1; return n; } };