Reverse Bits

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

Reverse bits of a given 32 bits unsigned integer.

For example, given input 43261596 (represented in binary as 00000010100101000001111010011100), return 964176192 (represented in binary as00111001011110000010100101000000).

Follow up:
If this function is called many times, how would you optimize it?

This question is much related with Number of 1 Bits

Solution 1:

<br />
class Solution {<br />
public:<br />
    uint32_t reverseBits(uint32_t n)<br />
    {<br />
        uint32_t i;<br />
        uint32_t value = 0;<br />
        for (i = 0; i &lt; 32; ++i)<br />
        {<br />
            uint32_t tmp = (uint32_t)(n &amp; ((uint32_t)1 &lt;&lt; (31 - i))) ? 1 : 0;<br />
            value |= tmp &lt;&lt; i;<br />
        }<br />
        return value;<br />
    }<br />
};

Solution 2:

<br />
uint32_t reverse(uint32_t x)<br />
{<br />
    x = ((x &gt;&gt; 1) &amp; 0x55555555u) | ((x &amp; 0x55555555u) &lt;&lt; 1);<br />
    x = ((x &gt;&gt; 2) &amp; 0x33333333u) | ((x &amp; 0x33333333u) &lt;&lt; 2);<br />
    x = ((x &gt;&gt; 4) &amp; 0x0f0f0f0fu) | ((x &amp; 0x0f0f0f0fu) &lt;&lt; 4);<br />
    x = ((x &gt;&gt; 8) &amp; 0x00ff00ffu) | ((x &amp; 0x00ff00ffu) &lt;&lt; 8);<br />
    x = ((x &gt;&gt; 16) &amp; 0xffffu) | ((x &amp; 0xffffu) &lt;&lt; 16);<br />
    return x;<br />
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *