Odejmowanie / dodawanie wartości bez przepełnienia lub niedopełnienia

Prostą metodą jest wykrycie przepełnienia i zresetowanie wartości odpowiednio jak poniżej

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

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

GCC może zoptymalizować sprawdzenie przepełnienia do warunkowego przypisania podczas kompilacji z-O2.

Zmierzyłem, ile optymalizacji w porównaniu z innymi rozwiązaniami. Z operacjami 1000000000 + na moim komputerze, To rozwiązanie i @ShafikYaghmour wynosiły średnio 4,2 sekundy, a @chux średnio 4,8 sekundy. To rozwiązanie jest również bardziej czytelne.

Dla odejmowania:

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

Dodanie:

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

Ewolucja

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

Dzięki @R_Kapp

Dzięki @ NathanOliver

To ćwiczenie pokazuje wartość prostego kodowania.

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

Jeśli używasz najnowszej wersji gcc lub clang (może również niektórych innych), Możesz użyć Wbudowanych do wykrywania przepełnienia.

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

Jeśli chcesz użyć assembly lub intrinsics, myślę, że mam optymalne rozwiązanie.

Dla odejmowania:

Możemy użyć sbb Instrukcja

W MSVC możemy użyć funkcji wewnętrznej _subborrow_u64 (dostępne również w innych rozmiarach bitów).

Oto Jak to jest używane:

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

Oto jak możemy zastosować to do twojej sytuacji

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

Do dodania:

Możemy użyć adcx Instrukcja

W MSVC możemy użyć funkcji wewnętrznej _addcarry_u64 (dostępne również w innych rozmiarach bitów).

Oto Jak to jest używane:

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

Oto jak możemy zastosować to do twojej sytuacji

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

Nie podoba mi się ta tak bardzo jak ta odejmowana, ale myślę, że jest całkiem fajna.

Jeśli dodawanie przepełnia się, carry_flag = 1. Nie-ing carry_flag daje 0, więc !carry_flag * result = 0 gdy jest przepełnienie. And since 0 - 1 will set the unsigned wartość całki do jej max, funkcja zwróci wynik dodawania, jeśli nie ma carry i zwróci max wybranej wartości całki, jeśli istnieje carry.

A co z tym:

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

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

Wszystko można wykonać w arytmetyce bajtów niepodpisanych

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

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

Jeśli będziesz często wywoływał te metody, najszybszym sposobem nie byłaby manipulacja bitami, ale prawdopodobnie tabela wyszukiwania. Zdefiniuj tablicę długości 511 dla każdej operacji. Przykład dla minus (odejmowanie)

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

Tablica jest statyczna i zainicjalizowana tylko raz. Teraz odejmowanie można zdefiniować jako metodę inline lub używając pre-kompilatora:

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

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

Użyj go jak:

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

Zauważ, że wykonanie jest niezwykle szybkie. Tylko jedno odejmowanie i jeden wskaźnik szacunku, aby uzyskać wynik. Bez rozgałęzień. Tablice statyczne są bardzo krótkie, więc zostaną w pełni załadowane do pamięci podręcznej procesora w celu dalszej szybkości up the calculation

To samo działa dla dodawania, ale z nieco inną tabelą (pierwsze 256 elementów będzie indeksami, a ostatnie 255 elementów będzie równe 255, aby naśladować odcięcia poza 255.

Jeśli nalegasz na działanie bitów, odpowiedzi, które używają (A > b) są błędne. To nadal może być zaimplementowane jako rozgałęzienie. Użyj techniki znak-bit

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

Teraz możesz go użyć do obliczania odejmowania i dodawania.

Jeśli chcesz emulować funkcje max(), min () bez użycia rozgałęzień:

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

Moje przykłady powyżej używają 32-bitowych liczb całkowitych. Można go zmienić na 64, choć uważam, że obliczenia 32 bitowe działają nieco szybciej. Do Ciebie

Dla dodania:

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

Dla odejmowania:

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

Nie są wymagane żadne operatory porównawcze ani mnożenie.

Jeśli chcesz to zrobić z dwoma bajtami, użyj najprostszego możliwego kodu.

Jeśli chcesz to zrobić z dwudziestoma miliardami bajtów, sprawdź jakie instrukcje wektorowe są dostępne na Twoim procesorze i czy można ich użyć. Może się okazać, że procesor może wykonać 32 z tych operacji za pomocą jednej instrukcji.

Możesz również skorzystać z biblioteki safe numerics w inkubatorze Boost Library. Zapewnia zamienniki drop-in dla int, long, itp... które gwarantują, że nigdy nie dostaniesz niewykrytego przelewu, niedopełnienia itp.