C:将有符号整数舍入到最接近的倍数
C: Round signed integer to nearest multiple
这感觉像是一个基本问题,但到目前为止我找不到明确的答案。
我想实现一个高效的函数 round_to_nearest(int x, int multiple)
,将有符号整数 x
舍入到最接近 multiple
的倍数,尽可能避免使用浮点运算。
示例输出:
round_to_nearest(14, 5);
15
round_to_nearest(16, 5);
15
round_to_nearest(23, 5);
25
round_to_nearest(22, 5);
20
round_to_nearest(-23, 5);
-25
round_to_nearest(-22, 5);
-20
对于正数:
- 将
multiple
的一半加到x
- 然后执行整数除法,去掉小数部分
- 然后乘以
multiple
得到最终答案
对于负数,第一步是减法,而不是加法。
int round_to_nearest(int x, int multiple)
{
if (x >= 0)
return ((x + multiple / 2) / multiple) * multiple;
else
return ((x - multiple / 2) / multiple) * multiple;
}
整数除法向零截断;这比四舍五入到最接近的结果小 0.5(平均幅度)。
如果分子的大小加上0.5 * divisor
的大小,那么结果会大0.5。
换句话说,对于无符号整数:
result = (numerator + divisor/2) / divisor;
.. 或者(除数为奇数时舍入误差较小,溢出风险较高 - 例如,如果分子为 INT_MAX
):
result = (numerator*2 + divisor) / (divisor * 2);
对于有符号整数,“量级”不是“值”;当分子和除数的符号不同时,它就会变得一团糟。要解决这个问题:
if( (numerator < 0) && (divisor < 0) ||
(numerator >= 0) && (divisor |= 0) ) {
/* Numerator and divisor have same sign */
result = (numerator*2 + divisor) / (divisor * 2);
} else {
/* Numerator and divisor have different sign */
result = (numerator*2 - divisor) / (divisor * 2);
}
要舍入到最接近的倍数,只需在“舍入到最近”后乘以除数即可。代码变为:
if( (numerator < 0) && (multiple < 0) ||
(numerator >= 0) && (multiple |= 0) ) {
/* Numerator and multiple have same sign */
result = (numerator*2 + multiple) / (multiple * 2);
} else {
/* Numerator and multiple have different sign */
result = (numerator*2 - multiple) / (multiple * 2);
}
result *= multiple;
在整数运算中,如果n为正数,则加m/2,否则减去m/2,然后除以m(截断整数除法),再乘以m:
int round_to_nearest( int n, int m )
{
return (( n + ((n < 0) ? -m : m) / 2) / m ) * m ;
}
int main()
{
int test[] = {16, 23, 22, -23, -22} ;
int m = 5 ;
for( int i = 0; i < sizeof(test) / sizeof(*test); i++ )
{
printf(" round_to_nearest( %d, %d ) = %d\n", test[i], m,
round_to_nearest( test[i], m ) ) ;
}
return 0;
}
测试输出:
round_to_nearest( 16, 5 ) = 15
round_to_nearest( 23, 5 ) = 25
round_to_nearest( 22, 5 ) = 20
round_to_nearest( -23, 5 ) = -25
round_to_nearest( -22, 5 ) = -20
一个警告是 m 必须 > 0 - 在这种情况下这是有道理的,我认为这是正确操作的先决条件;检查它作为运行时错误可能是不必要的,但您可以包含一个断言以防止程序员出现语义错误:
assert( m > 0 ) ;
标准库断言在定义 NDEBUG
时被删除 - 通常在禁用调试支持时。
为了向零方向舍入到下一个倍数(即正数向下舍入,负数向上舍入),您所要做的就是除以该倍数,然后将结果乘以该倍数.向零舍入将通过除法中的截断来完成。
int round_toward_zero( int num, int multiple )
{
int quotient;
quotient = num / multiple;
return quotient * multiple;
}
但是,既然你说你想四舍五入到最接近的倍数而不是零方向的下一个倍数,我们必须做同样的事情,但我们必须在我们想要的情况下添加一个小的修正向另一个方向舍入:
- 对于正数,如果除法的余数至少是倍数的一半,那么在乘以倍数之前,我们必须在商上加上
1
,使其远离零四舍五入。
- 对于负数,如果除法的余数不超过倍数的一半,我们必须在乘以倍数之前将商加上
-1
,以便它从零四舍五入。
因此,在下面的代码中,变量correction
的值可以是-1
、0
或+1
。对于正数,它将是 0
或 +1
,对于负数,它将是 -1
或 0
.
#include <stdio.h>
int round_to_nearest( int num, int multiple )
{
int quotient, remainder, correction;
quotient = num / multiple;
remainder = num % multiple;
correction = remainder / ( (multiple + 1 ) / 2 );
return (quotient + correction) * multiple;
}
int main( void )
{
printf( "%d\n", round_to_nearest(14, 5) );
printf( "%d\n", round_to_nearest(16, 5) );
printf( "%d\n", round_to_nearest(23, 5) );
printf( "%d\n", round_to_nearest(22, 5) );
printf( "%d\n", round_to_nearest(-23, 5) );
printf( "%d\n", round_to_nearest(-22, 5) );
}
输出:
15
15
25
20
-25
-20
这感觉像是一个基本问题,但到目前为止我找不到明确的答案。
我想实现一个高效的函数 round_to_nearest(int x, int multiple)
,将有符号整数 x
舍入到最接近 multiple
的倍数,尽可能避免使用浮点运算。
示例输出:
round_to_nearest(14, 5);
15
round_to_nearest(16, 5);
15
round_to_nearest(23, 5);
25
round_to_nearest(22, 5);
20
round_to_nearest(-23, 5);
-25
round_to_nearest(-22, 5);
-20
对于正数:
- 将
multiple
的一半加到x
- 然后执行整数除法,去掉小数部分
- 然后乘以
multiple
得到最终答案
对于负数,第一步是减法,而不是加法。
int round_to_nearest(int x, int multiple)
{
if (x >= 0)
return ((x + multiple / 2) / multiple) * multiple;
else
return ((x - multiple / 2) / multiple) * multiple;
}
整数除法向零截断;这比四舍五入到最接近的结果小 0.5(平均幅度)。
如果分子的大小加上0.5 * divisor
的大小,那么结果会大0.5。
换句话说,对于无符号整数:
result = (numerator + divisor/2) / divisor;
.. 或者(除数为奇数时舍入误差较小,溢出风险较高 - 例如,如果分子为 INT_MAX
):
result = (numerator*2 + divisor) / (divisor * 2);
对于有符号整数,“量级”不是“值”;当分子和除数的符号不同时,它就会变得一团糟。要解决这个问题:
if( (numerator < 0) && (divisor < 0) ||
(numerator >= 0) && (divisor |= 0) ) {
/* Numerator and divisor have same sign */
result = (numerator*2 + divisor) / (divisor * 2);
} else {
/* Numerator and divisor have different sign */
result = (numerator*2 - divisor) / (divisor * 2);
}
要舍入到最接近的倍数,只需在“舍入到最近”后乘以除数即可。代码变为:
if( (numerator < 0) && (multiple < 0) ||
(numerator >= 0) && (multiple |= 0) ) {
/* Numerator and multiple have same sign */
result = (numerator*2 + multiple) / (multiple * 2);
} else {
/* Numerator and multiple have different sign */
result = (numerator*2 - multiple) / (multiple * 2);
}
result *= multiple;
在整数运算中,如果n为正数,则加m/2,否则减去m/2,然后除以m(截断整数除法),再乘以m:
int round_to_nearest( int n, int m )
{
return (( n + ((n < 0) ? -m : m) / 2) / m ) * m ;
}
int main()
{
int test[] = {16, 23, 22, -23, -22} ;
int m = 5 ;
for( int i = 0; i < sizeof(test) / sizeof(*test); i++ )
{
printf(" round_to_nearest( %d, %d ) = %d\n", test[i], m,
round_to_nearest( test[i], m ) ) ;
}
return 0;
}
测试输出:
round_to_nearest( 16, 5 ) = 15
round_to_nearest( 23, 5 ) = 25
round_to_nearest( 22, 5 ) = 20
round_to_nearest( -23, 5 ) = -25
round_to_nearest( -22, 5 ) = -20
一个警告是 m 必须 > 0 - 在这种情况下这是有道理的,我认为这是正确操作的先决条件;检查它作为运行时错误可能是不必要的,但您可以包含一个断言以防止程序员出现语义错误:
assert( m > 0 ) ;
标准库断言在定义 NDEBUG
时被删除 - 通常在禁用调试支持时。
为了向零方向舍入到下一个倍数(即正数向下舍入,负数向上舍入),您所要做的就是除以该倍数,然后将结果乘以该倍数.向零舍入将通过除法中的截断来完成。
int round_toward_zero( int num, int multiple )
{
int quotient;
quotient = num / multiple;
return quotient * multiple;
}
但是,既然你说你想四舍五入到最接近的倍数而不是零方向的下一个倍数,我们必须做同样的事情,但我们必须在我们想要的情况下添加一个小的修正向另一个方向舍入:
- 对于正数,如果除法的余数至少是倍数的一半,那么在乘以倍数之前,我们必须在商上加上
1
,使其远离零四舍五入。 - 对于负数,如果除法的余数不超过倍数的一半,我们必须在乘以倍数之前将商加上
-1
,以便它从零四舍五入。
因此,在下面的代码中,变量correction
的值可以是-1
、0
或+1
。对于正数,它将是 0
或 +1
,对于负数,它将是 -1
或 0
.
#include <stdio.h>
int round_to_nearest( int num, int multiple )
{
int quotient, remainder, correction;
quotient = num / multiple;
remainder = num % multiple;
correction = remainder / ( (multiple + 1 ) / 2 );
return (quotient + correction) * multiple;
}
int main( void )
{
printf( "%d\n", round_to_nearest(14, 5) );
printf( "%d\n", round_to_nearest(16, 5) );
printf( "%d\n", round_to_nearest(23, 5) );
printf( "%d\n", round_to_nearest(22, 5) );
printf( "%d\n", round_to_nearest(-23, 5) );
printf( "%d\n", round_to_nearest(-22, 5) );
}
输出:
15
15
25
20
-25
-20