Share my O(log n) Solution using bit manipulation


  • 72
    Y

    Basic Idea:


    Since sqrt(x) is composed of binary bits, I calculate sqrt(x) by deciding every bit from the most significant to least significant. Since an integer n can have O(log n) bits with each bit decided within constant time, this algorithm has time limit O(log n), actually, because an Integer can have at most 32 bits, I can also say this algorithm takes O(32)=O(1) time.


     public int sqrt(int x) {
        if(x==0)
            return 0;
        int h=0;
        while((long)(1<<h)*(long)(1<<h)<=x) // firstly, find the most significant bit
            h++;
        h--;
        int b=h-1;
        int res=(1<<h);
        while(b>=0){  // find the remaining bits
            if((long)(res | (1<<b))*(long)(res |(1<<b))<=x)
                res|=(1<<b);
            b--;
        }
        return res;
    }

  • 0
    S
    This post is deleted!

  • 0
    Y

    I decrease h after the first while loop is because: after the while loop terminates, h is the smallest number that can make (1<<h)*(1<<h)>x, so the highest bit of sqrt(x) should be at h-1. Check a base case. if x=5, when while loop terminates, h=2. so the highest bit of sqrt(5) is (1<<h-1)=(10).


  • 93
    T

    Very brilliant! But can be improved a little bit in coding:

    public int sqrt(int x) {
        long ans = 0;
        long bit = 1l << 16;
        while(bit > 0) {
            ans |= bit;
            if (ans * ans > x) {
                ans ^= bit;
            }
            bit >>= 1;
        }
        return (int)ans;
    }

  • 0
    K

    Yeah, much nicer than mine, use XOR can test the lower bit while preserve the higher calculated bits.


  • 0
    L

    Brilliant! But I think most binary search based algorithms also takes O(32) for the worst case since Integer (in Java) is 32-bits.


  • 0
    3

    awesome, but when i tried your solution, it got Time Limit Exceeded.


  • 0
    M

    I can only pass if I use long long instead of long.


  • 0
    H

    you can break before bit equals 0.
    if (ans * ans > x) {
    ans ^= bit;
    }
    else if (ans * ans == x)
    break;


  • 0
    D

    A small bug, long should be unsigned long, and bit = 1l << 15.


  • 11
    P

    As x is int, the maximum of x is 2^31-1, sqrt(x)'s most significant bit is at most 2^15. But (2^15 + 2^14)^2 exceeds int, not unsigned int, so I use unsigned int to represent sqrt(x) as res, so res * res will never overflow. Here is my code

    int sqrt(int x) {
        unsigned int res = 0;
        for (int i = 15; i >= 0; i--)
        {
            if ((res + (1 << i)) * (res + (1 << i)) <= x)
                res += (1 << i);
        }
        return res;
    }

  • 0
    T

    Forgot to metion my code was in java. long in java is 64-bit integer.


  • 0
    L

    Why sqrt(x) 's is at most 15 bits? For example, 2^30 makes sqrt(x) 2^15, which requires 16 bits to represent.


  • 0
    P

    What I meant is sqrt(x)'s most significant bit is at most 2^15. Also, you mentioned "2^30 makes sqrt(x) 2^15", this is true. But (2^15 + 2^14 + 2^13 + ... + 2^0)^2 is actually a negtive number (11111111111111100000000000000001) as highest bit is 1. That means MAX_INT could be represented with a number N, where N's most significant bit is 2^15.


  • 0
    P

    I have change my answer to avoid confusion.


  • 0
    M

    me too, but it works on my laptop.


  • 0
    A

    Pretty COOOOOOOOOOL!!!!


  • 0
    Y

    there may be overflow while you are using (long)m * (long)m <= x.......long may be 4 bytes in some laptops(usually in 32-bit) and maybe 8 bytes in others (usually in 64-bit)


  • 0
    H

    1l easily be missed with 11, maybe, 1L will be better. Nice solution. Thx


  • 0

    all the answer ,yours is the earsiest to understand,and I have a conside:
    (1<<h)<=x/(1<<h) to replace ((long)(l<<h)*(long)(l<<h)<=x).
    what do you think??


Log in to reply
 

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