c - 整数除算の丸め (切り捨てではなく)

Question

数値を最も近い整数に丸める方法を知りたいと思っていました。たとえば、私が持っていた場合：

int a = 59 / 4;

浮動小数点で計算すると 14.75 になります。結果を "a" に 15 として格納するにはどうすればよいですか?

Answer 1

整数の切り上げの標準的な慣用句は次のとおりです。

int a = (59 + (4 - 1)) / 4;

除数から 1 を引いた値を被除数に追加します。

Answer 2

被除数と除数の任意の符号に対して機能するコード:

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;
}

Answer 3

int a = 59.0f / 4.0f + 0.5f;

これは、「。」の後のものを破棄するため、int に代入する場合にのみ機能します。

編集: このソリューションは、最も単純なケースでのみ機能します。より堅牢なソリューションは次のとおりです。

unsigned int round_closest(unsigned int dividend, unsigned int divisor)
{
    return (dividend + (divisor / 2)) / divisor;
}

Answer 4

代わりに、次のようなものを使用する必要があります。

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 の場合にのみアンダーフローします...

Answer 5

(編集済み) 整数を浮動小数点で丸めることが、この問題の最も簡単な解決策です。ただし、問題セットによっては可能な場合があります。たとえば、組み込みシステムでは、浮動小数点ソリューションはコストがかかりすぎる場合があります。

整数演算を使用してこれを行うのは、やや難しく、少し直感的ではありません。最初に投稿された解決策は、私が使用した問題に対しては問題なく機能しましたが、整数の範囲で結果を特徴付けた後、一般的に非常に悪いことが判明しました。ビットいじりと組み込み演算に関するいくつかの本を調べても、ほとんど結果が返されません。いくつかのメモ。まず、正の整数のみをテストしました。私の作業には負の分子または分母は含まれていません。第 2 に、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;

私の考えでは、最初のバージョンは大きな数でオーバーフローし、2 番目のバージョンは小さな数でアンダーフローするだろうというものでした。私は2つのことを考慮しませんでした。1.) 正しい答えを得るには D/2 を適切に丸める必要があるため、2 番目の問題は実際には再帰的です。2.) 最初のケースでは、オーバーフローしてからアンダーフローすることが多く、この 2 つが相殺されます。以下は、2 つの (正しくない) アルゴリズムのエラー プロットです。

このプロットは、最初のアルゴリズムが小さい分母 (0 < d < 10) に対してのみ正しくないことを示しています。意外なことに、実際には 2 番目のバージョンよりも大きな分子をより適切に処理します。

以下は、2 番目のアルゴリズムのプロットです。

予想どおり、小さな分子では失敗しますが、最初のバージョンよりも大きな分子でも失敗します。

明らかに、これは正しいバージョンのより良い出発点です:

#define DIVIDE_WITH_ROUND(N, D) (((N) == 0) ? 0:(((N * 10)/D) + 5)/10)

分母が 10 より大きい場合、これは正しく機能します。

D == 1 には特別なケースが必要です。単純に N を返します。D== 2 には特別なケースが必要です。 = N/2 + (N & 1) // 奇数の場合は切り上げます。

D >= 3 も、N が十分に大きくなると問題があります。分母が大きいほど、分子が大きい場合にのみ問題が発生することがわかります。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 ビット バージョンのグラフです:![ 0 < N <= 10 3の特殊なケースで署名された 8 ビット

8 ビットの場合、グラフ内のすべてのエラーでエラーが 10% 以下であることに注意してください。16 ビットでは < 0.1% です。

Answer 6

書かれているように、整数演算を実行しているため、小数の結果が自動的に切り捨てられます。浮動小数点演算を実行するには、定数を浮動小数点値に変更します。

int a = round(59.0 / 4);

floatまたは、または他の浮動小数点型にキャストします。

int a = round((float)59 / 4);

いずれにせよ、ヘッダー内のround()関数で最終的な丸めを行う必要があるため、必ずC99 互換コンパイラを使用してください。math.h#include <math.h>

Answer 7

int a, b;
int c = a / b;
if(a % b) { c++; }

剰余があるかどうかを確認すると、整数除算の商を手動で切り上げることができます。

Answer 8

#define CEIL(a, b) (((a) / (b)) + (((a) % (b)) > 0 ? 1 : 0))

別の便利なマクロ (MUST HAVE):

#define MIN(a, b)  (((a) < (b)) ? (a) : (b))
#define MAX(a, b)  (((a) > (b)) ? (a) : (b))
#define ABS(a)     (((a) < 0) ? -(a) : (a))

Answer 9

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;

Answer 10

正の整数を除算する場合は、上にシフトして除算を行い、実際の b0 の右側のビットを確認します。つまり、100/8 は 12.5 ですが、12 を返します。(100<<1)/8 を実行すると、b0 をチェックして、結果を下にシフトした後で切り上げることができます。

Answer 11

一部のアルゴリズムでは、「最も近い」が同点の場合、一貫したバイアスが必要です。

// 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)プラットフォームに依存する可能性があります。

Answer 12

double a=59.0/4;
int b=59/4;
if(a-b>=0.5){
    b++;
}
printf("%d",b);

1. 59.0/4 の正確な float 値を x (ここでは 14.750000) とします。
2. x より小さい最小の整数を y とする (ここでは 14)
3. xy<0.5 の場合、y が解になります。
4. それ以外の場合は y+1 が解です

Answer 13

切り上げを行う math ceil 関数を使用してみてください。数学セイル！

Answer 14

より安全な C コード (/0 を処理する他の方法がない場合):

return (_divisor > 0) ? ((_dividend + (_divisor - 1)) / _divisor) : _dividend;

もちろん、これは、無効な入力データの結果として誤った戻り値を持つことから発生する問題を処理しません。