Подтвердить что ты не робот

Вычитание/добавление значения без переполнения или переполнения

Предположим, у меня есть два беззнаковых байта b и x. Мне нужно вычислить bsub как b - x и badd как b + x. Тем не менее, я не хочу, чтобы во время этих операций происходило переполнение/переполнение. Например (псевдокод):

b = 3; x = 5;
bsub = b - x; // bsub must be 0, not 254

и

b = 250; x = 10;
badd = b + x; // badd must be 255, not 4

Очевидный способ сделать это включает ветвление:

bsub = b - min(b, x);
badd = b + min(255 - b, x);

Мне просто интересно, есть ли какие-нибудь более эффективные способы сделать это, т.е. с помощью некоторых хакерских манипуляций?

4b9b3361

ОТВЕТЫ

Ответ 1

В статье Нераспределяющая арифметика на уровне ветки предлагаются стратегии для этого:

Их аддитивное решение выглядит следующим образом:

u32b sat_addu32b(u32b x, u32b y)
{
    u32b res = x + y;
    res |= -(res < x);

    return res;
}

изменен для uint8_t:

uint8_t  sat_addu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x + y;
    res |= -(res < x);

    return res;
}

и их решение вычитания:

u32b sat_subu32b(u32b x, u32b y)
{
    u32b res = x - y;
    res &= -(res <= x);

    return res;
}

изменен для uint8_t:

uint8_t sat_subu8b(uint8_t x, uint8_t y)
{
    uint8_t res = x - y;
    res &= -(res <= x);

    return res;
}

Ответ 2

Простым методом является обнаружение переполнения и reset значение соответственно ниже

bsub = b - x;
if (bsub > b)
{
    bsub = 0;
}

badd = b + x;
if (badd < b)
{
    badd = 255;
}

GCC может оптимизировать проверку переполнения в условное присваивание при компиляции с -O2.

Я измерил, насколько оптимизирован по сравнению с другими решениями. С 1000000000+ операций на моем ПК это решение, а решение @ShafikYaghmour составляло в среднем 4,2 секунды, а для @chux - в среднем 4,8 секунды. Это решение более читаемо.

Ответ 3

Для вычитания:

diff = (a - b)*(a >= b);

Дополнение:

sum = (a + b) | -(a > (255 - b))

Эволюция

// sum = (a + b)*(a <= (255-b)); this fails
// sum = (a + b) | -(a <= (255 - b)) falis too

Благодаря @R_Kapp

Благодаря @NathanOliver

Это упражнение показывает значение простого кодирования.

sum = b + min(255 - b, a);

Ответ 4

Если вы используете достаточно новую версию gcc или clang (возможно, некоторые другие), вы можете использовать встроенные функции для обнаружения переполнения.

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}

Ответ 5

Для добавления:

unsigned temp = a+b;  // temp>>8 will be 1 if overflow else 0
unsigned char c = temp | -(temp >> 8);

Для вычитания:

unsigned temp = a-b;  // temp>>8 will be 0xFF if neg-overflow else 0
unsigned char c = temp & ~(temp >> 8);

Нет операторов сравнения или умножений.

Ответ 6

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

Для вычитания:

Мы можем использовать команду sbb

В MSVC мы можем использовать внутреннюю функцию _ subborrow_u64 (также доступны в других размерах бит).

Вот как он используется:

// *c = a - (b + borrow)
// borrow_flag is set to 1 if (a < (b + borrow))
borrow_flag = _subborrow_u64(borrow_flag, a, b, c);

Вот как мы можем применить его к вашей ситуации

uint64_t sub_no_underflow(uint64_t a, uint64_t b){
    uint64_t result;
    borrow_flag = _subborrow_u64(0, a, b, &result);
    return result * !borrow_flag;
}

Для добавления:

Мы можем использовать инструкцию adcx

В MSVC мы можем использовать внутреннюю функцию _ addcarry_u64 (также доступную в других размерах бит).

Вот как он используется:

// *c = a + b + carry
// carry_flag is set to 1 if there is a carry bit
carry_flag = _addcarry_u64(carry_flag, a, b, c);

