Comment soustraire deux entiers non signés avec les enrouler autour de débordement ou

Il existe deux entiers non signés (x et y) qui doivent être soustraits. x est toujours plus grand que y. Cependant, à la fois x et y peut s'enrouler autour d'; par exemple, si ils étaient tous les deux octets, après 0xff vient 0x00. Le cas problème est que si x entoure, tout en y ne pas. Maintenant x semble être plus petit que y. Heureusement, x sera pas autour de deux fois (une seule fois est garanti). En supposant octets, x a enveloppé et est maintenant 0x2, tandis que y a pas et est 0xFE. Le droit de réponse de x - y est censé être 0x4.

Peut-être,

( x > y) ? (x-y) : (x+0xff-y);

Mais je pense qu'il y a une autre façon, quelque chose avec la 2s compliment?, et dans ce système embarqué, x et y sont le plus grand unsigned int types, de sorte que l'ajout de 0xff... n'est pas possible

Quelle est la meilleure façon d'écrire l'instruction (de la langue cible, C)?

Ce que vous, sauf à partir de cette "meilleure façon" ? Veuillez préciser vos exigences ...
Que voulez-vous dire "à la fois x et y peuvent s'enrouler autour de"? Voulez-vous dire qu'ils pourraient s'enrouler autour de si en fonte de non signé signé types?
Les deux entiers non signés. Le cas problème est que si x entoure, tout en y ne pas. Maintenant x semble être plus petit que y. Heureusement, x sera pas autour de deux fois (une seule fois est garanti). En supposant octets, x a enveloppé et est maintenant 0x2, tandis que y a pas et est 0x14. Le droit de réponse de x - y est censé être 0x4. ( x > y) ? (x-y) : (x+0xff-y); mais je pense qu'il y a une autre façon, et dans ce système embarqué, x et y sont le plus grand unsigned int types, de sorte que l'ajout de 0xff... n'est pas possible.
Si un signé valeur intégrale est "enroulé autour de" (survolé), tous les paris sont éteints. Si vous êtes sur un complément à deux, vous pouvez toujours soustraire assigner à un unsigned valeur, mais ce n'est pas portable. Garbage in, Garbage out.
Votre reformulé la question fait encore que peu de sens. La valeur n'enveloppent pas par eux-mêmes. Une fois que vous avez x que x ne sera pas envelopper n'importe où jusqu'à ce que vous commencez à les modifier en quelque sorte. Si vous êtes de la modifier, de nous montrer comment. En ce moment il n'y a aucun moyen de vraiment comprendre ce que "envelopper" vous êtes talikng sur.
Alok: entier Signé de débordement est un comportement indéfini.
Également intéressant d'avoir un regard sur: Est entier non signé de la soustraction comportement défini? 🙂

InformationsquelleAutor mgag | 2010-01-13

c int overflow subtraction

30

