Étant donné un nombre entier, comment puis-je trouver la puissance suivante la plus grande des deux en utilisant le bit-twiddling?

Question

Si j'ai un nombre entier n , comment puis-je trouver le prochain nombre k > n tel que k = 2^i , avec quelques i élément de n par décalage binaire ou logique.

Exemple: si j'ai n = 123 , comment puis-je trouver k = 128 , qui est une puissance de deux, et non 124 qui n'est divisible que par deux. Cela devrait être simple, mais cela m'échappe.

Answer 1

Pour les nombres entiers de 32 bits, c'est une simple route:

unsigned int n;

n--;
n |= n >> 1;   // Divide by 2^k for consecutive doublings of k up to 32,
n |= n >> 2;   // and then or the results.
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n++;           // The result is a number of 1 bits equal to the number
               // of bits in the original number, plus 1. That's the
               // next highest power of 2.

Voici un exemple plus concret. Prenons le numéro 221, qui est 11011101 en binaire:

n--;           // 1101 1101 --> 1101 1100
n |= n >> 1;   // 1101 1101 | 0110 1110 = 1111 1111
n |= n >> 2;   // ...
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;  // 1111 1111 | 1111 1111 = 1111 1111
n++;           // 1111 1111 --> 1 0000 0000

Il y a un peu dans le neuvième position, ce qui représente 2^8, ou 256, qui est en effet la deuxième plus grande puissance de 2. Chacun des quarts de travail chevauche toutes les bits à 1 dans le nombre avec une partie de la auparavant intactes les zéros, finit par produire un certain nombre de bits à 1 égal au nombre de bits dans le numéro d'origine. L'ajout d'une valeur produit une nouvelle puissance de 2.

Un autre exemple, nous allons utiliser 131, qui est 10000011 en binaire:

n--;           // 1000 0011 --> 1000 0010
n |= n >> 1;   // 1000 0010 | 0100 0001 = 1100 0011
n |= n >> 2;   // 1100 0011 | 0011 0000 = 1111 0011
n |= n >> 4;   // 1111 0011 | 0000 1111 = 1111 1111
n |= n >> 8;   // ... (At this point all bits are 1, so further bitwise-or
n |= n >> 16;  //      operations produce no effect.)
n++;           // 1111 1111 --> 1 0000 0000

Et en effet, 256 est la prochaine plus haute puissance de 2 131.

Si le nombre de bits utilisés pour représenter l'entier est lui-même une puissance de 2, vous pouvez continuer à étendre cette technique de manière efficace et à l'infini (par exemple, ajouter un n >> 32 ligne pour les entiers 64 bits).

Answer 2

Il est en fait un assemblage de solution (depuis le 80386 jeu d'instructions).

Vous pouvez utiliser le BSR (Bit de Balayage Inverse) instructions pour numériser pour le bit le plus significatif dans votre entier.

bsr scanne les bits, de départ à la most significant bit, dans le doubleword opérande ou le deuxième mot. Si les bits sont tous nuls, ZF est effacé. Sinon, ZF est définie et l' l'index du bit du premier ensemble de bits trouvé, lors de la numérisation dans le sens inverse direction, est chargé dans la registre de destination

(Extrait de: http://dlc.sun.com/pdf/802-1948/802-1948.pdf)

Et de inc le résultat avec 1.

donc:

bsr ecx, eax  //eax = number
jz  @zero
mov eax, 2    // result set the second bit (instead of a inc ecx)
shl eax, ecx  // and move it ecx times to the left
ret           // result is in eax

@zero:
xor eax, eax
ret

Answer 3

Une manière plus mathématique, sans boucles:

 public static int ByLogs(int n)
{
    double y = Math.Floor(Math.Log(n, 2));

    return (int)Math.Pow(2, y + 1);
}
 

Answer 4

Voici une réponse logique:

 function getK(int n)
{
  int k = 1;
  while (k < n)
    k *= 2;
  return k;
}
 

Answer 5

Voici John Feminella de réponse mis en œuvre une boucle de sorte qu'il peut gérer Python entiers longs:

def next_power_of_2(n):
    """
    Return next power of 2 greater than or equal to n
    """
    n -= 1 # greater than OR EQUAL TO n
    shift = 1
    while (n+1) & n: # n+1 is not a power of 2 yet
        n |= n >> shift
        shift *= 2
    return n + 1

Il renvoie également plus rapide si n est déjà une puissance de 2.

Pour Python >2.7, c'est plus simple et plus rapide pour la plupart N:

def next_power_of_2(n):
    """
    Return next power of 2 greater than or equal to n
    """
    return 2**(n-1).bit_length()