Comment calculer la valeur absolue entière
Comment calculer la valeur absolue entière sans utiliser la condition if. Je suppose que nous devons utiliser une opération bit à bit. Quelqu'un peut-il aider?
10 réponses
1) Définissez le masque comme décalage droit d'entier de 31 (en supposant que les entiers sont stockés sous forme de valeurs 32 bits à deux compléments et que l'opérateur de décalage droit signe l'extension).
mask = n>>31
2) XOU le masque avec le numéro
mask ^ n
3) soustrayez le masque du résultat de l'étape 2 et renvoyez le résultat.
(mask^n) - mask
Identique aux réponses existantes, mais avec plus d'explications:
Supposons un nombre de complément à deux (comme c'est le cas habituel et vous ne dites pas le contraire) et supposons 32 bits:
Tout d'abord, nous effectuons un décalage arithmétique de 31 bits. Cela se déplace dans tous les 1
S pour un nombre négatif ou tous les 0
S pour un nombre positif (mais notez que le comportement réel de l'opérateur >>
en C ou c++ est implémenté pour les nombres négatifs, mais effectuera généralement une arithmétique shift, mais supposons simplement des instructions de pseudocode ou de matériel réel, car cela ressemble à des devoirs de toute façon):
mask = x >> 31;
Donc, ce que nous obtenons est 111...111
(-1) pour les nombres négatifs et 000...000
(0) pour positifs
Maintenant, nous XOR ceci avec x
, obtenant le comportement D'un NOT for mask=111...111
(négatif) et d'un no-op pour mask=000...000
(positif):
x = x XOR mask;
Et enfin soustraire notre masque, ce qui signifie +1 pour les négatifs et + 0 / no-op pour les positifs:
x = x - mask;
Donc, pour les positifs, nous effectuons un XOR avec 0 et une soustraction de 0 et donc obtenir le même nombre. Et pour les négatifs, nous avons (NOT x) + 1
, qui est exactement -x
lors de l'utilisation de la représentation à deux compléments.
Supposons que {[1] } est de 32 bits.
int my_abs(int x)
{
int y = (x >> 31);
return (x ^ y) - y;
}
On peut également effectuer l'opération ci-dessus que:
return n*(((n>0)<<1)-1);
Où n
est le nombre dont le besoin absolu doit être calculé.
J'ai écrit le mien, avant de découvrir cette question.
Ma réponse est probablement plus lente, mais toujours valide:
int abs_of_x = ((x*(x >> 31)) | ((~x + 1) * ((~x + 1) >> 31)));
En C, vous pouvez utiliser des unions pour effectuer des manipulations de bits sur des doubles. Ce qui suit fonctionnera en C et peut être utilisé pour les entiers, les flottants et les doubles.
/**
* Calculates the absolute value of a double.
* @param x An 8-byte floating-point double
* @return A positive double
* @note Uses bit manipulation and does not care about NaNs
*/
double abs(double x)
{
union{
uint64_t bits;
double dub;
} b;
b.dub = x;
//Sets the sign bit to 0
b.bits &= 0x7FFFFFFFFFFFFFFF;
return b.dub;
}
Notez que cela suppose que les doubles sont de 8 octets.
Quel est le langage de programmation que vous utilisez? En C # vous pouvez utiliser les mathématiques.ABS methos:
int value1 = -1000;
int value2 = 20;
int abs1 = Math.Abs(value1);
int abs2 = Math.Abs(value2);
Pour l'assemblage, le plus efficace serait d'initialiser une valeur à 0, de soustraire l'entier, puis de prendre le max:
pxor mm1, mm1 ; set mm1 to all zeros
psubw mm1, mm0 ; make each mm1 word contain the negative of each mm0 word
pmaxswmm1, mm0 ; mm1 will contain only the positive (larger) values - the absolute value
Dans C # , Vous pouvez implémenter abs () sans utiliser de variables locales:
public static long abs(long d) => (d + (d >>= 63)) ^ d;
public static int abs(int d) => (d + (d >>= 63)) ^ d;
Remarque: en ce qui concerne
0x80000000 (int.MinValue)
et0x8000000000000000 (long.MinValue)
:
Comme avec toutes les autres méthodes bitwise/Non-ramification montrées sur cette page, cela donne le résultat non mathématique uniqueabs(int.MinValue) == int.MinValue
(de même pourlong.MinValue
). Ceux-ci représentent lesseulement cas où la valeur du résultat est négative, c'est-à-dire, où leMSB du résultattwo-complement est1
- et sont également les seuls cas où la valeur d'entrée est retournée inchangée. Je ne crois pas que ce point important ait été mentionné ailleurs sur cette page.
Le code ci-dessus dépend de la valeur de d
utilisé sur la droit côté de la xor étant la valeur de d
mise à jour lors du calcul de gauche côté. De C# programmeurs cela paraît évidente. Ils ont l'habitude de voir du code comme celui-ci parce que . net intègre formellement un modèle de mémoire fort qui garantit strictement la séquence de récupération correcte ici. La raison pour laquelle je mentionne cela est parce que dans C
ou C++
, Il peut être nécessaire d'être plus prudent. Les modèles de mémoire de ce dernier sont considérablement plus permissifs, ce qui peut permettre à certaines optimisations du compilateur d'émettre des récupérations désordonnées. De toute évidence, dans un tel régime, la sensibilité à l'ordre d'extraction représenterait une justesse de danger.
Si vous n'êtes pas autorisé à utiliser le signe moins, vous pouvez faire quelque chose comme ceci:
int absVal(int x) {
return ((x >> 31) + x) ^ (x >> 31);
}