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

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



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);


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

715   11  

11 ответов:

статьи Насыщающая Арифметика Без Ветвей обеспечивает стратегии для этого:

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

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;
}
79  
2015-11-02 18:23:25

простой метод заключается в обнаружении переполнения и сбросить значение соответственно, как показано ниже

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 секунды. Это решение также более читабельно.

39  
2015-11-02 18:57:16

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

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);
16  
2017-05-23 14:46:18

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

if (__builtin_add_overflow(a,b,&c))
{
  c = UINT_MAX;
}
10  
2015-11-03 08:40:18

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

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

мы можем использовать 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;
}

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

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

3  
2015-11-04 18:57:56

Как насчет этого:

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

bsub = a - b;
bsub = (bsub > a || bsub > b) ? 0 : bsub;
2  
2015-11-02 17:48:40

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

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

// Subtraction without underflow
return (b > a) ? 0 : a - b;
2  
2015-11-02 18:44:22

если вы будете называть эти методы много, самый быстрый способ будет не бит манипуляции, но, вероятно, таблица поиска. Определите массив длины 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.

если вы настаиваете на операции bits, ответы, которые используют (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-битные вычисления выполняются немного быстрее. До вас

2  
2015-11-02 19:54:36

дополнения:

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);

не требуется никаких операторов сравнения или умножения.

2  
2015-11-02 22:33:23

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

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

2  
2015-11-03 03:44:31

вы также можете использовать библиотеку safe numerics по адресу Boost Библиотека Инкубатор. Он обеспечивает падени-в заменах для инт, длиной, ЕТК... что гарантирует, что вы никогда не получите незамеченное переполнение, подток и т. д.

2  
2015-11-03 06:18:31

Comments

    Ничего не найдено.
Click here to cancel reply.