Si je veux arrondir un entier non signé à l'entier pair plus petit ou égal le plus proche, puis-je diviser par 2 puis multiplier par 2 ?

Question

Par exemple :

f(8)=8
f(9)=8

Puis-je faire x = x/2*2; ? Le compilateur ne risque-t-il pas d'optimiser une telle expression ?

Answer 1

Le compilateur est autorisé à effectuer toutes les optimisations qu'il souhaite tant qu'il n'introduit pas d'effets secondaires dans le programme. Dans votre cas, il ne peut pas annuler les '2' car l'expression aurait alors une valeur différente pour les nombres impairs.

x / 2 * 2 est évalué strictement como (x / 2) * 2 et x / 2 est effectuée en arithmétique entière si x est un type intégral.

Il s'agit en fait d'une technique d'arrondi idiomatique.

Answer 2

Puisque vous avez spécifié que les entiers sont non signés, vous pouvez le faire avec un simple masque :

x & (~1u)

Ce qui mettra le LSB à zéro, produisant ainsi le nombre pair immédiat qui n'est pas supérieur à x . C'est-à-dire que si x a un type qui n'est pas plus large qu'un unsigned int .

Vous pouvez bien sûr forcer le 1 pour être du même type qu'un plus grand x comme ceci :

x & ~((x & 1u) | 1u)

Mais à ce stade, vous devriez vraiment considérer cette approche comme un exercice d'obscurcissement, et accepter la réponse de Bathsheba.

---

J'ai bien sûr oublié la bibliothèque standard. Si vous incluez stdint.h (ou cstdint comme il se doit dans le code C++). Vous pouvez laisser l'implémentation s'occuper des détails :

uintmax_t const lsb = 1;
x & ~lsb;

ou

x & ~UINTMAX_C(1)

Answer 3

Le C et le C++ utilisent généralement la règle du "comme si" dans l'optimisation. Le résultat du calcul doit être comme si le compilateur n'a pas optimisé votre code.

Dans ce cas, 9/2*2=8 . Le compilateur peut utiliser n'importe quelle méthode pour obtenir le résultat 8. Cela inclut les bitmasks, les décalages de bits, ou toute autre astuce spécifique au processeur qui produit les mêmes résultats (x86 a un certain nombre d'astuces qui reposent sur le fait qu'il ne fait pas de différence entre les pointeurs et les entiers, contrairement à C et C++).

Answer 4

Vous pouvez écrire x / 2 * 2 et le compilateur produira un code très efficace pour effacer le bit le moins significatif si x a un type non signé.

À l'inverse, vous pourriez écrire :

x = x & ~1;

Ou probablement de façon moins lisible :

x = x & -2;

Ou même

x = (x >> 1) << 1;

Ou ça aussi :

x = x - (x & 1);

Ou cette dernière, suggérée par supercat, qui fonctionne pour les valeurs positives de tous les types et représentations d'entiers :

x = (x | 1) ^ 1;

Toutes les propositions ci-dessus fonctionnent correctement pour tous les types d'entiers non signés sur les architectures à complément à 2. Que le compilateur produise un code optimal est une question de configuration et de qualité d'implémentation.

Notez toutefois que x & (~1u) ne fonctionne pas si le type de x est plus grande que unsigned int . Il s'agit d'un piège contre-intuitif. Si vous insistez pour utiliser une constante non signée, vous devez écrire x & ~(uintmax_t)1 comme même x & ~1ULL échouerait si x a un caractère plus grand que unsigned long long . Pour aggraver les choses, de nombreuses plateformes ont maintenant des types d'entiers plus grands que uintmax_t comme __uint128_t .

Voici un petit repère :

typedef unsigned int T;

T test1(T x) {
    return x / 2 * 2;
}

T test2(T x) {
    return x & ~1;
}

T test3(T x) {
    return x & -2;
}

T test4(T x) {
    return (x >> 1) << 1;
}

T test5(T x) {
    return x - (x & 1);
}

T test6(T x) {  // suggested by supercat
    return (x | 1) ^ 1;
}

T test7(T x) {  // suggested by Mehrdad
    return ~(~x | 1);
}

T test1u(T x) {
    return x & ~1u;
}

Comme suggéré par Ruslan, les tests sur L'explorateur de compilateur de Godbolt montre que pour toutes les alternatives ci-dessus gcc -O1 produit le même code exact pour unsigned int mais en changeant le type T à unsigned long long montre un code différent pour test1u .

Answer 5

Si vos valeurs sont de n'importe quel type non signé comme vous le dites, le plus facile est

x & -2;

Les merveilles de l'arithmétique non signée font que -2 est converti au type de x et a une configuration binaire qui contient tous les uns, sauf le bit le moins significatif qui est 0 .

Contrairement à certaines des autres solutions proposées, cela devrait fonctionner avec n'importe quel type d'entier non signé qui est au moins aussi large que unsigned . (Et vous ne devriez pas faire d'arithmétique avec des types plus étroits, de toute façon).

Bonus supplémentaire, comme l'a fait remarquer supercat, cela n'utilise que la conversion d'un type signé en un type non signé. Ceci est bien défini par la norme comme étant de l'arithmétique modulo. Le résultat est donc toujours UTYPE_MAX-1 para UTYPE le type non signé de x . En particulier, elle est indépendante de la représentation des signes de la plate-forme pour les types signés.