moyen le plus rapide de déterminer si un bit est défini dans un type de données entier

J’ai une méthode qui calcule une valeur de hachage selon un algorithme spécifique.

uint8_t cal_hash(uint64_t _in_data) { uint8_t hash; // algorithm // bit at hash[0] = XOR of some specific bits in _in_data // repeat above statement for other indexed bits of hash return hash; } 

Je veux savoir quel pourrait être le moyen le plus efficace d’accéder et de définir les bits correspondants dans un type de données entier. J’ai déjà essayé des choses comme

 (((x) & (1<<(n)))?1:0) 

pour déterminer si un bit est 1 ou 0 à n’importe quel index. Quelque chose de mieux que ça?

    Je pense que ceci est une question de type vitesse / mémoire. (Mise à jour avec la suggestion de MrSmith42):

    Si vous voulez vraiment de la vitesse, je définirais un masque pour chaque bit et le comparer. Peut-être quelque chose comme:

     const uint8_t BitMask[] = { 0x1, 0x2, 0x4, 0x8, 0x10, 0x20, 0x40, 0x80 }; /* Find out if LSB is set */ if( hash & BitMask[0] ) { ... } 

    Le problème avec les décalages est qu’il utilise une instruction par décalage alors qu’un masque fixe n’aura qu’un seul access mémoire avant la comparaison.

    Votre première préoccupation devrait être d’avoir une version correcte et portable. Les compilateurs optimiseront alors ces opérations de manière très intelligente.

    Veillez à ce que le masque que vous utilisez corresponde au type de données que vous testez. Utiliser un int ou unsigned peut ne pas suffire car vous êtes intéressé par les bits d’un uint64_t et que le fait de décaler plus que de bits est un comportement indéfini.

    Dans votre cas, vous utiliseriez probablement quelque chose comme

     (UINT64_C(1) << (n)) 

    pour le masque. Si vous voulez faire cela de manière plus générique, vous devez obtenir un 1 de votre type de base avec quelque chose comme

     (1 ? 1U : (X)) 

    ensemble dans une macro

     #define MASK(X, N) ((1 ? 1U : (X)) << (N)) 

    et puis le test pourrait ressembler à

     #define BIT(X, N) !!((X) & MASK(X, N)) 

    Pour trouver un paramètre rapide, essayez ceci:

     int oneBit = x & ~(x-1); 

    Après cela, oneBit aura UNIQUEMENT le bit le plus bas de l’ensemble X.
    (par exemple, si x était 1011 0100 , oneBit sera 0000 0100 , par exemple, le bit le plus bas)

    Après cela, vous pouvez désactiver le bit le plus bas avec:

     x &= x-1; 

    (par exemple: si x était 1011 0100 , le nouveau x devrait être 1011 0000 )

    Ensuite, vous pouvez répéter la première opération pour rechercher le prochain bit le plus bas défini.

    Cela a le grand avantage de ne pas passer du temps à “tester” un peu pour savoir que c’est zéro.
    Il vous amène directement aux bits définis et ignore les bits nuls.

    Voici un exemple de code qui le montre en action:

     int main(void) { int x = 180; // 1011 0100 while (x) { printf("Low Bit is: %d\n", x & ~(x-1)); x &= (x-1); } } 

    Sortie:

     Low Bit is: 4 // eg. 0000 0100 Low Bit is: 16 // eg. 0001 0000 Low Bit is: 32 // eg. 0010 0000 Low Bit is: 128 // eg. 1000 0000