/*
**	The idea of the solution is to calculate each bit in the result, from high to low
**	Set the bit on, if the quare value is exceed the parameter, set bit off.
**
*/


int Sqrt(int x) 
{
	unsigned int k = x; //convert to unsigned type to prevent from overflow
    unsigned int add = (1 << ((sizeof(x)*8 - 1 ) / 2));//max bit would be in max square result
	
    int result = 0;
	//decide each bit
    while(add > 0)
    {
        result |= add;
        if (k < result*result)
            //remove the bit from result
            //result &= 0xFFFF ^ add;
			result -= add;

        add >>= 1;
    }
	
	return result;
}


#include <stdio.h>

int main(int argc, char** argv)
{
    printf("%d\n", Sqrt(4));
    printf("%d\n", Sqrt((1<<15)*(1<<15))); //32768
    return 0;
}