# Share my O(log n) Solution using bit manipulation

• ## 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;
}``````

• This post is deleted!

• 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).

• 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;
}``````

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

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

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

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

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

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

• 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;
}``````

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

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

• 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.

• I have change my answer to avoid confusion.

• me too, but it works on my laptop.

• Pretty COOOOOOOOOOL!!!!

• 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)

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

• 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??

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