A small, interesting detail you might have overlooked which optimizes the C++ solution from 8ms to 4ms


  • 1
    P

    My naive approach to the problem looks like this. It is the most common solution I came across in the this answer thread:

    class Solution {
    public:
        uint32_t reverseBits(uint32_t n) {
            
            uint32_t reverse= 0;
            int mask = 1;
            uint32_t shifter = 1<<31;  // make sure that shifter is unsigned.Otherwise shifting right will add ones to left
            
            for(int i = 0; i < 32; i++)
            {
                if(n & mask)  {  reverse |= (shifter>>i);  }
                mask <<= 1;
            }
            return reverse;
        }
    };
    

    This approach works fine but the loop has to run 32 times even if you don't have to. Say for , example your number in binary is 11011. You will have to still loop the loop 32 times even though you only require it to run 5 times.
    So what is a better approach ? Well, what if instead of shifting mask to the left each time, you shifted your original number to the right by one each time until your number becomes zero. Then your loop will have fewer loops. The solution looks like this:

    class Solution {
    public:
        uint32_t reverseBits(uint32_t n) {
    
            uint32_t reverse= 0;
            uint32_t shifter = 1<<31;
            
            //stops when n becomes zero
            for(int i = 0; n!= 0; i++)
            {
                if(n & 1) { reverse |=(shifter>>i); }
                n >>=1;
            }
            
            return reverse;
     }
    };
    

  • 0

    @pb1771 Cool answer!


Log in to reply
 

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