已知一个n-bits的整数N，已有的基本操作加法和移位求平方根

Binary numeral system (base 2)

 

 

Inherent to digit-by-digit algorithms is a search and test step: find a digit, , when added to the right of a current solution , such that , where is the value for which a root is desired. Expanding, we obtain . The current value of —or, usually, the remainder—can be incrementally updated efficiently when working in binary, as the value of will be a single bit, and the operations needed to compute and can be replaced with faster bit shift operations. This gives rise to simple computer implementations:

 short sqrt(short num) {
        short op = num;
        short res = 0;
        short one = 1 << 14; // The second-to-top bit is set: 1L<<30 for long

        // "one" starts at the highest power of four <= the argument.
        while (one > op)
            one >>= 2;

        while (one != 0) {
            if (op >= res + one) {
                op -= res + one;
                res = (res >> 1) + one;
            }
            else
              res >>= 1;
            one >>= 2;
        }
        return res;
    }