Quelle est la méthode la plus rapide pour calculer un nombre ayant seulement un ensemble de bits qui est le chiffre le plus significatif dans un autre nombre?

Question

Doublons possibles:
Previous power of 2
Getting the Leftmost Bit

Ce que je veux est, supposons qu'il y ait un certain nombre 5 dire 101. Ma réponse devrait être 100. Pour savoir 91001, la réponse devrait être 1000

Answer 1

int input = 5; 
std::size_t numBits = 0; 
while(input) 
{ 
    input >>= 1; 
    numBits++; 
} 
int output = 1 << (numBits-1); 

Answer 2

De Hacker's Delight, une solution agréable sans agence:

uint32_t flp2 (uint32_t x) 
{ 
    x = x | (x >> 1); 
    x = x | (x >> 2); 
    x = x | (x >> 4); 
    x = x | (x >> 8); 
    x = x | (x >> 16); 
    return x - (x >> 1); 
} 

Cela prend généralement 12 instructions. Vous pouvez le faire en moins si votre CPU a une instruction "count leading zero".

Answer 3

Vous ne pouvez pas demander la séquence le plus rapide sans donner contraintes sur la machine sur laquelle cela doit fonctionner. Par exemple, certaines machines supportent une instruction appelée "count leading zeroes" ou ont des moyens de l'émuler très rapidement. Si vous pouvez accéder à cette instruction (par exemple avec gcc), vous pouvez écrire:

#include <limits.h> 
#include <stdint.h> 
uint32_t f(uint32_t x) 
{ 
    return ((uint64_t)1)<<(32-__builtin_clz(x)-1); 
} 
int main() 
{ 
    printf("=>%d\n",f(5)); 
    printf("=>%d\n",f(9)); 
} 

f (x) retourne ce que vous voulez (le moins y avec x> = y et y = 2 ** n). Le compilateur va maintenant générer la séquence de code optimale pour la machine cible. Par exemple, lors de la compilation pour une architecture x86_64 par défaut, f() ressemble à ceci:

bsrl %edi, %edi 
    movl $31, %ecx 
    movl $1, %eax 
    xorl $31, %edi 
    subl %edi, %ecx 
    salq %cl, %rax 
    ret 

Vous voyez, pas de boucles ici! 7 instructions, pas de branches.

Mais si je dis à mon compilateur (gcc-4.5) pour optimiser la machine que je utilise en ce moment (AMD Phenom II), alors ce sort pour f():

bsrl %edi, %ecx 
    movl $1, %eax 
    salq %cl, %rax 
    ret 

Cette est probablement le moyen le plus rapide d'aller chercher cette machine.

EDIT: f (0) aurait abouti à UB, j'ai résolu cela (et l'ensemble). En outre, uint32_t signifie que je peux écrire 32 sans se sentir coupable :-)

Answer 4

Ceci est une tâche liée au comptage des bits. Check this out.

Utilisation du 2a (qui est mon préféré des algorithmes, pas le plus rapide), on peut venir à ceci:

int highest_bit_mask (unsigned int n) { 
    while (n) { 
     if (n & (n-1)) { 
     n &= (n-1) ; 
     } else { 
     return n; 
     } 
    } 
    return 0; 
} 

La magie de n &= (n-1); est qu'il supprime de n bit le moins significatif. (Le corollaire: n & (n-1) est faux seulement quand n a exactement un bit défini.) La complexité de l'algorithme dépend du nombre de bits mis dans l'entrée.

Vérifiez le lien quand même. C'est une lecture très amusante et éclairante qui pourrait vous donner plus d'idées.