Supposant deux unsigned entiers:
- Si vous savez que l'on est censé être "plus" que les autres, juste soustraire. Il fonctionnera à condition que vous n'avez pas enroulé autour de plus d'une fois (évidemment, si vous avez, vous ne serez pas en mesure de dire).
- Si vous ne savez pas que l'un est plus gros que les autres, de soustraction et de la fonte de la raison et la signature d'un int de la même largeur. Il fonctionnera à condition que la différence entre les deux est dans la gamme de la signature de l'int (si pas, vous ne serez pas en mesure de dire).
Pour clarifier: le scénario décrit par le posteur d'origine semble être embrouiller les gens, mais il est typique de plus en plus monotone à largeur fixe compteurs, tels que le matériel tique des compteurs ou des numéros de séquence dans les protocoles. Le compteur va (par exemple, pour 8 bits) 0xfc, 0xfd, 0xfe, 0xff, 0x00, 0x01, 0x02 0x03 etc., et vous savez que les deux valeurs de x et y que vous avez, x vient plus tard. Si x==0x02 et y==0xfe, le calcul de x-y (comme un 8-bit de résultat) donnera la bonne réponse de 4, en supposant que la soustraction de deux n-bit valeurs enveloppements modulo 2ⁿ - qui C99 garanties pour la soustraction de valeurs non signées. (Note: le C standard ne pas garantie de ce comportement pour la soustraction de signé valeurs).
- Vous décrivez exactement la situation que j'ai. J'ai dit que j'aurais à rendre compte de l'écharpe et "utilisation 2s compliment". Je vais essayer de mon système et de voir si en effet, elle donne le résultat correct.
- Cela ne fonctionne que pour les systèmes avec en complément à deux. Si vous êtes sur un signe de grandeur ou un " complément de la machine, la méthode "ne fonctionne pas". Une fois que vous débordement d'un int, il peut ou peut ne pas s'enrouler autour de la même manière partout.
- Si vous utilisez un type non signé en C, c'est la garantie de s'enrouler autour d', comme décrit ici, si oui ou non le système utilise 2s complément (§6.2.5, paragraphe 9: "Un calcul impliquant non signé opérandes ne peut jamais déborder, car un résultat qui ne peut pas être représenté par la résultante de type entier non signé est réduite modulo le nombre qui est plus grand que la plus grande valeur qui peut être représenté par le type résultant.")
- Il convient de répéter que Stephen est tout à fait correcte. unsigned arithmétique est complètement défini en C, en fonction de la largeur de la type non signé.
- L'OP a changé la question, et d'abord sa formulation implique qu'il s'attendait à des valeurs signées à enrouler autour prévisible. Vous êtes, bien sûr, tout à fait correct.
- Pour les types, il est garanti pour fonctionner. Pour les types signés, il n'est pas: kuliniewicz.org/blog/archives/2011/06/11/...
- merci pour les commentaires sur cette ancienne réponse et à les pousser à m'éditer. Vous et les autres, sont ici tout à fait à droite; au moment où j'ai répondu, j'avais rencontré le truc avant, mais n'était pas au courant de la garantie dans la norme qu'il travaille toujours pour unsigned soustraction.
- Casting unsigned int signé int n'est pas sûr. §6.3.1.3 entiers signés et non Signés: le nouveau type est signé et que la valeur ne peut pas être représenté dans; soit le résultat de la mise en œuvre est définie ou d'une mise en œuvre définies par le signal est déclenché.
- De toute évidence, cela fonctionne comme prévu (et tel que requis par la norme. Vous pouvez facilement tester sur chef ou dans votre compilateur.
- Voici un exemple de code qui illustre la fonctionnalité: #include <stdio.h> int main(void) { unsigned char a = 0x02, b= 0xFE, ab, ba; ab = a-b; ba = b-a; printf("a=%x, b=%x, a-b=%u, b-a=%u", a, b, ab, ba); return 0; } Ce sorties suivantes: a=2, b=fe, a-b=4, b-a=252
InformationsquelleAutor Matthew Slattery
21

Voici un peu plus en détail pourquoi il fonctionne lorsque vous soustrayez les 'petits' de la 'grande'.

Un couple de choses qui vont dans cette...

1. Dans le matériel, la soustraction utilise plus: Le opérande est tout simplement annulés avant d'être ajoutés.

2. En complément à deux (dont à peu près tout les utilisations), un entier est niée par l'inversion de tous les bits puis en ajoutant 1.

Matériel ne présente plus efficacement qu'il n'y paraît à partir de la description ci-dessus, mais c'est l'algorithme de base pour la soustraction (même lorsque les valeurs ne sont pas signés).

Ainsi, laisse la figure 2 – 250 8bit des entiers non signés. En binaire, nous avons
```
  0 0 0 0 0 0 1 0  
- 1 1 1 1 1 0 1 0
```
Nous inversons l'opérande soustrait et de les ajouter. Rappelons que pour nier d'inverser tous les bits puis ajouter 1. Après inversion des bits de la seconde opérande nous avons
```
0 0 0 0 0 1 0 1  
```
Puis après l'ajout de 1 nous avons
```
0 0 0 0 0 1 1 0  
```
Maintenant, nous avons effectuer une addition...
```
  0 0 0 0 0 0 1 0   
+ 0 0 0 0 0 1 1 0

= 0 0 0 0 1 0 0 0 = 8, which is the result we wanted from 2 - 250
```
InformationsquelleAutor Purdude
13

Peut-être que je ne comprends pas, mais ce qui est erroné avec:

unsigned r = x - y;
- En cas d'octets: 255 - ( - 10) = ?
- Il a dit deux ont été signés.
- 20 - 200 ne donne pas 0 et c'est ce qu'il voulait dire
InformationsquelleAutor GManNickG
3

La question, comme l'a dit, est source de confusion. Vous avez dit que vous êtes en soustrayant les valeurs non signées. Si x est toujours plus grand que y, comme vous l'avez dit, puis x - y ne peut l'enrouler autour de la ou de débordement. Donc, vous venez de faire x - y (si c'est ce que vous avez besoin) et c'est tout.
- x - y peuvent s'enrouler autour de si vous utilisez signé ints.
- L'objet de la question clairement et explicitement les états qui nous sont soustraction unsigned ints.
- Oups, désolé. Le contenu de la question elle-même dit juste "entiers", mais j'ai oublié de payer l'attention sur le titre lui-même.
InformationsquelleAutor AnT
2

