a**********2 发帖数: 340 | 1 求int sqrt(int x)越界如何处理啊?
看到以前的一个帖子,觉得好像不太对, INT_MAX是2^31-1不是2^32,用(1<<16)还是
会越界,请问下该如何处理?
还有判断越界一般用什么方法?多谢了 | a**********2 发帖数: 340 | | i**********e 发帖数: 1145 | 3 Good observation.
You are correct, my previous post has bugs and did not address the overflow
issue properly.
Two methods to address:
i) find the upper bound of SQRT(INT_MAX) once and pass it into that function
. The upper bound can be found using a helper function that tests for
overflow. (ie, as soon as the condition when x > x*x is met, we knew x-1 is
the upper bound).
ii) declare the parameter x as unsigned int. Then initialize the upper bound
,
hi = min(n/2, (1<<16) - 1);
Hope this helps.
【在 a**********2 的大作中提到】 : 求int sqrt(int x)越界如何处理啊? : : 看到以前的一个帖子,觉得好像不太对, INT_MAX是2^31-1不是2^32,用(1<<16)还是 : 会越界,请问下该如何处理? : 还有判断越界一般用什么方法?多谢了
| i**********e 发帖数: 1145 | 4 This should also work too :)
The observation is when it overflows, it must be the case M > M*M, so
readjust the upper bound to M-1 when that happens.
int mysqrt(int n) {
int L = 0;
int H = min(n/2, (1<<16));
while (L < H) {
int M = L+(H-L+1)/2;
int M_sqr = M*M;
if (M <= M_sqr && M_sqr <= n)
L = M;
else /* M > M_sqr || (M_sqr > n) */
H = M-1;
}
return L;
} | k*j 发帖数: 153 | 5 or just test if M*M<0, if so then it overflows.
【在 i**********e 的大作中提到】 : This should also work too :) : The observation is when it overflows, it must be the case M > M*M, so : readjust the upper bound to M-1 when that happens. : int mysqrt(int n) { : int L = 0; : int H = min(n/2, (1<<16)); : while (L < H) { : int M = L+(H-L+1)/2; : int M_sqr = M*M; : if (M <= M_sqr && M_sqr <= n)
| l*********8 发帖数: 4642 | 6 这个不能保证吧。
【在 k*j 的大作中提到】 : or just test if M*M<0, if so then it overflows.
|
|