Explication de la moyenne sûre de deux nombres

Lorsque j’ai besoin de faire la moyenne de deux nombres pour un algorithme tel que la recherche binary, je fais toujours quelque chose comme ceci:

int mid = low + ((high - low) / 2); 

J’ai récemment vu une autre façon de le faire dans cet article , mais je ne le comprends pas. Il dit que vous pouvez le faire en Java:

 int mid = (low + high) >>> 1; 

ou ceci en C ++:

 int mid = ((unsigned int)low + (unsigned int)high)) >> 1; 

La version C ++ rend essentiellement les deux opérandes non signés. Ainsi, un décalage entraîne un décalage arithmétique au lieu d’un décalage signé. Je comprends ce que font ces deux morceaux de code, mais comment cela résout-il le problème de débordement? Je pensais que toute la question était que la valeur intermédiaire high + low pourrait déborder?

Modifier:

Oh, duh. Toutes les réponses ne répondaient pas exactement à ma question, mais c’est la réponse de @John Zeringue qui l’a fait cliquer. Je vais essayer d’expliquer ici.

Le problème avec (high + low)/2 en Java n’est pas exactement le dépassement high + low (il déborde car les entiers sont signés, mais tous les bits sont toujours présents et aucune information n’est perdue). Le problème avec la moyenne comme celle-ci est la division. La division fonctionne sur une valeur signée, votre résultat sera donc négatif. Utiliser le décalage au lieu de cela divisera par deux mais considérons les bits au lieu du signe (en le traitant comme non signé).

Considérons donc les octets au lieu des ints. La seule différence est qu’un octet est un entier de 8 bits, alors qu’un int a 32 bits. En Java, les deux sont toujours signés, ce qui signifie que le bit de tête indique s’ils sont positifs (0) ou négatifs (1).

 byte low = Byte.valueOf("01111111", 2); // The maximum byte value byte high = low; // This copies low. byte sum = low + high; // The bit representation of this is 11111110, which, having a // leading 1, is negative. Consider this the worst case // overflow, since low and high can't be any larger. byte mid = sum >>> 1; // This correctly gives us 01111111, fixing the overflow. 

Pour ints, c’est la même chose. En gros, l’essentiel est que l’utilisation d’un décalage binary non signé sur des entiers signés vous permet de tirer parti du bit de premier plan pour gérer les valeurs les plus grandes possibles de bas et haut.

Le code que vous avez vu est cassé: il ne calcule pas correctement la moyenne des nombres négatifs. Si vous n’utilisez que des valeurs non négatives, telles que des index, c’est correct, mais ce n’est pas un remplacement général. Le code que vous avez à l’origine,

 int mid = low + ((high - low) / 2); 

n’est pas à l’abri du débordement non plus, car la différence high - low risque de déborder de la plage des entiers signés. Encore une fois, si vous travaillez uniquement avec des entiers non négatifs, c’est très bien.

En utilisant le fait que A+B = 2*(A&B) + A^B nous pouvons calculer la moyenne de deux entiers sans débordement comme ceci:

 int mid = (high&low) + (high^low)/2; 

Vous pouvez calculer la division par 2 en utilisant un décalage de bit, mais gardez à l’esprit que les deux ne sont pas identiques: la division arrondit à 0 alors que le décalage de bit est toujours arrondi.

 int mid = (high&low) + ((high^low)>>1); 

La version C ++ a un sortingcheur caché: low et high sont int mais ils ne sont jamais négatifs. Lorsque vous les convertissez en unsigned int votre bit de signe devient un bit de précision supplémentaire, qu’un simple ajout ne peut pas dépasser.

Ce n’est pas une très bonne sortingche car les indices de tableaux doivent être unsigned toute façon.

Comme cela a été dit ailleurs, i >> 1 signifie /2 pour les entiers non signés.

La version C ++ ne résout pas le problème de débordement. Cela résout uniquement le problème de la division par 2 réussie en utilisant shift au lieu de / , optimisation que votre compilateur devrait pouvoir créer lui-même s’il s’agissait d’une amélioration des performances.

D’autre part, le dépassement de capacité peut ne pas être un réel problème si vos types d’entiers sont suffisamment grands pour contenir un nombre raisonnable d’indices.

Vous ne pouvez pas utiliser un entier non signé en Java. En cas de dépassement de capacité, les 32 bits les plus bas sont pris en compte et les bits de poids fort sont rejetés. Le décalage droit non signé vous aidera à traiter l’int en tant que non signé. Cependant, en C ++, vous n’aurez pas le débordement.

Vous êtes à l’abri des débordements d’entiers en utilisant la façon dont vous avez dit que vous utilisez déjà, à savoir:

 int mid = low + ((high - low) / 2); 

Laissez le compilateur faire son travail pour l’optimiser s’il le faut.