Poids Hamming écrit uniquement dans les opérations binarys?

J’ai besoin d’écrire une expression de Hamming d’un octet en termes d’opérations binarys uniquement (&, ^, >>); sans boucle, juste une formule.

Je sais qu’il existe de nombreux algorithmes permettant de calculer le poids de Hamming, mais ils utilisent tous des opérations arithmétiques ou des boucles.

Si nous prenons un algorithme de http://en.wikipedia.org/wiki/Hamming_weight , alors la première sum D = B + C peut être écrite comme D = B ^ C ^ (B & C << 1), mais deux sommes sont plus compliqués.

Est-ce que quelqu’un a un indice?

MISE À JOUR: Merci pour l’aide les gars. En fait, j’avais besoin de quelque chose comme:

int popcount_1(unsigned char in){ unsigned char m1 = 0x55; unsigned char m2 = 0x33; unsigned char m4 = 0x0f; unsigned char B,C = 0; unsigned char x = in; x = (x & (x << 1) & (m1 <> 1))); B = x & m2; C = (x >> 2) & m2; x = B ^ C ^ ((B & C) <> 4) & m4); C = (x & ((x >> 4) & m4)) << 1; x = B ^ C ^ ((B & C) << 1); return x; } 

Ce code se traduira par Hamming poids de la variable en . Il ne contient pas d’instructions de comparaison +, – ou, et il peut fonctionner sur des microcontrôleurs 8 bits. Néanmoins, cela prend plus d’opérations que la plupart des autres solutions. Maintenant, j’essaie de le simplifier.

UPDATE2: Une autre solution, basée sur des registres 64 bits, est proposée par @Evgeny Kluev

Je ne sais pas si c’est ce que vous recherchez, mais voici une formule utilisant uniquement des décalages et des bits au niveau des bits et:

 int weight(unsigned char x) { return ((0x876543210 >> (((0x4332322132212110 >> ((x & 0xF) << 2)) & 0xF) << 2)) >> ((0x4332322132212110 >> (((x & 0xF0) >> 2)) & 0xF) << 2)) & 0xf; } 

Ici, l'opération shift est utilisée à deux resockets en remplacement de l'indexation de tableaux (pour trouver des poids de compression 4 bits). Et une opération supplémentaire utilise l’indexation sur tableau pour effectuer l’ajout.

Je pense que le mieux que vous puissiez faire est O (log n). Voici le code (en Go) pour le nombre de pop-count d’un entier 32 bits. Étendre cela à 64 bits devrait être évident si vous en avez besoin, espérons que les commentaires expliquent clairement ce qui se passe réellement:

 func popCount(n uint32) int { // each bit in n is a one-bit integer that indicates how many bits are set // in that bit. n = ((n & 0xAAAAAAAA) >> 1) + (n & 0x55555555) // Now every two bits are a two bit integer that indicate how many bits were // set in those two bits in the original number n = ((n & 0xCCCCCCCC) >> 2) + (n & 0x33333333) // Now we're at 4 bits n = ((n & 0xF0F0F0F0) >> 4) + (n & 0x0F0F0F0F) // 8 bits n = ((n & 0xFF00FF00) >> 8) + (n & 0x00FF00FF) // 16 bits n = ((n & 0xFFFF0000) >> 16) + (n & 0x0000FFFF) // kaboom - 32 bits return int(n) }