Utilisation de la manipulation de bits pour calculer la valeur moyenne de deux nombres?

Question

Je trouve ce code:

int mid = (l & r) + ((l^r) >> 1) 

qui est le même que mid=(l+r)/2

mais je ne peux pas comprendre pourquoi?

Une aide? Merci!

Answer 1

Ce n'est pas tout à fait pareil, le point n'est pas le même. C'est principalement le même, mais sans problème de débordement: si vous entrez deux nombres positifs, le résultat ne sera jamais négatif. Ce n'est pas vrai de mid = (l + r)/2, si vous avez par exemple l = 0x7fffffff, r = 1 alors le vrai milieu est 0x40000000 mais le calcul du point milieu naïf dit 0xc0000000, un grand nombre négatif.

L'addition se décompose en:

x + y = (x^y) + ((x & y) << 1) 

C'est juste un simple « calculer la somme par chiffres, puis appliquer la porte séparément » décomposition. Déplacez ensuite le tout droit en 1 tout en rétablissant les bits qui « est tombé à la fin » par tout simplement pas déplacer à gauche pour commencer et déplacer l'autre chose à droite,

x + y = ((x^y) >> 1) + (x & y) 

Ce qui est que le calcul milieu. Notez qu'il arrondit vers le bas, pas vers zéro, ce qui compte pour les résultats négatifs. Je n'appellerais pas le résultat mauvais, il est encore à mi-chemin entre les points de terminaison, mais il ne correspond pas au résultat d'une division signée normale par 2 (arrondit généralement vers zéro, bien que les opinions divergent).

Vous pouvez changer de travailler pour tous les non signés entiers en utilisant un décalage droit non signé:

// unsigned midpoint without wrapping/overflow 
int mid = (l & r) + ((l^r) >>> 1); 

étant bien sûr le milieu non signé, les entrées négatives sont implicitement considérés comme des nombres positifs très importants, c'est la point.

Si vous travaillez avec des chiffres signés mais non-négatif (comme cela est habituellement le cas pour le calcul milieu), vous pouvez utiliser le nettement plus simple

int mid = (x + y) >>> 1