o****e
发帖数: 80 | 1 Given a positive integer, return the integer part of its square root.
Requirements: cannot use any math
functions; can only use integer variables, no double variables even for
intermediate variables; as efficient as
possible. |
l******l
发帖数: 497 | 2 binary search between (0,n/2) |
c**********e
发帖数: 2007 | 3
no use of +-*/?
【在 o****e 的大作中提到】
: Given a positive integer, return the integer part of its square root.
: Requirements: cannot use any math
: functions; can only use integer variables, no double variables even for
: intermediate variables; as efficient as
: possible.
|
f******y
发帖数: 2971 | 4 Come on, this is NOT a C++ question. |
J*******g
发帖数: 267 | 5 Newton-Raphson method?
【在 o****e 的大作中提到】
: Given a positive integer, return the integer part of its square root.
: Requirements: cannot use any math
: functions; can only use integer variables, no double variables even for
: intermediate variables; as efficient as
: possible.
|
j******n
发帖数: 271 | 6 1. Use shift to find out the position of highest bit, M.
2. Do binary search in the range:
[ 2^(M/2) , 2^((M+1)/2) ) |
