Soustraire / ajouter de la valeur sans débordement ni dépassement

Question

Imaginez, j'ai deux octets non signés b et x. J'ai besoin de calculer le bsub comme b - x et badd comme b + x. Cependant, je ne veux pas de dépassement inférieur/dépassement de se produire au cours de ces opérations. Par exemple (pseudo-code):

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

et

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

Le moyen le plus évident pour ce faire, comprend de branchement:

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

Je me demande juste si il ya des meilleures façons de le faire, c'est à dire par certains hacky peu de manipulations?

Answer 1

L’article Branchfree saturant arithmétique fournit des stratégies pour cela :

Leur solution d’addition est comme suit :

modification d’uint8_t :

et leur solution de soustraction est :

modification d’uint8_t :

Answer 2

Une méthode simple consiste à détecter de débordement et de réinitialiser la valeur en conséquence comme ci-dessous

GCC peut optimiser le contrôle de dépassement de capacité sous une attribution conditionnelle lors de la compilation avec - O2.

J’ai mesuré combien optimisation en comparant avec d’autres solutions. Avec 1000000000 + opérations sur mon PC, cette solution et celle de @ShafikYaghmour en moyenne 4,2 secondes, et celle de @chux en moyenne 4,8 secondes. Cette solution est plus lisible ainsi.

Answer 3

Pour la soustraction:

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

Plus:

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

---

L'évolution

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

Merci à @R_Kapp

Merci à @NathanOliver

Cet exercice montre la valeur de simplement de codage.

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

Answer 4

Si vous utilisez une version assez récente de gcc ou clang (peut-être aussi quelques autres), vous pouvez utiliser built-ins pour détection de dépassement de capacité.

Answer 5

Si vous êtes prêt à utiliser de l'assemblée ou intrinsèques, je pense avoir une solution optimale.

Pour la soustraction:

Nous pouvons utiliser l' sbb enseignement

Dans MSVC, nous pouvons utiliser la fonction intrinsèque _subborrow_u64 (également disponible dans d'autres bits tailles).

Voici comment il est utilisé:

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

Voici comment on pourrait l'appliquer à votre situation

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

Pour plus:

Nous pouvons utiliser l' adcx enseignement

Dans MSVC, nous pouvons utiliser la fonction intrinsèque _addcarry_u64 (également disponible dans d'autres bits tailles).

Voici comment il est utilisé:

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

Voici comment on pourrait l'appliquer à votre situation

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

Je n'aime pas celui-ci autant que la soustraction, mais je pense que c'est assez chouette.

Si l'ajouter les débordements, carry_flag = 1. Pas-ing carry_flag rendements 0, !carry_flag * result = 0 lorsqu'il y a dépassement de capacité. Et depuis 0 - 1 sera de définir la unsigned partie intégrante de la valeur à son maximum, la fonction retourne le résultat de l'addition s'il n'y a pas de report et de retour au max, le choix de la valeur intégrale si il y a transporter.