Вот как мы можем применить его к вашей ситуации

uint64_t add_no_overflow(uint64_t a, uint64_t b){
    uint64_t result;
    carry_flag = _addcarry_u64(0, a, b, &result);
    return !carry_flag * result - carry_flag;
}

Мне это не нравится, как вычитание, но я думаю, что он довольно изящный.

Если добавление переполняется, carry_flag = 1. Not-ing carry_flag дает 0, поэтому !carry_flag * result = 0, когда происходит переполнение. И поскольку 0 - 1 установит значение без знакового значения в значение max, функция вернет результат сложения, если нет переноса и возвращает максимум выбранного интегрального значения, если есть перенос.

Ответ 7

что об этом:

bsum = a + b;
bsum = (bsum < a || bsum < b) ? 255 : bsum;

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;

Ответ 8

Вы также можете использовать библиотеку безопасных чисел в Boost Library Incubator. Он предоставляет замены для замены для int, long и т.д., Которые гарантируют, что вы никогда не получите необнаруженное переполнение, недополнение и т.д.

Ответ 9

Все может быть выполнено в беззнаковой байтовой арифметике

// Addition without overflow
return (b > 255 - a) ? 255 : a + b

// Subtraction without underflow
return (b > a) ? 0 : a - b;

Ответ 10

Если вы хотите сделать это с помощью двух байтов, используйте самый простой код.

Если вы хотите сделать это с двадцатью миллиардами байт, проверьте, какие векторные инструкции доступны на вашем процессоре и можно ли их использовать. Вы можете обнаружить, что ваш процессор может выполнить 32 из этих операций с помощью одной команды.

Ответ 11

Если вы вызовете эти методы много, самым быстрым способом будет не манипуляция бит, а, вероятно, справочная таблица. Определите массив длиной 511 для каждой операции. Пример для минус (вычитание)

static unsigned char   maxTable[511];
memset(maxTable, 0, 255);           // If smaller, emulates cutoff at zero
maxTable[255]=0;                    // If equal     - return zero
for (int i=0; i<256; i++)
    maxTable[255+i] = i;            // If greater   - return the difference

Массив статический и инициализируется только один раз. Теперь вычитание может быть определено как встроенный метод или с использованием предварительного компилятора:

#define MINUS(A,B)    maxTable[A-B+255];

Как это работает? Ну, вы хотите предварительно вычислить все возможные вычитания для неподписанных символов. Результаты варьируются от -255 до +255, всего 511 разных результатов. Мы определяем массив всех возможных результатов, но поскольку в C мы не можем получить к нему доступ из отрицательных индексов, мы используем +255 (в [A-B + 255]). Вы можете удалить это действие, указав указатель на центр массива.

const unsigned char *result = maxTable+255;
#define MINUS(A,B)    result[A-B];

используйте его как:

bsub  = MINUS(13,15); // i.e 13-15 with zero cutoff as requested

Обратите внимание, что выполнение выполняется очень быстро. Только одно вычитание и одно указание указателя, чтобы получить результат. Нет ветвления. Статические массивы очень короткие, поэтому они будут полностью загружены в кеш процессора, чтобы ускорить вычисление

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

Если вы настаиваете на работе битов, ответы, которые используют (a > b), неверны. Это может быть реализовано как ветвление. Использовать технику с надписью

// (num1>num2) ? 1 : 0
#define        is_int_biggerNotEqual( num1,num2) ((((__int32)((num2)-(num1)))&0x80000000)>>31)

Теперь вы можете использовать его для вычисления вычитания и добавления.

Если вы хотите эмулировать функции max(), min() без ветвления использует:

inline __int32 MIN_INT(__int32 x, __int32 y){   __int32 d=x-y; return y+(d&(d>>31)); }              

inline __int32 MAX_INT(__int32 x, __int32 y){   __int32 d=x-y; return x-(d&(d>>31)); }

В приведенных выше примерах используются 32-битные целые числа. Вы можете изменить его на 64, хотя я считаю, что 32-разрядные вычисления выполняются немного быстрее. До вас