C / C ++에서 정수 나누기의 빠른 상한 ceil(10/5)=2와 ceil(11/5)=3. 확실한 접근

정수 값 xyC 및 C ++는 모두 q = x/y부동 소수점의 바닥을 몫으로 반환 합니다. 천장을 반환하는 방법에 관심이 있습니다. 예를 들어, ceil(10/5)=2ceil(11/5)=3.

확실한 접근 방식은 다음과 같습니다.

q = x / y;
if (q * y < x) ++q;

이를 위해서는 추가 비교와 곱셈이 필요합니다. 그리고 내가 본 (실제로 사용 된) 다른 방법은 float또는 로 캐스팅하는 것과 관련이 있습니다 double. 추가 곱셈 (또는 두 번째 나눗셈)과 분기를 피하고 부동 소수점 숫자로 캐스팅을 피하는보다 직접적인 방법이 있습니까?



답변

양수

unsigned int x, y, q;

반올림하려면 …

q = (x + y - 1) / y;

또는 (x + y에서 오버플로 방지)

q = 1 + ((x - 1) / y); // if x != 0

답변

양수의 경우 :

    q = x/y + (x % y != 0);

답변

Sparky의 대답은이 문제를 해결하는 하나의 표준 방법이지만 내 의견에 썼 듯이 오버플로의 위험이 있습니다. 더 넓은 유형을 사용하면이 문제를 해결할 수 있지만 long longs 를 나누려면 어떻게해야 합니까?

Nathan Ernst의 답변은 하나의 솔루션을 제공하지만 함수 호출, 변수 선언 및 조건부와 관련이 있습니다. 이는 OPs 코드보다 짧지 않으며 최적화하기가 더 어려워 아마도 느릴 수 있습니다.

내 해결책은 이것입니다 :

q = (x % y) ? x / y + 1 : x / y;

모듈로와 나누기는 프로세서에서 동일한 명령을 사용하여 수행되기 때문에 OPs 코드보다 약간 빠릅니다. 컴파일러는 이들이 동등한 것을 알 수 있기 때문입니다. 적어도 gcc 4.4.1은 x86에서 -O2 플래그를 사용하여이 최적화를 수행합니다.

이론적으로 컴파일러는 Nathan Ernst의 코드에서 함수 호출을 인라인하고 동일한 것을 방출 할 수 있지만 gcc는 테스트 할 때 그렇게하지 않았습니다. 컴파일 된 코드를 단일 버전의 표준 라이브러리에 연결하기 때문일 수 있습니다.

마지막으로, 매우 엄격한 루프 상태에 있고 모든 데이터가 레지스터 또는 L1 캐시에있는 경우를 제외하고는 최신 머신에서는이 문제가 중요하지 않습니다. 그렇지 않으면 Nathan Ernst를 제외하고 이러한 모든 솔루션이 똑같이 빠를 것입니다.이 기능은 주 메모리에서 함수를 가져와야하는 경우 상당히 느려질 수 있습니다.


답변

divcstdlib 의 함수를 사용하여 한 번의 호출로 몫 및 나머지를 얻은 다음 아래에서와 같이 천장을 개별적으로 처리 할 수 ​​있습니다

#include <cstdlib>
#include <iostream>

int div_ceil(int numerator, int denominator)
{
        std::div_t res = std::div(numerator, denominator);
        return res.rem ? (res.quot + 1) : res.quot;
}

int main(int, const char**)
{
        std::cout << "10 / 5 = " << div_ceil(10, 5) << std::endl;
        std::cout << "11 / 5 = " << div_ceil(11, 5) << std::endl;

        return 0;
}

답변

이건 어때요? (y가 음수가 아닌 것을 요구하므로 y가 음이 아닌 보증이없는 변수 인 드문 경우에는 사용하지 마십시오)

q = (x > 0)? 1 + (x - 1)/y: (x / y);

나는 1로 줄었고 y/y용어를 없애고 x + y - 1넘칠 가능성이있었습니다.

부호없는 유형이고 0을 포함 x - 1할 때 감싸는 것을 피 x합니다.

signed의 경우 x, 음수와 0은 여전히 ​​단일 사례로 결합됩니다.

아마도 현대의 범용 CPU에 큰 이점은 아니지만 임베디드 시스템에서는 다른 정답보다 훨씬 빠릅니다.


답변

긍정과 부정 모두에 대한 솔루션이 x있지만 y분기가 하나만 있고 분기가없는 긍정에 대한 솔루션이 있습니다 .

int ceil(int x, int y) {
    return x / y + (x % y > 0);
}

참고 경우 x입니다 긍정적 인 다음 부문은 0에 가까워, 그리고 알림이 0이 아닌 경우, 우리는 하나를 추가해야합니다.

경우 x부정적인는 다음 부문은 우리가 필요로 무엇을, 0에 가까워이며, 때문에 우리는 아무것도 추가하지 않습니다 x % y긍정적 아니다


답변

양수 또는 음수에 적용됩니다.

q = x / y + ((x % y != 0) ? !((x > 0) ^ (y > 0)) : 0);

나머지가있는 경우, 검사가 있는지 xy같은 부호이며, 추가 1따라.