Équivalent Python du code C de Bit Twiddling Hacks?

J’ai une méthode de comptage un peu que j’essaye de faire aussi vite que possible. Je veux essayer l’algorithme ci-dessous de Bit Twiddling Hacks , mais je ne sais pas C. Qu’est-ce que ‘type T’ et quel est l’équivalent python de (T) ~ (T) 0/3?

Une généralisation de la meilleure méthode de comptage de bits à des entiers de largeur de bit jusqu’à 128 (paramétrée par le type T) est la suivante:

v = v - ((v >> 1) & (T)~(T)0/3); // temp v = (v & (T)~(T)0/15*3) + ((v >> 2) & (T)~(T)0/15*3); // temp v = (v + (v >> 4)) & (T)~(T)0/255*15; // temp c = (T)(v * ((T)~(T)0/255)) >> (sizeof(v) - 1) * CHAR_BIT; // count 

T est un type entier, qui, je suppose, n’est pas signé. Comme il s’agit de C, ce sera une largeur fixe, probablement (mais pas nécessairement) l’un des 8, 16, 32, 64 ou 128. Le fragment (T)~(T)0 qui apparaît à plusieurs resockets dans cet exemple de code ne donne que le valeur 2 ** N-1, où N est la largeur du type T. Je suppose que le code peut exiger que N soit un multiple de 8 pour un fonctionnement correct.

Voici une traduction directe du code donné en Python, paramétrée en fonction de N, la largeur de T en bits.

 def count_set_bits(v, N=128): mask = (1 << N) - 1 v = v - ((v >> 1) & mask//3) v = (v & mask//15*3) + ((v >> 2) & mask//15*3) v = (v + (v >> 4)) & mask//255*15 return (mask & v * (mask//255)) >> (N//8 - 1) * 8 

Mises en garde:

(1) Ce qui précède ne fonctionne que pour les nombres inférieurs à 2 ** 128. Vous pourriez cependant pouvoir le généraliser pour des nombres plus importants.

(2) Il y a des inefficacités évidentes: par exemple, ‘masque // 15’ est calculé deux fois. Cela n’a pas d’importance pour C, bien sûr, car le compilateur assurera presque certainement la division au moment de la compilation plutôt que de l’exécution, mais l’optimiseur de perforation de Python n’est peut-être pas aussi intelligent.

(3) La méthode C la plus rapide peut ne pas être traduite par la méthode Python la plus rapide. Pour la vitesse Python, vous devriez probablement rechercher un algorithme qui minimise le nombre d’opérations au niveau des bits Python. Comme l’a dit Alexander Gessler: profil!

Ce que vous avez copié est un modèle pour générer du code. Ce n’est pas une bonne idée de translittérer ce modèle dans une autre langue et de s’attendre à ce qu’il soit rapide. Développons le modèle.

(T) ~ (T) 0 signifie “autant de bits que nécessaire dans le type T”. L’algorithme a besoin de 4 masques que nous allons calculer pour les différentes tailles de T qui pourraient nous intéresser.

 >>> for N in (8, 16, 32, 64, 128): ... all_ones = (1 << N) - 1 ... constants = ' '.join([hex(x) for x in [ ... all_ones // 3, ... all_ones // 15 * 3, ... all_ones // 255 * 15, ... all_ones // 255, ... ]]) ... print N, constants ... 8 0x55 0x33 0xf 0x1 16 0x5555 0x3333 0xf0f 0x101 32 0x55555555L 0x33333333L 0xf0f0f0fL 0x1010101L 64 0x5555555555555555L 0x3333333333333333L 0xf0f0f0f0f0f0f0fL 0x101010101010101L 128 0x55555555555555555555555555555555L 0x33333333333333333333333333333333L 0xf0f0f0f0f0f0f0f0f0f0f0f0f0f0f0fL 0x1010101010101010101010101010101L >>> 

Vous remarquerez que les masques générés pour le cas 32 bits correspondent à ceux du code C 32 bits codé en dur. Détail de la mise en œuvre: perd le suffixe L des masques 32 bits (Python 2.x) et perd tous les suffixes L pour Python 3.x.

Comme vous pouvez le voir, tout le gabarit et (T) ~ (T) 0 câpres n’est qu’un sophisme obscurcissant. En termes simples, pour un type d’octet k, vous avez besoin de 4 masques:

 k bytes each 0x55 k bytes each 0x33 k bytes each 0x0f k bytes each 0x01 

et le décalage final est simplement N-8 (c’est-à-dire 8 * (k-1)) bits. De plus: je doute que le code de modèle fonctionne réellement sur une machine dont CHAR_BIT n’était pas égal à 8, mais il n’y en a pas beaucoup de ces jours-ci.

Mise à jour: il existe un autre point qui affecte l’exactitude et la vitesse lors de la translittération de tels algorithmes de C en Python. Les algorithmes C supposent souvent des entiers non signés. En C, les opérations sur les entiers non signés fonctionnent silencieusement modulo 2 ** N. En d’autres termes, seuls les N bits les moins significatifs sont conservés. Pas d’exception de débordement. De nombreux algorithmes de tournage de bits reposent sur cela. Cependant (a) les int Python et long sont signés (b), vieux Python 2.X lèvera une exception, les Python 2.X récents feront la promotion silencieuse de int en long et Python 3.x int == long Python 2.x

Le problème de correction nécessite généralement d’ register &= all_ones au moins une fois le code register &= all_ones dans le code Python. Une parsing minutieuse est souvent nécessaire pour déterminer le masquage correct minimal.

Travailler long au lieu de int ne fait pas beaucoup pour l’efficacité. Vous remarquerez que l’algorithme pour 32 bits renverra une réponse long même à partir de l’entrée 0 , car la valeur all_ones 32 bits est long .