Je voudrais calculer la différence absolue de deux entiers. Naïvement, ce n'est que pour les entiers non signés, pour les entiers signés, Comment ces problèmes peuvent-ils être traités de manière efficace?
Je voudrais un algorithme (ou une paire d'algorithmes) qui fonctionne pour les entiers signés et non signés, et ne repose pas sur la mise en oeuvre des valeurs à une taille entière plus grande.
(Aussi, pour clarifier: ma question n'est pas comment écrire cela dans le code, mais que je devrais écrire exactement afin de garantir la sécurité-sécurité. Informatique ABS (A - B) . Cependant, cela a quelques problèmes, selon que les entiers soient signés ou non signés:
a - b sera un grand nombre positif si B est supérieur à A et de l'absolu Le fonctionnement de la valeur ne résout pas cela.
A - B peut être en dehors de la plage de valeurs pouvant être représentée sous forme d'entier signé, conduisant ainsi à un comportement non défini. (Évidemment, cela signifie que le résultat devra être un entier non signé.)
ABS (A - B) Une valeur signée puis une valeur non signée ne fonctionne pas, car un débordement entier signé est typiquement une opération non définie, au moins en c.)
4 Réponses :
édité pour utiliser le correctif de Brook Moses pour des types signés et Kerrek SB's make_unsigned pour permettre Utilisation de modèle.
Premièrement, vous pouvez avoir ce qui suit pour make_unsigned, ou vous pouvez utiliser std :: make_unsigned, TR1 :: make_unsigned ou boost :: make_unsigned. p>
template <typename T>
typename make_unsigned<T>::type absdiff(T a, T b)
{
typedef typename make_unsigned<T>::type UT;
if (a > b)
return static_cast<UT>(a) - static_cast<UT>(b);
else
return static_cast<UT>(b) - static_cast<UT>(a);
}
À droite, mais comment s'adresse-t-il la possibilité de débordement entier signé lorsque, disons, A est int_max et B est int_min?
Ce n'est pas une différence absolue et est toujours vulnérable au débordement des entiers signés.
D'accord, j'ai mal compris la question. Dans ce cas, nous voudrions toujours retourner un type non signé?
@JackToole: Oui, laissez-moi essayer de clarifier la question. Vous avez raison que nous devons toujours retourner un type non signé.
(Je travaille tout seul après avoir posé la question - je pensais que ce serait plus difficile, et je souhaitais toujours les autres réponses s'il y en a de meilleurs!)
La solution pour les entiers non signés est relativement simple (comme décrit dans la réponse de Jack Toole) et fonctionne en déplaçant le conditionnel (implicite) à l'extérieur de la soustraction de sorte que nous soustrayons toujours le nombre plus petit de la plus grande, et ne comparez pas une valeur potentiellement enveloppée à zéro: P>
if (a > b) return (unsigned) a - (unsigned) b; else return (unsigned) b - (unsigned) a;
Voici une idée: si nous sommes non signés, nous prenons juste la bonne différence. Si nous sommes signés, nous renvoyons le type non signé correspondant:
#include <type_traits>
template <typename T, bool> struct absdiff_aux;
template <typename T> struct absdiff_aux<T, true>
{
static T absdiff(T a, T b) { return a < b ? b - a : a - b; }
};
template <typename T> struct absdiff_aux<T, false>
{
typedef typename std::make_unsigned<T>::type UT;
static UT absdiff(T a, T b)
{
if ((a > 0 && b > 0) || (a <= 0 && b <= 0))
return { a < b ? b - a : a - b; }
if (b > 0)
{
UT d = -a;
return UT(b) + d
}
else
{
UT d = -b;
return UT(a) + d;
}
}
};
template <typename T> typename std::make_unsigned<T>::type absdiff(T a, T b)
{
return absdiff_aux<T, std::is_signed<T>::value>::absdiff(a, b);
}
+1, je cherchais un moyen de faire des choses non signées avec des modèles, mais malheureusement, je n'ai malheureusement pas été en mesure de passer à C ++ 11 encore. Il pourrait y avoir un moyen de le faire sans autant de Sfinae, en soustrayant STD :: numeric_limits
@JackToole: N'abandonnez pas de croire en vous-même! Juste parce que make_signed est qu'une partie de la nouvelle norme ne signifie pas que vous ne pouvez pas écrire quelque chose comme vous comme vous-même. (Ou tricher et prendre boost :: make_signed .) :-)
Pédantiquement, ce premier si dans le cas signé doit vérifier a> = 0 && b> = 0 || A <0 && B <0 Pour mener des zéros avec les numéros positifs - sinon, vous pouvez obtenir un débordement dans le cas où l'un est int_min et l'autre est 0, car 0 - INT_MIN est int_max + 1 . (Ce genre de choses est délicat!) Sinon, cela me convient: bien que cela prend au moins trois contenus et deux branches pour chaque valeur comparée, ce qui semble quelque peu inefficace.
@Brooksmoses: Il est tout à fait possible que j'ai manqué le cas spécial INT_MIN, alors n'hésitez pas à ajouter cela. Traiter avec des numéros signés est DigSy, donc si vous avez des idées pour éliminer les licenciements, disons. Je viens de faire cela sur place, visant que le plus gros problème de la différence soit trop grande pour un type signé.
@Kerreksb Yep :). J'ai triché et trouvé une implémentation, mais il n'est pas difficile d'écrire. Juste difficile à penser. Les modèles sont géniaux et peuvent faire toutes sortes de trucs soignés, mais j'ai toujours besoin de plus de pratique pour savoir comment faire les astuces avancées.
code: sortie:
Pourriez-vous expliquer ce que la ligne diff = 1 + ~ diff dans la fonction signée fait? Cela semble être la pièce clé.
Inverser tous les morceaux d'un entier de complément d'un groupe de 2, puis en ajoutant 1 annule le nombre, changeant positif à négatif et inversement. Exemples (avec INTS non signé 16 bits): 1 + ~ 0 = 1 + 0xFFFF = 0, 1 + ~ 1 = 1 + 0xFFFE = 0xFFFF (= - 1), 1 + ~ 0xFFFF (= - 1) = 1 + 0 = 1, 1 + ~ 0x8000 (= - 0x8000) = 1 + 0x7FFF = 0x8000 (= - 0x8000). Fondamentalement, mes fonctions effectuent d'abord la soustraction complète des numéros de 2. La différence est également le complément de 2 (mais il peut manquer un bit de signalisation supplémentaire, par exemple lorsque vous l'obtenez égal à 0x80 ... 00 dans Absdiiffsigned ()). Vous obtenez le morceau de signe de (A
Ce n'est pas comme si quelqu'un utilise sérieusement la non-2's-complément. Peut aussi bien utiliser unaire moins
@HAROLD: La raison pour laquelle j'ai utilisé
@HAROLD: La norme de 2003 C ++ dit en 5.3.1C7:
Bon à savoir, merci d'avoir regardé ça - on dirait que ça va être en sécurité en C ++ au moins
@HAROLD: Et en C aussi, voir Cette question .
1 + ~ au lieu de - est que certains compilateurs n'aiment pas voir un accord moins devant des valeurs non signées. Comme je me souviens, MSVC ++ avec un niveau d'avertissement défini sur 4 le ferait. En outre, je ne suis pas tout à fait sûr d'un comportement non défini ici, bien que mathématiquement -x devrait être équivalent à 0-x , mais l'arithmétique de C n'est pas votre arithmétique normale .. .
Le négatif d'une quantité non signée est calculé en soustrayant sa valeur de 2 ^ N, où N est le nombre de bits dans l'opérande promu. Le 1999 c standard n'inclut pas une énoncé explicite et ne définit pas clairement le comportement unitaire ni dans 6.5.3.3c1,3 ni en 6.5c4 ( certains opérateurs (l'opérateur unitaire ~ et les opérateurs binaires << , >>, &, ^, et |, ...) ... Valeurs de retour qui dépendent des représentations internes des entiers et ont des aspects définis par la mise en œuvre et non définis pour les types signés. ).