我很想知道如何将一个数字四舍五入到最接近的整数。例如,如果我有:
int a = 59 / 4;
如果以浮点数计算,则为 14.75;如何将结果存储为“a”中的 15?
我很想知道如何将一个数字四舍五入到最接近的整数。例如,如果我有:
int a = 59 / 4;
如果以浮点数计算,则为 14.75;如何将结果存储为“a”中的 15?
整数舍入的标准习惯用法是:
int a = (59 + (4 - 1)) / 4;
您将除数减一加到被除数上。
适用于除数和除数的任何符号的代码:
int divRoundClosest(const int n, const int d)
{
return ((n < 0) ^ (d < 0)) ? ((n - d/2)/d) : ((n + d/2)/d);
}
回应评论“为什么这实际上有效?”,我们可以把它分开。首先,观察这n/d
将是商,但它被截断为零,而不是四舍五入。如果在除法之前将分母的一半与分子相加,则会得到四舍五入的结果,但前提是分子和分母具有相同的符号。如果符号不同,除法前必须减去分母的一半。把所有这些放在一起:
(n < 0) is false (zero) if n is non-negative
(d < 0) is false (zero) if d is non-negative
((n < 0) ^ (d < 0)) is true if n and d have opposite signs
(n + d/2)/d is the rounded quotient when n and d have the same sign
(n - d/2)/d is the rounded quotient when n and d have opposite signs
如果您更喜欢宏:
#define DIV_ROUND_CLOSEST(n, d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d)))
Linux 内核宏 DIV_ROUND_CLOSEST 不适用于负除数!
编辑:这将不会溢出:
int divRoundClosest( int A, int B )
{
if(A<0)
if(B<0)
return (A + (-B+1)/2) / B + 1;
else
return (A + ( B+1)/2) / B - 1;
else
if(B<0)
return (A - (-B+1)/2) / B - 1;
else
return (A - ( B+1)/2) / B + 1;
}
int a = 59.0f / 4.0f + 0.5f;
这仅在分配给 int 时有效,因为它会丢弃 '.' 之后的任何内容。
编辑: 此解决方案仅适用于最简单的情况。一个更强大的解决方案是:
unsigned int round_closest(unsigned int dividend, unsigned int divisor)
{
return (dividend + (divisor / 2)) / divisor;
}
你应该改用这样的东西:
int a = (59 - 1)/ 4 + 1;
我假设您确实在尝试做一些更一般的事情:
int divide(x, y)
{
int a = (x -1)/y +1;
return a;
}
x + (y-1) 有可能溢出,给出不正确的结果;而 x - 1 只有在 x = min_int 时才会下溢...
(已编辑)用浮点数舍入整数是解决此问题的最简单方法;但是,根据问题集是可能的。例如,在嵌入式系统中,浮点解决方案可能过于昂贵。
使用整数数学来做这件事有点困难,而且有点不直观。第一个发布的解决方案对于我使用它的问题来说效果很好,但是在对整数范围内的结果进行表征之后,结果证明总的来说非常糟糕。翻阅几本关于位旋转和嵌入式数学的书,结果很少。一些笔记。首先,我只测试了正整数,我的工作不涉及负分子或分母。其次,对 32 位整数的详尽测试在计算上是令人望而却步的,因此我从 8 位整数开始,然后确保使用 16 位整数得到类似的结果。
我从之前提出的 2 个解决方案开始:
#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)
#define DIVIDE_WITH_ROUND(N, D) (N == 0) ? 0:(N - D/2)/D + 1;
我的想法是第一个版本会溢出大数字,而第二个版本会溢出小数字。我没有考虑两件事。1.)第二个问题实际上是递归的,因为要获得正确的答案,您必须正确舍入 D/2。2.)在第一种情况下,您经常上溢然后下溢,两者相互抵消。这是两个(不正确的)算法的错误图:
该图显示第一个算法仅对小分母 (0 < d < 10) 不正确。出乎意料的是,它实际上比第二版更好地处理大分子。
这是第二种算法的图:
正如预期的那样,它对于小分子会失败,但对于比第一版更多的大分子也会失败。
显然,这是正确版本的更好起点:
#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)
如果您的分母 > 10,那么这将正常工作。
D == 1 需要特殊情况,只需返回 N。D== 2 需要特殊情况,= N/2 + (N & 1) // 如果奇数则向上取整。
一旦 N 变得足够大,D >= 3 也会出现问题。事实证明,较大的分母只对较大的分子有问题。对于 8 位有符号数,问题点是
if (D == 3) && (N > 75))
else if ((D == 4) && (N > 100))
else if ((D == 5) && (N > 125))
else if ((D == 6) && (N > 150))
else if ((D == 7) && (N > 175))
else if ((D == 8) && (N > 200))
else if ((D == 9) && (N > 225))
else if ((D == 10) && (N > 250))
(为这些返回 D/N)
所以一般来说,特定分子变坏的点在某个地方
N > (MAX_INT - 5) * D/10
这并不准确,但很接近。当使用 16 位或更大的数字时,如果您只是对这些情况进行 C 除法(截断),则误差 < 1%。
对于 16 位有符号数字,测试将是
if ((D == 3) && (N >= 9829))
else if ((D == 4) && (N >= 13106))
else if ((D == 5) && (N >= 16382))
else if ((D == 6) && (N >= 19658))
else if ((D == 7) && (N >= 22935))
else if ((D == 8) && (N >= 26211))
else if ((D == 9) && (N >= 29487))
else if ((D == 10) && (N >= 32763))
当然,对于无符号整数,MAX_INT 将替换为 MAX_UINT。我确信有一个精确的公式可以确定适用于特定 D 和位数的最大 N,但我没有更多时间来解决这个问题......
(我现在好像漏掉了这张图,我稍后会编辑和添加。)这是带有上述特殊情况的 8 位版本的图表:![8 位签名,带有特殊情况0 < N <= 10
3
请注意,对于图表中的所有错误,对于 8 位,错误为 10% 或更少,16 位小于 0.1%。
如所写,您正在执行整数运算,它会自动截断任何小数结果。要执行浮点运算,请将常量更改为浮点值:
int a = round(59.0 / 4);
或者将它们转换为一个float
或其他浮点类型:
int a = round((float)59 / 4);
无论哪种方式,您都需要对标头中的round()
函数进行最后的舍入math.h
,因此请务必#include <math.h>
使用与 C99 兼容的编译器。
从 Linux 内核(GPLv2):
/*
* Divide positive or negative dividend by positive divisor and round
* to closest integer. Result is undefined for negative divisors and
* for negative dividends if the divisor variable type is unsigned.
*/
#define DIV_ROUND_CLOSEST(x, divisor)( \
{ \
typeof(x) __x = x; \
typeof(divisor) __d = divisor; \
(((typeof(x))-1) > 0 || \
((typeof(divisor))-1) > 0 || (__x) > 0) ? \
(((__x) + ((__d) / 2)) / (__d)) : \
(((__x) - ((__d) / 2)) / (__d)); \
} \
)
2021 年 5 月 2 日更新:
下面我原始答案中的代码仅适用于正整数。要处理负整数的正确舍入,请参阅我的项目 repo 中的技术:https ://github.com/ElectricRCAaircraftGuy/eRCaGuy_hello_world/tree/master/c/rounding_integer_division 。主文件:rounding_integer_division.cpp。
它包含:
DIVIDE_ROUNDUP(numer, denom)
DIVIDE_ROUNDDOWN(numer, denom)
DIVIDE_ROUNDNEAREST(numer, denom)
DIVIDE_ROUNDUP2(numer, denom)
DIVIDE_ROUNDDOWN2(numer, denom)
DIVIDE_ROUNDNEAREST2(numer, denom)
template <typename T>
T divide_roundup(T numer, T denom)
template <typename T>
T divide_rounddown(T numer, T denom)
template <typename T>
T divide_roundnearest(T numer, T denom)
原始答案:
// To do (numer/denom), rounded to the nearest whole integer, use:
#define ROUND_DIVIDE(numer, denom) (((numer) + (denom) / 2) / (denom))
使用示例:
int num = ROUND_DIVIDE(13,7); // 13/7 = 1.857 --> rounds to 2, so num is 2
其中一些答案看起来很疯狂!不过,Codeface 搞定了!(请参阅@0xC0DEFACE在此处的回答)。我真的很喜欢函数形式的无类型宏或 gcc 语句表达式形式,但是,所以,我写了这个答案,详细解释了我在做什么(即:为什么这在数学上有效)并将其放入 2 种形式:
/// @brief ROUND_DIVIDE(numerator/denominator): round to the nearest whole integer when doing
/// *integer* division only
/// @details This works on *integers only* since it assumes integer truncation will take place automatically
/// during the division!
/// @notes The concept is this: add 1/2 to any number to get it to round to the nearest whole integer
/// after integer trunction.
/// Examples: 2.74 + 0.5 = 3.24 --> 3 when truncated
/// 2.99 + 0.5 = 3.49 --> 3 when truncated
/// 2.50 + 0.5 = 3.00 --> 3 when truncated
/// 2.49 + 0.5 = 2.99 --> 2 when truncated
/// 2.00 + 0.5 = 2.50 --> 2 when truncated
/// 1.75 + 0.5 = 2.25 --> 2 when truncated
/// To add 1/2 in integer terms, you must do it *before* the division. This is achieved by
/// adding 1/2*denominator, which is (denominator/2), to the numerator before the division.
/// ie: `rounded_division = (numer + denom/2)/denom`.
/// ==Proof==: 1/2 is the same as (denom/2)/denom. Therefore, (numer/denom) + 1/2 becomes
/// (numer/denom) + (denom/2)/denom. They have a common denominator, so combine terms and you get:
/// (numer + denom/2)/denom, which is the answer above.
/// @param[in] numerator any integer type numerator; ex: uint8_t, uint16_t, uint32_t, int8_t, int16_t, int32_t, etc
/// @param[in] denominator any integer type denominator; ex: uint8_t, uint16_t, uint32_t, int8_t, int16_t, int32_t, etc
/// @return The result of the (numerator/denominator) division rounded to the nearest *whole integer*!
#define ROUND_DIVIDE(numerator, denominator) (((numerator) + (denominator) / 2) / (denominator))
在此处查看更多关于 gcc 语句表达式的信息。
/// @brief *gcc statement expression* form of the above macro
#define ROUND_DIVIDE2(numerator, denominator) \
({ \
__typeof__ (numerator) numerator_ = (numerator); \
__typeof__ (denominator) denominator_ = (denominator); \
numerator_ + (denominator_ / 2) / denominator_; \
})
(2020 年 3 月/4 月添加)
#include <limits>
// Template form for C++ (with type checking to ensure only integer types are passed in!)
template <typename T>
T round_division(T numerator, T denominator)
{
// Ensure only integer types are passed in, as this round division technique does NOT work on
// floating point types since it assumes integer truncation will take place automatically
// during the division!
// - The following static assert allows all integer types, including their various `const`,
// `volatile`, and `const volatile` variations, but prohibits any floating point type
// such as `float`, `double`, and `long double`.
// - Reference page: https://en.cppreference.com/w/cpp/types/numeric_limits/is_integer
static_assert(std::numeric_limits<T>::is_integer, "Only integer types are allowed");
return (numerator + denominator/2)/denominator;
}
BASE 2 CONCEPT:
获取更多详细信息!待办事项:测试这个是否有负面输入并更新这个答案,如果它有效:
#define ROUND_DIVIDE(numer, denom) ((numer < 0) != (denom < 0) ? ((numer) - (denom) / 2) / (denom) : ((numer) + (denom) / 2) / (denom))
#define CEIL(a, b) (((a) / (b)) + (((a) % (b)) > 0 ? 1 : 0))
另一个有用的宏(必须有):
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
#define ABS(a) (((a) < 0) ? -(a) : (a))
int a, b;
int c = a / b;
if(a % b) { c++; }
检查是否有余数允许您手动舍入整数除法的商。
借用@ericbn,我更喜欢定义为
#define DIV_ROUND_INT(n,d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d)))
or if you work only with unsigned ints
#define DIV_ROUND_UINT(n,d) ((((n) + (d)/2)/(d)))
这是我的解决方案。我喜欢它,因为我发现它更具可读性并且因为它没有分支(ifs 和三元组都没有)。
int32_t divide(int32_t a, int32_t b) {
int32_t resultIsNegative = ((a ^ b) & 0x80000000) >> 31;
int32_t sign = resultIsNegative*-2+1;
return (a + (b / 2 * sign)) / b;
}
说明预期行为的完整测试程序:
#include <stdint.h>
#include <assert.h>
int32_t divide(int32_t a, int32_t b) {
int32_t resultIsNegative = ((a ^ b) & 0x80000000) >> 31;
int32_t sign = resultIsNegative*-2+1;
return (a + (b / 2 * sign)) / b;
}
int main() {
assert(divide(0, 3) == 0);
assert(divide(1, 3) == 0);
assert(divide(5, 3) == 2);
assert(divide(-1, 3) == 0);
assert(divide(-5, 3) == -2);
assert(divide(1, -3) == 0);
assert(divide(5, -3) == -2);
assert(divide(-1, -3) == 0);
assert(divide(-5, -3) == 2);
}
int divide(x,y){
int quotient = x/y;
int remainder = x%y;
if(remainder==0)
return quotient;
int tempY = divide(y,2);
if(remainder>=tempY)
quotient++;
return quotient;
}
例如 59/4 商 = 14,tempY = 2,余数 = 3,余数 >= tempY 因此商 = 15;
对于没有浮点或条件分支的正负操作数,以下正确地将商四舍五入到最接近的整数(请参见下面的汇编输出)。假设 N 位 2 的补码整数。
#define ASR(x) ((x) < 0 ? -1 : 0) // Compiles into a (N-1)-bit arithmetic shift right
#define ROUNDING(x,y) ( (y)/2 - (ASR((x)^(y)) & (y)))
int RoundedQuotient(int x, int y)
{
return (x + ROUNDING(x,y)) / y ;
}
ROUNDING 的值将与被除数 (x) 具有相同的符号,并且是除数 (y)大小的一半。因此,在整数除法截断所得商之前,将 ROUNDING 添加到被除数会增加其大小。这是针对 32 位 ARM Cortex-M4 处理器进行 -O3 优化的 gcc 编译器的输出:
RoundedQuotient: // Input parameters: r0 = x, r1 = y
eor r2, r1, r0 // r2 = x^y
and r2, r1, r2, asr #31 // r2 = ASR(x^y) & y
add r3, r1, r1, lsr #31 // r3 = (y < 0) ? y + 1 : y
rsb r3, r2, r3, asr #1 // r3 = y/2 - (ASR(x^y) & y)
add r0, r0, r3 // r0 = x + (y/2 - (ASR(x^y) & y)
sdiv r0, r0, r1 // r0 = (x + ROUNDING(x,y)) / y
bx lr // Returns r0 = rounded quotient
对于某些算法,当“最近”是平局时,您需要一致的偏差。
// round-to-nearest with mid-value bias towards positive infinity
int div_nearest( int n, int d )
{
if (d<0) n*=-1, d*=-1;
return (abs(n)+((d-(n<0?1:0))>>1))/d * ((n<0)?-1:+1);
}
无论分子或分母的符号如何,这都有效。
如果要匹配round(N/(double)D)
(浮点除法和舍入)的结果,这里有一些变体,它们都产生相同的结果:
int div_nearest( int n, int d )
{
int r=(n<0?-1:+1)*(abs(d)>>1); // eliminates a division
// int r=((n<0)^(d<0)?-1:+1)*(d/2); // basically the same as @ericbn
// int r=(n*d<0?-1:+1)*(d/2); // small variation from @ericbn
return (n+r)/d;
}
注意:(abs(d)>>1)
vs . 的相对速度(d/2)
可能取决于平台。
如果要除正整数,可以将其向上移动,进行除法,然后检查实数 b0 右侧的位。换句话说,100/8 是 12.5,但会返回 12。如果您执行 (100<<1)/8,则可以检查 b0,然后在将结果向下移动后向上取整。
double a=59.0/4;
int b=59/4;
if(a-b>=0.5){
b++;
}
printf("%d",b);
除以 4 的一些替代方法
return x/4 + (x/2 % 2);
return x/4 + (x % 4 >= 2)
或者一般来说,除以 2 的任何幂
return x/y + x/(y/2) % 2; // or
return (x >> i) + ((x >> i - 1) & 1); // with y = 2^i
如果小数部分⩾ 0.5,即第一个数字⩾ base/2,则它通过四舍五入来工作。在二进制中,它相当于将第一个小数位添加到结果中
这种方法在带有标志寄存器的体系结构中具有优势,因为进位标志将包含被移出的最后一位。例如在 x86 上可以优化为
shr eax, i
adc eax, 0
它也很容易扩展以支持有符号整数。请注意,负数的表达式是
(x - 1)/y + ((x - 1)/(y/2) & 1)
我们可以使它适用于正值和负值
int t = x + (x >> 31);
return (t >> i) + ((t >> i - 1) & 1);
正如先前的贡献者所提出的,基本的舍入除法算法是在除法之前将分母的一半加到分子上。这在输入无符号时很简单,但在涉及有符号值时则不然。以下是一些通过 GCC 为 ARM (thumb-2) 生成最佳代码的解决方案。
签名/未签名
inline int DivIntByUintRnd(int n, uint d)
{
int sgn = n >> (sizeof(n)*8-1); // 0 or -1
return (n + (int)(((d / 2) ^ sgn) - sgn)) / (int)d;
}
第一个代码行通过整个字复制分子符号位,创建零(正)或 -1(负)。在第二行,该值(如果为负)用于使用 2 的补码否定取舍舍入项:补码和增量。以前的答案使用条件语句或乘法来实现这一点。
已签名/已签名
inline int DivIntRnd(int n, int d)
{
int rnd = d / 2;
return (n + ((n ^ d) < 0 ? -rnd : rnd)) / d;
}
我发现我用条件表达式得到了最短的代码,但前提是我通过计算舍入值 d/2 来帮助编译器。使用 2 的补码否定很接近:
inline int DivIntRnd(int n, int d)
{
int sgn = (n ^ d) >> (sizeof(n)*8-1); // 0 or -1
return (n + ((d ^ sgn) - sgn) / 2) / d;
}
2的幂除法
整数除法向零截断,而移位则向负无穷大截断。这使得舍入移位更简单,因为无论分子的符号如何,您总是添加舍入值。
inline int ShiftIntRnd(int n, int s) { return ((n >> (s - 1)) + 1) >> 1; }
inline uint ShiftUintRnd(uint n, int s) { return ((n >> (s - 1)) + 1) >> 1; }
表达式是相同的(根据类型生成不同的代码),因此宏或重载函数对两者都适用。
传统方法(舍入除法的工作方式)是将除数的一半相加,1 << (s-1)。相反,我们减一格,加一格,然后进行最后一班。这可以节省创建一个重要的值(即使是常量)和机器寄存器来放入它。
尝试使用进行四舍五入的数学 ceil 函数。数学赛尔!
我遇到了同样的困难。下面的代码应该适用于正整数。
我还没有编译它,但我在谷歌电子表格上测试了算法(我知道,wtf)并且它正在工作。
unsigned int integer_div_round_nearest(unsigned int numerator, unsigned int denominator)
{
unsigned int rem;
unsigned int floor;
unsigned int denom_div_2;
// check error cases
if(denominator == 0)
return 0;
if(denominator == 1)
return numerator;
// Compute integer division and remainder
floor = numerator/denominator;
rem = numerator%denominator;
// Get the rounded value of the denominator divided by two
denom_div_2 = denominator/2;
if(denominator%2)
denom_div_2++;
// If the remainder is bigger than half of the denominator, adjust value
if(rem >= denom_div_2)
return floor+1;
else
return floor;
}
更安全的 C 代码(除非您有其他处理 /0 的方法):
return (_divisor > 0) ? ((_dividend + (_divisor - 1)) / _divisor) : _dividend;
当然,这并不能处理由于输入数据无效而导致返回值不正确而导致的问题。