개요
어떤 정수 A를 다른 정수 B로 나누고, 그것을 올림하는데, ceil이나 mod 연산 없이 정수 연산만으로 구할 수 있는 방법이 있어 정리하고자 한다. 방법은 간단하다! A에 B-1만 더해주면 된다.
(A + (B-1)) / B
증명
원리는 간단하다. A / B = C로 나누어 떨어진다고 하면, (A+B) / B는 C+1이 된다. 그럼 (A+1), (A+2), ..., (A+B-1)은 정수의 내림 연산에 의해 C이다. 즉, A가 B로 나누어 떨어지는 상황에서 (A+B-1)/B는 정상적으로 C가 된다.
이번에는 A/B = C이 나누어 떨어지지 않는 상황을 생각해보자. 이 경우 우리는 올림을 해줘야 하는데, A에 A%B를 통해 구한 나머지보다 큰 수를 더해야지만 C+1을 구할 수 있다.그런데, A%B <= B-1 이므로 (A+B-1)/B는 상항 C+1로 올림이 된다.