Кажется, что всякий раз, когда я делю отрицательный int на положительный int, мне нужно, чтобы он округлялся (в сторону -inf), а не на 0. Но оба С# и С++ округлились к 0.
Итак, мне нужен метод DivideDownward(). Я могу написать это в нескольких строках с тестом на отрицание и так далее, но мои идеи кажутся klugey. Поэтому мне интересно, не хватает ли я чего-то, и если у вас есть "элегантный" способ округлить отрицательное деление вниз.
ПРЕДУПРЕЖДЕНИЕ: этот пост создает неверные результаты для ввода с a = -1. См. Другие ответы. -cam
[С++]
Это, вероятно, то, что вы имели в виду под "kludgey", но это то, что я придумал;)
int divideDown(int a, int b){
int r=a/b;
if (r<0 && r*b!=a)
return r-1;
return r;
}
В выражении if я помещаю r < 0 - однако я не уверен, что это то, что вы хотите. Вы можете изменить оператор if на
if (a<0 && b>0)
который будет соответствовать вашему описанию "Кажется, что всякий раз, когда я делю отрицательный int на положительный int".
Всякий раз, когда я делю отрицательный int на положительный int, мне нужно его округлить.
Да, черт возьми, не так ли? Кнут писал, почему это правильный способ сделать что-то, но мы застряли в унаследованном целочисленном аппаратном обеспечении.
Если вы можете позволить себе потерю точности, самым простым и чистым способом сделать это - отбросить 32-битное целое число до 64-битного double и использовать режим округления FP для округления до минус бесконечности когда вы преобразовываете фактор обратно в целое. Сегодня единицы с плавающей запятой довольно быстры и могут фактически делить быстрее, чем целое число; конечно, вы должны были бы измерить.
Если вам нужна полная 64-разрядная целая точность, я рассмотрел эту проблему как писатель-компилятор, выполнив две условные ветки, чтобы вы завершили разделение величин, а затем получили правильный знак. Но это было некоторое время назад, когда условная ветка была дешевой по сравнению с делением; на сегодняшнем оборудовании мне пришлось бы экспериментировать, прежде чем я смогу что-то порекомендовать.
В принципе, вы можете потянуть трюк с плавающей запятой в 64-битных ints, используя устаревшие номера с плавающей запятой Intel 80 бит, но он невероятно неспособен, и я не верю, что Intel будет продолжать делать это устройство быстро. В наши дни скорость с плавающей запятой находится в блоке SSE.
Места поиска других трюков будут включать книгу Хэнка Уоррена Hacker Delight (моя копия на работе) и MLton компилятор для стандартного ML, который требует целочисленного деления округлять до минусовой бесконечности.
Независимо от того, что вы делаете, когда вы будете улажены, если вы используете С++ или C99, придерживайте свою процедуру разделения в файл .h и делайте ее static inline. Таким образом, когда ваше решение окажется субоптимальным для нового оборудования whizbang, поставляемого через 5 лет, у вас есть одно место для его изменения.
Предполагая, что b всегда положительно, вот дешевое решение:
inline int roundDownDivide(int a, int b) {
if (a >= 0) return a/b;
else return (a-b+1)/b;
}
Вы можете избавиться от любого ветвления, выполнив следующее:
inline int DivideRoundDown(int a_numerator, int a_denominator)
{
return (a_numerator / a_denominator) + ((a_numerator % a_denominator) >> 31);
}
Если вы хотите написать это, просто используя целые числа относительно лаконичным образом, вы можете написать это:
var res = a / b - (a % b < 0 ? 1 : 0);
Это, вероятно, компилируется в несколько инструкций, но все же может быть быстрее, чем использование плавающих точек.
Math.Floor((double)a/(double)b)
если вам это нужно как int, бросьте его потом
(int)Math.Floor((double)a/(double)b)
Для полномочий 2, в зависимости от реализации вашего компилятора (Visual Studio), вы можете использовать сдвиг вправо.
-5 >> 2 == -2
Решение Dr Atlans выше - это самый общий ответ, но если вы знаете, что a не будет меньше некоторого фиксированного числа, вы можете добавить наименьший кратный b, который сделает его положительным, а затем скорректируйте результат. Например, если a всегдa >= -10 * b, вы можете сказать:
return (a + 10 * b) / b - 10
или если вы просто хотите получить правильный результат, если a положительный или 0, и некоторый отрицательный результат, когда a отрицательный (например, для тестирования, если результат равен >= 0 без включения диапазона a = [-1; -b +1 ]) вы можете сделать
return (a + b) / b - 1;
который будет возвращать -1 для [-1, -b + 1], а также для [-b; -2 * b + 1], но это не имеет значения, если вы просто пытаетесь установить, является ли результат деления положительным. Эффективно мы просто меняем округление так, чтобы оно округлялось к -1 вместо 0.
Я не эксперт в оптимизации на низком уровне, но здесь версия без ветвления (условные выражения), которая также не требует преобразований чисел с плавающей запятой. Протестировано на С#, оно, кажется, значительно быстрее, чем версии с использованием ветвления.
return (a - (((a % b) + b) % b)) / b;
Это решение частично получено из обсуждений о том, как сделать лучшую функцию по модулю для отрицательных чисел: Модуль отрицательных чисел
Многие языки программирования, включая более старые стандарты C и С++, гарантируют правило деления, которое
a = b * (a / b) + a % b
даже если точные значения a/b и a%b остаются undefined. (В настоящее время они определены в C и С++.) Это может быть использовано для вычисления желаемого результата на многих языках и платформах, используя (эквивалент) следующий код:
int divF(int a, int b) { return a / b - (a % b < 0); }
Это версия из ответа @TomasPetricek. Однако это работает только для b > 0!
Следующий код будет работать для любого b != 0: [1]
int sign(int x) { return (x > 0) - (x < 0); }
int divF2(int a, int b) { return a / b - (sign(a % b) == -sign(b)); }
Однако округление (или разделение полов, а также подразделение Кнута) не всегда желательно. Утверждается [2] что евклидово разделение является наиболее общедоступным. Он округляется до b > 0 и вверх для b < 0. Он обладает хорошим свойством, что значение согласованного по определению остатка всегда неотрицательно, для всех a, b, независимо от их знаков. Кроме того, он совпадает с бит-сдвигами на двухкомпонентных машинах для делителей мощности двух делений. Да, он также быстрее вычисляет:
int divE(int a, int b) {
int c = a % b < 0;
return a / b + (b < 0 ? c : -c);
}
Все три версии генерируют нераспространяемый код с clang 3.4.1 -O2 на amd64. Тем не менее, на двух дополнительных архитектурах, следующее может быть немного быстрее:
int divE2(int a, int b) { return a / b + (-(a % b < 0) & (b < 0 ? 1 : -1)); }
divF:
cdq
idiv esi
shr edx, 31
sub eax, edx
divF2:
cdq
idiv esi
test edx, edx
setg cl
movzx ecx, cl
shr edx, 31
sub ecx, edx
test esi, esi
setg dl
movzx edx, dl
shr esi, 31
sub esi, edx
cmp ecx, esi
sete cl
movzx ecx, cl
sub eax, ecx
Dive:
cdq
idiv esi
mov ecx, edx
shr ecx, 31
sar edx, 31
test esi, esi
cmovs edx, ecx
add eax, edx
divE2:
cdq
idiv esi
sar edx, 31
shr esi, 31
lea ecx, dword ptr [rsi + rsi - 1]
and ecx, edx
add ecx, eax
mov eax, ecx // WTF? But OK when inlined...
С вышеупомянутым компилятором на i7-3720QM CPU @2.60GHz, запуская следующий код с различными TESTFUNC, дает
simple truncating division:
1225053229 base: 8.41 ns
round to -inf for b > 0, broken for b < 0:
975205675 divF: 8.70 ns
975205675 ben135: 8.71 ns
euclidean division:
1225082031 divE2: 9.37 ns
1225082031 divE: 9.67 ns
round to -inf, work for b < 0:
975229215 Chazz: 9.67 ns
975229215 divF2: 10.56 ns
975229215 runevision: 13.85 ns
975229215 LegsDrivenCat: 16.62 ns
975229215 Warty: 20.00 ns
likely an overflow bug trying to implement the above:
975049659 DrAltan: 11.77 ns
Первый столбец - это алгоритмы группировки контрольных сумм, которые дают тот же результат. base - это простейшее усекающее деление, используемое для измерения накладных расходов на тестирование.
код:
#define STRINGIZE2(a) #a
#define STRINGIZE(a) STRINGIZE2(a)
int main()
{
srandom(6283185);
static const int N = 500000000;
int ret = 0;
for(int i = 0; i < N; ++i)
{
int a = random() - 0x40000000, b;
do b = (random() >> 16) - 0x4000; while(b == 0);
ret += TESTFUNC(a,b);
}
timespec t;
clock_gettime(CLOCK_VIRTUAL, &t);
printf("%10d %20s: %5.2f ns\n", ret, STRINGIZE(TESTFUNC), (t.tv_sec*1.e9 + t.tv_nsec)/N);
}
Изменить: Мое решение не работало во всех случаях. Здесь реализация С# решения Dr.Atlan:
/// <summary>
/// Divides a/b, rounding negative numbers towards -Inf.
/// </summary>
/// <param name="a">Dividend</param>
/// <param name="b">Divisor; must be positive for correct results</param>
/// <returns>a ÷ b</returns>
public static int Div(int a, int b)
{
return a < 0 ? (a - b + 1) / b : a / b;
}
Здесь версия, которая работает, когда делитель отрицателен:
int floor_div2(int a, int b)
{
int rem = a % b;
int div = a/b;
if (!rem)
a = b;
int sub = a ^ b;
sub >>= 31;
return div+sub;
}
Выполняйте вычисления в unsigned long путем смещения с помощью 2 ^ 31, например:
int floor_div(int a, int b)
{
unsigned long aa = a + (1UL << 31);
unsigned long cc = (aa / b) - (1UL << 31);
return (int)cc
}
Я не тестировал это.
Я сделал это так (только одно деление, без умножения, без модуля, выглядит как быстрое решение):
(a < 0 && b > 0) ? (a - b + 1) / b : (a > 0 && b < 0) ? (a - b - 1) / b : a / b
Мне было любопытно, что быстрее: меньше ветвления или меньше умножений/делений/модулов, поэтому я сравнил свое решение с runevision, а в этом конкретном случае меньше делений лучше, чем меньше разветвлений. ben135 решение дает неверные результаты в некоторых случаях (например, 10/-3 дает -3, но должно быть -4).