Formule de la valeur moyenne d'un nombre entier sûr

Question

Je cherche une formule efficace fonctionnant en Java qui calcule l'expression suivante :

(low + high) / 2

qui est utilisé pour la recherche binaire. Jusqu'à présent, j'ai utilisé "low + (high - low) / 2" et "high - (high - low) / 2". pour éviter les débordements et les sous-débordements dans certains cas, mais pas dans les deux. Je cherche maintenant un moyen efficace de le faire, pour n'importe quel entier (en supposant que les entiers vont de -MAX_INT - 1 à MAX_INT).

UPDATE : En combinant les réponses de Jander et Peter G. et en expérimentant un peu, j'ai obtenu les formules suivantes pour l'élément de valeur moyenne et ses voisins immédiats :

Point médian le plus bas (égal à floor((low + high)/2) (par exemple, [2 3] -> 2, [2 4] -> 3, [-3 -2] -> -3).

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

Point le plus haut-moyen (égal à ceil((low + high)/2) par exemple [2 3] -> 3, [2 4] -> 3, [-3 -2] -> -2)

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

Avant le point médian (égal à floor((low + high - 1)/2)) (par exemple, [2 3] -> 2, [2 4] -> 2, [-7 -3] -> -6)

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

Après le point médian (égal à ceil((low + high + 1)/2)) par exemple [2 3] -> 3, [2 4] -> 4, [-7 -3] -> -4)

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

Ou encore, sans le signe et (&) et le signe ou (|), un code légèrement plus lent ( x >> 1 peut être remplacé par floor(x / 2) pour obtenir des formules sans opérateur binaire) :

Point médian le plus à gauche

halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);

Point médian le plus à droite

low++
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);

Avant le point médian

high--;
halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1);

Après le point médian

halfLow = (low >> 1), halfHigh = (high >> 1);
mid = halfLow + halfHigh + ((low-2*halfLow + high-2*halfHigh) >> 1) + 1;

Note : ce qui précède >> est considéré comme un décalage signé.

Answer 1

De http://aggregate.org/MAGIC/#Average%20of%20Integers :

(low & high) + ((low ^ high) / 2)

est une moyenne sans débordement de deux entiers non signés.

Maintenant, cette astuce ne fonctionne que sur les entiers non signés. Mais parce que ((a+x) + (b+x))/2 = (a+b)/2 + x Si vous avez des entiers non signés avec la même taille de bit que vos entiers signés, vous pouvez vous arranger comme suit :

unsigned int u_low  = low + MAX_INT + 1;
unsigned int u_high = high + MAX_INT + 1;
unsigned int u_avg  = (u_low & u_high) + (u_low ^ u_high)/2;
int avg = u_avg - MAX_INT - 1;

---

UPDATE : En y réfléchissant, cela fonctionnera même si vous n'avez pas d'entiers signés. Par bit, les entiers signés et non signés sont équivalents pour l'addition, la soustraction et les opérations booléennes. Il suffit donc de s'assurer que divide se comporte comme une division non signée, ce que nous pouvons faire en utilisant un décalage et en masquant le bit supérieur.

low += MAX+INT + 1;
high += MAX_INT + 1;
avg = (low & high) + (((low ^ high) >> 1) & MAX_INT);
avg -= MAX_INT + 1;

(Notez que si vous utilisez Java, vous pouvez utiliser un décalage non signé, ... >>> 1 au lieu de (... >> 1) & MAX_INT .)

CEPENDANT, Je suis tombé sur une solution encore plus simple, mais je n'ai pas encore compris comment elle fonctionne. Il n'y a pas besoin d'ajuster les nombres par MAX_INT ou d'utiliser des variables non signées ou quoi que ce soit. C'est tout simplement :

avg = (low & high) + ((low ^ high) >> 1);

Testé avec toutes les combinaisons d'entiers signés de 16 bits low y high dans l'intervalle -32768..32767, mais pas encore prouvé catégoriquement (par moi en tout cas).

Answer 2

int half_low = low/2;
int lsb_low = low - 2*half_low;
int half_high = high/2;
int lsb_high = high - 2*half_high;
int mean = half_low + half_high + (lsb_low + lsb_high)/2;

Answer 3

En supposant que high >= low une variante de votre approche initiale devrait également fonctionner :

low + ((high - low) >>> 1)

donde >>> est un décalage non signé (comme en Java).

L'idée est que high - low ne déborde jamais si le résultat est interprété comme un entier non signé, de sorte que le décalage non signé effectue correctement la division par 2 et que la formule calcule la valeur moyenne.

Answer 4

Notez qu'aucune de vos idées ne fonctionne pour low=-MAX_INT-1, high=MAX_INT . Le mieux que je puisse faire est quelque chose comme low/2 + high/2 + ((low & 1) + (high & 1))/2 .