Finding the square root of a given number using bitwise operations

Question

Is there an algorithm to find the square root of a given number using bitwise operations?

Answer 1

There is this famous piece of code magic that computes inverse square root with a some very clever bit twiddling. It is wrongfully attributed to John Carmack - here's a deeper dig into its origin. Maybe that's what you're asking about?

I wouldn't suggest using it, though. On modern CPU's it cannot beat dedicated transcendental instructions. Your usual c++ intrinsic sqrt() would probably beat it hands down.

[Edit:] The cited article describes a general derivation method for such fast approximations, and explicitly states 'Derive a similar method for sqrt(x)' as a homework problem at its final lines. So you should be able to track its reasoning and devise a similar method for sqrt (without the reciprocal) directly.

Answer 2

Wikipedia has an article about and a code too. And another wikipedia article shows an algorithm (even for roots greater than 2) that can be easily implemented in binary (so, involving operation on bits).

If you want to stick only to real bitwise operators, you have to implement + using Ands, Ors, Xors, Nots... If you want to do it on floats according to IEEE, you need more work (the first code in wikipedia could be used on the mantissa "directly", likely under certain restriction, and adjust exponent "accordingly"... you have to figure out how, however!)