Как я могу гарантировать, что деление целых чисел всегда округляется?

Question

Я хочу убедиться, что деление целых чисел всегда округляется при необходимости. Есть ли лучший способ, чем этот? Происходит много кастингов. : -)

(int)Math.Ceiling((double)myInt1 / myInt2)

Answer 1

ОБНОВЛЕНИЕ: Этот вопрос был темой моего блога в январе 2013 года . Спасибо за отличный вопрос!

---

Получить правильную целочисленную арифметику сложно. Как было продемонстрировано до сих пор, в тот момент, когда вы пытаетесь сделать «умный» трюк, велика вероятность, что вы допустили ошибку. И когда обнаружен недостаток, изменение кода для исправления недостатка без учета того, что исправление нарушает что-то еще , не является хорошим методом решения проблем. До сих пор у нас было пять различных неправильных целочисленных арифметических решений этой совершенно не особо сложной проблемы.

Правильный способ решения целочисленных арифметических задач, то есть способ повышения вероятности получения правильного ответа в первый раз, - это тщательно подходить к проблеме, решать ее по одному шагу за раз и использовать хороший инжиниринг. принципы в этом.

Начните с прочтения спецификации того, что вы пытаетесь заменить. Спецификация для целочисленного деления четко гласит:

1. Деление округляет результат до нуля

2. Результат равен нулю или положителен, если два операнда имеют одинаковый знак, и равен нулю или отрицанию, когда два операнда имеют противоположные знаки

3. Если левый операнд является наименьшим представимым int, а правый операнд равен –1, происходит переполнение. [...] это определяется реализацией относительно того, выбрасывается ли [ArithmeticException] или переполнение не сообщается, а результирующее значение равно левому операнду.

4. Если значение правого операнда равно нулю, выдается исключение System.DivideByZeroEx.

Нам нужна целочисленная функция деления, которая вычисляет частное, но округляет результат всегда вверх , а не всегда в направлении нуля .

Итак, напишите спецификацию для этой функции. Наша функция int DivRoundUp(int dividend, int divisor) должна иметь поведение, определенное для каждого возможного входа. Это неопределенное поведение вызывает глубокую тревогу, поэтому давайте устраним его. Мы скажем, что наша операция имеет эту спецификацию:

1. Операция генерируется, если делитель равен нулю

2. Операция генерируется, если делимое равно int.minval, а делитель равен -1

3. если нет остатка - деление является «четным» - тогда возвращаемое значение является целым частным

4. В противном случае возвращается наименьшее целое число, которое на больше , чем частное, то есть всегда округляется в большую сторону.

Теперь у нас есть спецификация, поэтому мы знаем, что можем придумать тестируемый дизайн . Предположим, мы добавили дополнительный критерий проектирования, согласно которому задача должна решаться исключительно с помощью целочисленной арифметики, а не вычисления коэффициента как двойного, поскольку «двойное» решение было явно отклонено в формулировке задачи.

Так что мы должны вычислять? Понятно, что для соответствия нашей спецификации, оставаясь исключительно в целочисленной арифметике, нам нужно знать три факта. Во-первых, каково целое отношение? Во-вторых, было ли разделение свободным от остатка? И в-третьих, если нет, вычислялся ли целочисленный коэффициент округлением в большую или меньшую сторону?

Теперь, когда у нас есть спецификация и дизайн, мы можем начать писать код.

public static int DivRoundUp(int dividend, int divisor)
{
  if (divisor == 0 ) throw ...
  if (divisor == -1 && dividend == Int32.MinValue) throw ...
  int roundedTowardsZeroQuotient = dividend / divisor;
  bool dividedEvenly = (dividend % divisor) == 0;
  if (dividedEvenly) 
    return roundedTowardsZeroQuotient;

  // At this point we know that divisor was not zero 
  // (because we would have thrown) and we know that 
  // dividend was not zero (because there would have been no remainder)
  // Therefore both are non-zero.  Either they are of the same sign, 
  // or opposite signs. If they're of opposite sign then we rounded 
  // UP towards zero so we're done. If they're of the same sign then 
  // we rounded DOWN towards zero, so we need to add one.

  bool wasRoundedDown = ((divisor > 0) == (dividend > 0));
  if (wasRoundedDown) 
    return roundedTowardsZeroQuotient + 1;
  else
    return roundedTowardsZeroQuotient;
}

Это умно? Нет. Красиво? Нет. Коротко? Правильно ли в соответствии со спецификацией? Я верю в это, но я не полностью протестировал его. Хотя это выглядит довольно хорошо.

Мы здесь профессионалы; использовать хорошие инженерные практики. Изучите свои инструменты, укажите желаемое поведение, сначала рассмотрите случаи ошибок, и напишите код, чтобы подчеркнуть его очевидную правильность. И когда вы обнаружите ошибку, подумайте, не является ли ваш алгоритм изначально ошибочным, прежде чем вы случайным образом начинайте менять местами сравнения и прерывать то, что уже работает.

Answer 2

Все ответы здесь пока кажутся слишком сложными.

В C # и Java для получения положительных дивидендов и делителей вам просто нужно сделать:

( dividend + divisor - 1 ) / divisor 

Источник: Преобразование чисел, Roland Backhouse, 2001

Answer 3

Окончательный int-based ответ

Для целых чисел со знаком:

