Using bit shifting instead of division gives me "Time Limit Exceeded", wondering why?


  • 0
    I

    If I use bit shifting like this:

    mid = low + (high - low) >> 1;
    

    I'd get a "Time Limit Exceeded" message, but it's fine just using division:

    mid = low + (high - low) / 2;
    

    Wondering what's the problem here?
    Thanks!


  • 0
    L

    The issue is operator precendence:

    • Division is done before addition
    • Shifting is done after addition

    low + (high - low) >> 1 is equivalent to (low + (high - low)) >> 1.
    Using mid = low + ((high - low) >> 1) should fix it.


  • 0
    I

    @LinusVanElswijk Oh, I see. Thanks very much for your answer!


Log in to reply
 

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