C'est un moyen efficace pour déterminer la quantité d'espace libre dans un buffer circulaire ou faire coulissante de la fenêtre de contrôle de flux.
Utilisation unsigned ints pour head et tail - incrément et les laisser envelopper!
Longueur de la mémoire tampon doit être une puissance de 2.

free = ((head - tail) & size_mask), où size_mask est de 2^n-1 le tampon ou de la taille de la fenêtre.
- Si vous êtes prêt à prendre une performances, vous pouvez permettre à toute positive de la longueur de la mémoire tampon en utilisant le module opérateur: free = ((head - tail) % buf_len);
InformationsquelleAutor C guy

Juste de mettre déjà la réponse correcte dans le code:

Si vous savez que x est la plus petite valeur, le calcul suivant fonctionne:

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    uint8_t res = y - x;
    printf("Expect 20: %d\n", res); //res is 20

    return 0;
}

Si vous ne savez pas lequel est le plus petit:

int main()
{
    uint8_t x = 0xff;
    uint8_t y = x + 20;
    int8_t res1 = (int8_t)x - y;
    int8_t res2 = (int8_t)y - x;
    printf("Expect -20 and 20: %d and %d\n", res1, res2);

    return 0;
}

Où la différence doit être à l'intérieur de la gamme de uint8_t dans ce cas.

Le code de l'expérience m'a aidé à comprendre la meilleure solution.

InformationsquelleAutor Tarion

1

Le problème devrait être formulée comme suit:

Supposons la position (angle) de deux pointeurs a et b d'une horloge est donné par une u_int8_t. L'ensemble de la circumerence est divisée en 256 valeurs d'une u_int8_t. Comment peut-on la plus petite distance entre les deux pointeur être calculé de manière efficace?

Une solution est:

uint8_t smaller_distance = abs( (int8_t)( a - b ) );

Je présume qu'il n'est rien de plus effient que sinon il n'y aurait quelque chose de plus efficace que l'abs().

InformationsquelleAutor hpc64
0

Faire écho à tout le monde de répondre, si vous vous contentez de soustraire les deux et interpréter le résultat comme unsigned vous serez amende.

Sauf si vous avez un contre-exemple explicite.

Votre exemple de x = 0x2, y= 0x14 ne serait pas le résultat en 0x4, il en résulterait un 0xEE, sauf si vous avez plus de contraintes sur les mathématiques qui sont stipulées.
- ouais c'était un type fixe maintenant.
InformationsquelleAutor MSN

Vous devez vous connecter pour publier un commentaire.