My C solution,4ms ,O(log n), use bit-manipulation


  • 0
    A
    int mySqrt(int x) {
    	unsigned short root=0,i=0;
    	unsigned int rem=0,divisor=0,uX=x;
    	// fast log2(n)
    	double fX=uX;
    	static const size_t _n = 2 - ( sizeof( size_t ) >> 2 );
    	static const size_t _r = ( 20 + ( ( sizeof( size_t ) >> 3 ) << 5 ) );
    	int lg2_n = ( ( (size_t*)&fX )[_n] >> _r ) - 1023;
    
    	uX<<=(15-(lg2_n>>1))<<1;
    	i=(lg2_n>>1)+2;
    	while(--i) {
    		root<<=1;
    		rem=((rem<<2)|uX>>30);
    		uX<<=2;
    		divisor=root<<1|1;
    		if(divisor<=rem) {
    			rem-=divisor;
    			++root;
    		}
    	}
    	return (int)root;
    }

Log in to reply
 

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