Fast(3ms) and easy-understand solution in C/C++


  • 0
    J

    My solution is not very good. However it is quite easy to understand. No magics and no tricks.

    Process

    Suppose we will reverse a bit space named s,

    1. allocate an empty space(0) named z, and an space whose highest bit is 1 named i.

    2. check if the lowest(last) bit of s is 1,

      if (s & 1) { }
      

      if true, then do Bitwise OR:

      z |= i;
      
    3. Right shift z and i and do step 2 until z is empty space(zero).

    Illustration

    Here I will use a byte to illustrate it.

    z = 0000-0000
    i = 1000-0000

    Suppose s = 0000-1001

    After each step:

    1. z = 1000-0000
      i = 0100-0000
      s = 0000-0100

    2. z = 1000-0000
      i = 0010-0000
      s = 0000-0010

    3. z = 1000-0000
      i = 0001-0000
      s = 0000-0001

    4. z = 1001-0000
      i = 0000-1000
      s = 0000-0000
      s is zero, stop the loop.

    Code sample

    
    uint32_t reverseBits(uint32_t s) {
      uint32_t z = 0,  i = 1 << 31;
    
      while ( s ) {
        if (s & 1) z |= i;
        s >>= 1;
        i >>= 1;
      }
    
      return i;
    }
    

    Analysis

    Time Complexity(N bits): O(N). With average O(N/2), worst O(N).
    Space Complexity: O(2N).


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.