Округление целочисленного деления без логических операторов
Я хочу функцию
int rounded_division(const int a, const int b) {
return round(1.0 * a/b);
}
Итак, мы имеем, например,
rounded_division(3, 2) // = 2
rounded_division(2, 2) // = 1
rounded_division(1, 2) // = 1
rounded_division(0, 2) // = 0
rounded_division(-1, 2) // = -1
rounded_division(-2, 2) // = -1
rounded_division(-3, -2) // = 2
Или в коде, где a а также b 32-разрядные целые числа со знаком:
int rounded_division(const int a, const int b) {
return ((a < 0) ^ (b < 0)) ? ((a - b / 2) / b) : ((a + b / 2) / b);
}
И тут возникает сложная часть: как реализовать этого парня продуктивно (без использования больших 64-битных значений) и без логических операторов такие как ?:, &&… Это вообще возможно?
Причина, по которой мне интересно избегать логических операторов, потому что процессор, для которого я должен реализовать эту функцию, не имеет условных инструкций (Подробнее об отсутствующих условных инструкциях по ARM.).
Решение
a/b + a%b/(b/2 + b%2) работает довольно хорошо — не провалился в миллиарде + тестовых случаев. Он отвечает всем целям ОП: нет переполнения, нет long longбез разветвлений, работает во всем диапазоне int когда a/b определено.
Нет 32-битной зависимости. Если используется C99 или более поздняя версия, ограничений поведения реализации нет.
int rounded_division(int a, int b) {
int q = a / b;
int r = a % b;
return q + r/(b/2 + b%2);
}
Это работает с дополнением 2, дополнением 1 и величиной знака, так как все операции математические.
Другие решения
Как насчет этого:
int rounded_division(const int a, const int b) {
return (a + b/2 + b * ((a^b) >> 31))/b;
}
(a ^ b) >> 31 следует оценить -1 если a а также b имеют разные знаки и 0 в противном случае, при условии int имеет 32 бита, а крайний левый бит знака.
РЕДАКТИРОВАТЬ
Как отметил @chux в своих комментариях, этот метод неверен из-за целочисленного деления. Эта новая версия оценивает то же самое, что и пример OP, но содержит немного больше операций.
int rounded_division(const int a, const int b) {
return (a + b * (1 + 2 * ((a^b) >> 31)) / 2)/b;
}
Однако эта версия по-прежнему не учитывает проблему переполнения.
Как насчет
...
return ((a + (a*b)/abs(a*b) * b / 2) / b);
}
Без переполнения:
...
return ((a + ((a/abs(a))*(b/abs(b))) * b / 2) / b);
}
Это грубый подход, который вы можете использовать. Использование маски для применения чего-либо, если операция a * b < 0.
Обратите внимание, что я не проверил это должным образом.
int function(int a, int b){
int tmp = float(a)/b + 0.5;
int mask = (a*b) >> 31; // shift sign bit to set rest of the bits
return tmp - (1 & mask);//minus one if a*b was < 0
}
так как функция кажется симметричной, как насчет sign(a/b)*floor(abs(a/b)+0.5)
Следующие rounded_division_test1() соответствует требованию OP об отсутствии ветвления — если считать sign(int a), nabs(int a), а также cmp_le(int a, int b) как не разветвляющийся. Увидеть Вот за идеи о том, как это сделать sign() без сравнения операторов. Эти вспомогательные функции могут быть свернуты в rounded_division_test1() без явных звонков.
Код демонстрирует правильную функциональность и полезен для тестирования различных ответов. когда a/b определяется, этот ответ не переполняется.
#include <limits.h>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <errno.h>
int nabs(int a) {
return (a < 0) * a - (a >= 0) * a;
}
int sign(int a) {
return (a > 0) - (a < 0);
}
int cmp_le(int a, int b) {
return (a <= b);
}
int rounded_division_test1(int a, int b) {
int q = a / b;
int r = a % b;
int flag = cmp_le(nabs(r), (nabs(b) / 2 + nabs(b % 2)));
return q + flag * sign(b) * sign(r);
}
// Alternative that uses long long
int rounded_division_test1LL(int a, int b) {
int c = (a^b)>>31;
return (a + (c*2 + 1)*1LL*b/2)/b;
}
// Reference code
int rounded_division(int a, int b) {
return round(1.0*a/b);
}
int test(int a, int b) {
int q0 = rounded_division(a, b);
//int q1 = function(a,b);
int q1 = rounded_division_test1(a, b);
if (q0 != q1) {
printf("%d %d --> %d %d\n", a, b, q0, q1);
fflush(stdout);
}
return q0 != q1;
}
void tests(void) {
int err = 0;
int const a[] = { INT_MIN, INT_MIN + 1, INT_MIN + 1, -3, -2, -1, 0, 1, 2, 3,
INT_MAX - 1, INT_MAX };
for (unsigned i = 0; i < sizeof a / sizeof a[0]; i++) {
for (unsigned j = 0; j < sizeof a / sizeof a[0]; j++) {
if (a[j] == 0) continue;
if (a[i] == INT_MIN && a[j] == -1) continue;
err += test(a[i], a[j]);
}
}
printf("Err %d\n", err);
}
int main(void) {
tests();
return 0;
}
Позвольте мне внести свой вклад:
Как насчет:
int rounded_division(const int a, const int b) {
return a/b + (2*(a%b))/b;
}
Нет ветви, нет логических операторов, только математические операторы. Но он может потерпеть неудачу, если b больше INT_MAX / 2 или меньше INT_MIN / 2.
Но если разрешено 64 бита для вычисления 32-битных циклов. Не подведет
int rounded_division(const int a, const int b) {
return a/b + (2LL*(a%b))/b;
}