반올림 정수 나누기 (잘라 내기 대신)

반올림 정수 나누기 (잘라 내기 대신)

---

숫자를 가장 가까운 정수로 반올림하는 방법을 알고 싶었습니다. 예를 들어 다음과 같은 경우 :

int a = 59 / 4;

부동 소수점으로 계산하면 14.75가됩니다. 결과를 "a"에 15로 저장하려면 어떻게해야합니까?

---

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 + (4 - 1)) / 4;

제수 마이너스 1을 피제수에 더합니다.

---

모든 사인 인 배당 및 제수에 대해 작동하는 코드 :

int divRoundClosest(const int n, const int d)
{
  return ((n < 0) ^ (d < 0)) ? ((n - d/2)/d) : ((n + d/2)/d);
}

매크로를 선호하는 경우 :

#define DIV_ROUND_CLOSEST(n, d) ((((n) < 0) ^ ((d) < 0)) ? (((n) - (d)/2)/(d)) : (((n) + (d)/2)/(d)))

Linux 커널 매크로 DIV_ROUND_CLOSEST는 음수 제수에 대해 작동하지 않습니다!

---

대신 다음과 같이 사용해야합니다.

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 비트 정수로 비슷한 결과를 얻었는지 확인했습니다.

이전에 제안한 두 가지 솔루션으로 시작했습니다.

#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)에는 특별한 경우가 필요합니다. // 홀수이면 올림합니다.

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 비트 버전의 그래프이다 (. 내가 나중에 편집하고 추가 할 순간이 그래프를 누락하는 것) : 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));    \
}                           \
)

---

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

나머지가 있는지 확인하면 정수 나누기의 몫을 수동으로 반올림 할 수 있습니다.

---

#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))

---

여기 내 해결책이 있습니다. 나는 더 읽기 쉽고 분기가 없기 때문에 좋아합니다 (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);
}

---

@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)))

---

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;

---

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이 해결책입니다.

---

try using math ceil function that makes rounding up. Math Ceil !

---

If you're dividing positive integers you can shift it up, do the division and then check the bit to the right of the real b0. In other words, 100/8 is 12.5 but would return 12. If you do (100<<1)/8, you can check b0 and then round up after you shift the result back down.

---

For some algorithms you need a consistent bias when 'nearest' is a tie.

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

This works regardless of the sign of the numerator or denominator.

---

If you want to match the results of round(N/(double)D) (floating-point division and rounding), here are a few variations that all produce the same results:

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

Note: The relative speed of (abs(d)>>1) vs. (d/2) is likely to be platform dependent.

---

The following correctly rounds the quotient to the nearest integer for both positive and negative operands WITHOUT floating point or conditional branches (see assembly output below). Assumes N-bit 2's complement integers.

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

The value of ROUNDING will have the same sign as the dividend (x) and half the magnitude of the divisor (y). Adding ROUNDING to the dividend thus increases its magnitude before the integer division truncates the resulting quotient. Here's the output of the gcc compiler with -O3 optimization for a 32-bit ARM Cortex-M4 processor:

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

---

Some alternatives for division by 4

return x/4 + (x/2 % 2);
return x/4 + (x % 4 >= 2)

Or in general, division by any power of 2

return x/y + x/(y/2) % 2;    // or
return (x >> i) + ((x >> i - 1) & 1);  // with y = 2^i

It works by rounding up if the fractional part ⩾ 0.5, i.e. the first digit ⩾ base/2. In binary it's equivalent to adding the first fractional bit to the result

This method has an advantage in architectures with a flag register, because the carry flag will contain the last bit that was shifted out. For example on x86 it can be optimized into

shr eax, i
adc eax, 0

It's also easily extended to support signed integers. Notice that the expression for negative numbers is

(x - 1)/y + ((x - 1)/(y/2) & 1)

we can make it work for both positive and negative values with

int t = x + (x >> 31);
return (t >> i) + ((t >> i - 1) & 1);

---

I ran into the same difficulty. The code below should work for positive integers.

I haven't compiled it yet but I tested the algorithm on a google spreadsheet (I know, wtf) and it was working.

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

---

Safer C code (unless you have other methods of handling /0):

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

This doesn't handle the problems that occur from having an incorrect return value as a result of your invalid input data, of course.

참고 URL : https://stackoverflow.com/questions/2422712/rounding-integer-division-instead-of-truncating