int div = a / b;
if (((a ^ b) >= 0) && (a % b != 0))
    div++;

Для целых чисел без знака:

int div = a / b;
if (a % b != 0)
    div++;

Обоснование этого ответа

Целочисленное деление '/' определено для округления до нуля (7.7.2 спецификации), но мы хотим округлить в большую сторону. Это означает, что отрицательные ответы уже округлены правильно, но положительные ответы необходимо скорректировать.

Нулевые положительные ответы легко обнаружить, но нулевой ответ немного сложнее, поскольку это может быть либо округление отрицательного значения, либо округление положительного.

Самая безопасная ставка - определить, когда ответ должен быть положительным, проверив, что знаки обоих целых совпадают. Целочисленный оператор xor '^' для этих двух значений приведет к появлению 0-значного бита, если это так, что означает неотрицательный результат, поэтому проверка (a ^ b) >= 0 определяет, что результат должен быть положительным до округления. Также обратите внимание, что для целых чисел без знака каждый ответ явно положительный, поэтому эту проверку можно опустить.

Тогда остается только проверить, произошло ли какое-либо округление, для которого a % b != 0 выполнит работу.

Извлеченные уроки

Арифметика (целочисленная или иная) не так проста, как кажется. Всегда нужно тщательно обдумывать.

Кроме того, хотя мой окончательный ответ, возможно, не такой «простой» или «очевидный» или, возможно, даже «быстрый», как ответы с плавающей запятой, у меня есть одно очень сильное искупительное качество для меня; Теперь я обдумал ответ, поэтому я уверен, что он правильный (пока кто-нибудь умнее не скажет мне иначе - украдкой взгляд в сторону Эрика -).

Чтобы получить такое же чувство уверенности в ответе с плавающей запятой, мне нужно было бы сделать больше (и, возможно, более сложно) подумать о том, существуют ли какие-либо условия, при которых точность с плавающей запятой может мешать, и Math.Ceiling возможно делает что-то нежелательное на "правильных" входах.

пройденный путь

Заменить (заметьте, я заменил второе myInt1 на myInt2, предполагая, что это то, что вы имели в виду):

(int)Math.Ceiling((double)myInt1 / myInt2)

с:

(myInt1 - 1 + myInt2) / myInt2

Единственное предостережение в том, что если myInt1 - 1 + myInt2 переполняет целочисленный тип, который вы используете, вы можете не получить то, что ожидаете.

Причина, по которой это неправильно : -1000000 и 3999 должны дать -250, это дает -249

EDIT:
Учитывая, что это имеет ту же ошибку, что и другое целочисленное решение для отрицательных значений myInt1, может быть проще сделать что-то вроде:

int rem;
int div = Math.DivRem(myInt1, myInt2, out rem);
if (rem > 0)
  div++;

Это должно дать правильный результат в div, используя только целочисленные операции.

Причина, по которой это неправильно : -1 и -5 должны давать 1, это дает 0

РЕДАКТИРОВАТЬ (еще раз, с чувством):
Оператор деления округляется до нуля; для отрицательных результатов это совершенно верно, поэтому только неотрицательные результаты требуют корректировки. Также учитывая, что DivRem просто выполняет / и % в любом случае, давайте пропустим вызов (и начнем с простого сравнения, чтобы избежать вычисления по модулю, когда оно не нужно):

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

Причина, по которой это неправильно : -1 и 5 должны давать 0, это дает 1

(Защищая последнюю попытку, я никогда не должен был пытаться дать обоснованный ответ, пока мой разум говорил мне, что я на 2 часа опоздал на сон)

Answer 4

Прекрасный шанс использовать метод расширения:

public static class Int32Methods
{
    public static int DivideByAndRoundUp(this int number, int divideBy)
    {                        
        return (int)Math.Ceiling((float)number / (float)divideBy);
    }
}

Это также делает ваш код более читабельным:

int result = myInt.DivideByAndRoundUp(4);

Answer 5

Вы можете написать помощника.

static int DivideRoundUp(int p1, int p2) {
  return (int)Math.Ceiling((double)p1 / p2);
}

Answer 6

Вы можете использовать что-то вроде следующего.

a / b + ((Math.Sign(a) * Math.Sign(b) > 0) && (a % b != 0)) ? 1 : 0)

Answer 7

Проблема всех решений здесь либо в том, что они нуждаются в приведении, либо в числовой проблеме. Кастинг на float или double всегда возможен, но мы можем добиться большего.

При использовании кода ответа от @ jerryjvl

int div = myInt1 / myInt2;
if ((div >= 0) && (myInt1 % myInt2 != 0))
    div++;

есть ошибка округления. 1/5 будет округлять вверх, потому что 1% 5! = 0. Но это неправильно, потому что округление произойдет только в том случае, если вы замените 1 на 3, поэтому результат равен 0,6. Нам нужно найти способ округления, когда вычисление дает нам значение, большее или равное 0,5. Результат оператора по модулю в верхнем примере имеет диапазон от 0 до myInt2-1. Округление произойдет только в том случае, если остаток больше 50% делителя. Таким образом, скорректированный код выглядит так:

int div = myInt1 / myInt2;
if (myInt1 % myInt2 >= myInt2 / 2)
    div++;

Конечно, у нас есть проблема с округлением на myInt2 / 2, но этот результат даст вам лучшее решение для округления, чем на этом сайте.