Функции С++ для целочисленного деления с четко определенной стратегией округления

Я хочу что-то в С++, что позволяет мне делать эффективное целочисленное деление с заданным действием округления, примерно так:

div_down(-4,3)        ==> -2
div_up(4,3)           ==> 2
div_to_zero(-4,3)     ==> -1
div_to_nearest(5,3)   ==> 2

Я бы хотел, чтобы он обнаруживал поведение целевой машины во время компиляции и генерировал соответствующие оптимальные реализации. Нечто подобное для модуля также было бы хорошим, абстрагировав поведение undefined для отрицательных операндов во время компиляции.

Это существует?

Если нет, какой хороший способ сделать это? Я могу придумать несколько возможных подходов:

  • Попробуйте реализовать их как отдельные выражения, которые статически оптимизируют
  • Используйте константные выражения для определения поведения цели и выбора из нескольких реализаций, возможно используя шаблоны (но как именно?)

Ответы

Ответ 1

Это то, что у меня есть до сих пор, с предварительным условием d > 0. Все они работают, но могут ли они быть упрощены?

int div_down(int n, int d) {
  if (n < 0) {
    return -((d - n - 1) / d);
  } else {
    return n / d;
  }
}

int div_up(int n, int d) {
  if (n < 0) {
    return -(-n / d);
  } else {
    return (n + d - 1) / d;
  }
}

int div_to_zero(int n, int d) {
  return n / d;
}

int div_to_nearest(int n, int d) {
  if (n < 0) {
    return (n - d/2 + 1) / d;
  } else {
    return (n + d/2) / d;
  }
}

Ответ 2

Последний черновик С++ 11, n3242, который почти идентичен фактическому стандарту С++ 11, говорит об этом в пункте 5.6 пункта 4 (стр. 118):

Для интегральных операндов оператор/дает алгебраическое отношение с отброшенной фракцией; (см. примечание 80)

Примечание 80 состояний (обратите внимание, что примечания являются ненормативными):

80) Это часто называют усечением к нулю.

Для полноты, точка 4 продолжает указывать:

если частное a/b представимо в типе результата, (a/b) * b + a% b равно a.

который, как можно показать, требует, чтобы знак a%b был таким же, как знак a (если не ноль).

Примечание. Фактический стандарт С++ 11 не доступен в режиме онлайн. Однако проекты есть. К счастью, различия между последним проектом (N3242) и фактическим стандартом малы. См. этот ответ.

ПРИМЕЧАНИЕ. Я не уверен, какие компиляторы придерживаются стандарта С++ 11.

So div_to_zero() - регулярное деление /.

Для других функций, боюсь, вам придется протестировать знаки a и b и соответствующим образом скорректировать. Иногда может потребоваться дополнительная проверка того, равен ли a%b нулю. Итак, мы смотрим на 12 тестовых примеров на каждую функцию здесь (3 для знака или нулевой точки a, раз 2 для знака b, раз 2, если a%b равно нулю или нет).

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

Я знаю, что я не ответил на ваш вопрос, но информация выше показалась мне ценной и была слишком большой, чтобы вписаться в комментарий.

Ответ 3

Старый пост, но вот он идет. Просьба принять и оценить его, если хотите.

int div_to_zero(int n, int d) { return n / d; }
//as per C++11 standard note 80

int div_up(int n, int d) {
    return n / d + (((n < 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && positive result)

int div_down(int n, int d) {
    return n / d - (((n > 0) ^ (d > 0)) && (n % d));
} //i.e. +1 iff (not exact int && negative result)

int div_to_nearest(int n, int d) {
    return (2*n - d + 2*(true&&(n<0^d>0))*d) / (2*d); 
} //i.e. +-0.5 as per pre-rounding result sign, then div_to-zero 
//it however rounds numbers like +/- 3.5 towards 0 and not even.

Примечание. Большинство современных компиляторов будут использовать операцию единичного деления для n/d и n% d, используемых совместно. Таким образом, их производительность лучше всего уменьшает количество перемещений памяти.