Explication pour le calcul de la puissance la plus proche de deux supérieure à l'argument en utilisant le bit twiddling

Question

Il s'agit d'une fonction bien connue pour calculer la puissance la plus proche suivante de deux pour les arguments positifs. Cependant, je n'ai pas beaucoup d'expérience pour triturer la logique/théorie derrière cela. Voulez-vous expliquer pourquoi et comment cela fonctionne? En particulier, le choix de 1,2,4,8,16 pour le déplacement et si la gamme de l'argument était plus grande ce qui serait utilisé, par exemple, pour un long? Pourquoi le décalage logique au lieu de l'arithmétique et, finalement, qu'est-ce que l'argument décalé ORing accomplit?

static int lowestPowerOfTwoGreaterThan(int arg) { 
    arg |= (arg >>> 1); 
    arg |= (arg >>> 2); 
    arg |= (arg >>> 4); 
    arg |= (arg >>> 8); 
    arg |= (arg >>> 16); 
    return ++arg; 
} 

Answer 1

C'est vraiment simple si vous suivez les changements à la valeur. Une puissance de deux a un seul bit de réglage, par exemple 100, 10000000, 10000000000, ce qui signifie qu'une puissance de deux, moins un, est une séquence de uns, par ex. 10000 - 1 = 1111. Donc, ce que la fonction fait est de changer n'importe quel nombre en une séquence de uns (sans déplacer son 1 bit le plus élevé), puis en ajouter un, par ex. il change 10000001000111001 (66105) en 11111111111111111 (131071) et en ajoute un pour créer 100000000000000000 (131072). Tout d'abord, il ORs la valeur par lui-même décalé de 1 bit vers la droite. Cela a pour effet d'allonger toutes les exécutions de 1 dans la valeur.

10000001000111001 
OR 01000000100011100 
    ================= 
    11000001100111101 

Vous remarquerez maintenant que chaque série de zéros est précédée d'au moins deux petits, donc au lieu de déplacer par un nouveau, nous pouvons accélérer le processus en déplaçant par deux bits au lieu d'un.

11000001100111101 
OR 00110000011001111 
    ================= 
    11110001111111111 

Maintenant, est précédé chaque série de zéros par au moins quatre ceux, donc nous passons par quatre cette fois-ci, et ou les valeurs à nouveau.

11110001111111111 
OR 00001111000111111 
    ================= 
    11111111111111111 

La répétition de cette logique, suivant la distance de décalage sera de 8, puis 16 (arrêt ici pour obtenir des valeurs 32 bits), puis 32 (arrêt ici pour les valeurs de 64 bits). Pour cet exemple, le résultat reste inchangé pour les autres décalages puisqu'il s'agit déjà d'une séquence de uns.

Cette méthode modifie n'importe quel nombre binaire en une séquence de uns. En ajoutant 1 à cela, comme indiqué précédemment, produit la prochaine plus grande puissance de deux.