Peu tourner les Hacks

Original: http://graphics.stanford.edu/~seander/bithacks.html


Par Sean Eron Anderson
Individuellement, les extraits de code ici sont du domaine public (sauf indication contraire), n’hésitez pas à les utiliser, mais s’il vous plaît. La collection globale et les descriptions sont © 1997-2005 Sean Eron Anderson. Le code et les descriptions sont distribuées dans l’espoir qu’ils seront utiles, mais sans aucune garantie et sans même la garantie implicite de qualité marchande ou d’ADEQUATION a un usage particulier. À compter du 5 mai 2005, tout le code a été testé à fond. Des milliers de personnes ont lu. En outre, professeur Randal Bryant, le doyen d’informatique à l’Université Carnegie Mellon, a personnellement testé presque tout avec son système de vérification de code Uclid. Ce qu’il n’a pas testé, j’ai vérifié contre toutes les entrées possibles sur un ordinateur 32 bits. À la première personne à m’informer d’un légitime bug dans le code, je vais payer une prime de 10 $ US (par chèque ou Paypal). Si dirigé vers un organisme de bienfaisance, je vais payer 20$ US.
Contenu
  • Sur l’opération de comptage méthodologie
  • Calculer le signe d’un entier
  • Détecter si deux entiers ont des signes opposés
  • Calculer la valeur absolue d’entier (abs), sans ramification
  • Calculer le minimum (min) ou maximale (max) de deux entiers sans ramification
  • Déterminer si un entier est une puissance de 2
  • Signe qui s’étend
    • Signe qui s’étend du bit-une largeur constante
    • Signe qui s’étend d’un bit-largeur variable
    • Signe qui s’étend d’un bit-largeur variable en 3 opérations
  • Conditionnellement définir ou supprimer des morceaux sans ramification
  • Conditionnellement nier une valeur sans ramification
  • Brèves de deux valeurs selon un masque de fusion
  • Comptage bits définis
    • Compter les bits ensemble, naïve façon
    • Compter les bits définie par la table de choix
    • Compter les bits ensemble, chemin de Brian Kernighan
    • Compter les bits définis dans 14, 24 ou des mots de 32 bits à l’aide d’instructions 64-bit
    • Comptage de bits définis, en parallèle
    • Compter les bits définis (grade) du bit le plus significatif jusqu’à une position donnée
    • Sélectionnez la position de bit (à partir de la mèche plus significative) avec le nombre donné (grade)
  • Calcul de parité (1 si un nombre impair de bits défini, 0 sinon)
    • Calculer la parité d’un mot la naïve façon
    • Calculer la parité de la table de choix
    • Calculer la parité d’un octet à l’aide de 64-bit se multiplient et la division modulo
    • Calculer la parité de parole avec une multiply
    • Calculer la parité en parallèle
  • Permutation des valeurs
    • Permutation des valeurs avec la soustraction et l’addition
    • Permutation des valeurs avec XOR
    • Permutation de bits individuels avec XOR
  • Inversion des séquences de bits
    • Inverser bits la manière évidente
    • Inverser bits dans word par table de correspondance
    • Inverser les bits dans un octet avec 3 opérations (64-bit se multiplient et division modulo)
    • Inverser les bits dans un octet avec 4 opérations (64-bit se multiplient, aucune division)
    • Inverser les bits dans un octet avec 7 opérations (pas 64 bits, seuls 32)
    • Inverser une quantité de N bits en parallèle avec 5 * opérations lg(N)
  • Division modulo (aka les restes de calcul)
    • Calcul de division modulo par 1 << s sans une opération de division (évidente)
    • Calcul de division modulo par (1 << s)1 sans une opération de division
    • Calcul de division modulo par (1 << s)1 en parallèle sans une opération de division
  • Trouver le journal entier base 2 d’un nombre entier (aka la position de l’ensemble de bits plus haut)
    • Trouver le log base 2 d’un entier avec la série MSB N en o (n) opérations (la manière évidente)
    • Trouver le journal entier base 2 d’un nombre entier avec un flotteur de IEEE 64 bits
    • Trouver le log base 2 d’un entier avec une table de choix
    • Trouver le log base 2 d’un entier N bits dans les opérations de O(lg(N))
    • Trouver le log base 2 d’un entier N bits dans les opérations de O(lg(N)) avec multiply et recherche
  • Trouver le journal entier base 10 d’un entier
  • Trouver le journal entier base 10 d’un nombre entier la manière évidente
  • Trouver le journal entier base 2 d’un flotteur de IEEE 32 bits
  • Trouver le journal entier base 2 de la pow(2, r)-racine d’un flotteur de IEEE 32 bits (pour r de l’entier non signé)
  • Comptage consécutives rampante bits zéro (ou trouver les indices de bit)
    • Compter les consécutives bits zéro (fuite) sur la droite linéaire
    • Compter les consécutives bits zéro (fuite) sur la droite en parallèle
    • Compter les consécutives bits zéro (fuite) sur le droit de recherche binaire
    • Compter les consécutives bits zéro (fuite) sur la droite en castant en float
    • Compter les consécutives bits zéro (fuite) sur la droite avec la division modulo et recherche
    • Compter les consécutives bits zéro (fuite) sur la droite avec multiply et recherche
  • Arrondir à la prochaine plus haute puissance de 2 par moulage de flotteur
  • Arrondir à la prochaine plus haute puissance de 2
  • Entrelacement de bits (alias informatique Morton numéros)
    • Interleave bits la manière évidente
    • Interleave bits par recherche dans la table
    • Interleave multiplier les bits avec 64-bit
    • Entrelacement de bits par des nombres binaires Magic
  • Tests pour les plages d’octets dans un mot (et compter les occurrences trouvées)
    • Déterminer si un mot possède un octet nul
    • Déterminer si un mot possède un octet égal à n
    • Déterminer si un mot a octet inférieur à n
    • Déterminer si un mot possède un octet supérieur à n
    • Déterminer si un mot possède un octet entre m et n
  • Calculer la permutation lexicographique suivante de bt

Sur l’opération de comptage méthodologie

En totalisant le nombre d’opérations pour les algorithmes ici, n’importe quel opérateur C est comptée comme une seule opération. Cessions intermédiaires, qui ne doivent pas être inscrites au RAM, ne sont pas comptées. Bien sûr, cette approche de comptage opération sert uniquement une approximation du nombre réel des instructions de la machine et le temps processeur. Toutes les opérations sont censées pour prendre la même quantité de temps, ce qui n’est pas vrai dans la réalité, mais les processeurs ont été va plus en plus dans cette direction au fil du temps. Il existe de nombreuses nuances qui déterminent à quelle vitesse un système exécutera un échantillon donné de code, tels que les tailles de cache, largeurs de bande de mémoire, jeux d’instructions, etc.. En fin de compte, l’analyse comparative est la meilleure façon de déterminer si une méthode est vraiment plus rapide que l’autre, alors envisager les techniques ci-dessous que les possibilités de tester sur votre architecture cible.
Calculer le signe d’un entier

int v;      // we want to find the sign of v
int sign;   // the result goes here

// CHAR_BIT is the number of bits per byte (normally 8).
sign = -(v < 0);  // if v < 0 then -1, else 0.
// or, to avoid branching on CPUs with flag registers (IA32):
sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT – 1));
// or, for one less instruction (but not portable):
sign = v >> (sizeof(int) * CHAR_BIT – 1);

La dernière expression ci-dessus évalue à signer = v >> 31 pour les entiers 32 bits. C’est une opération plus vite que la manière évidente, le signe =-(v < 0). Cette astuce fonctionne parce que lorsque des entiers signés sont décalées à droite, la valeur du bit plus à gauche est copiée dans les autres bits. Le bit de gauche est 1 lorsque la valeur est négative et 0 sinon ; tous les bits 1 donne -1. Malheureusement, ce comportement est propres à l’architecture.
Alternativement, si vous préférez que le résultat soit soit -1 + 1, puis utilisez :
sign = +1 | (v >> (sizeof(int) * CHAR_BIT – 1));  // if v < 0 then -1, else +1
En revanche, si vous préférez le résultat soit-1, 0 ou + 1, puis utilisez :
signe = (v! = 0) | -(int) ((unsigned int)((int)v) >> (sizeof (int) * CHAR_BIT 1)) ;
Ou, pour plus de vitesse mais moins la portabilité :
sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT – 1));

// Or, for more speed but less portability:
sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT – 1));  // -1, 0, or +1

// Or, for portability, brevity, and (perhaps) speed:
sign = (v > 0) – (v < 0); // -1, 0, or +1
Si au lieu de cela, vous voulez savoir si quelque chose n’est pas négatif, résultant en + 1, sinon 0, utilisez :
sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT – 1)); // if v < 0 then 0, else 1
Mise en garde : Le 7 mars 2003, Angus Duggan a souligné que la spécification ANSI C de 1989 laisse le résultat du décalage vers la droite signé défini par l’implémentation, sur certains systèmes que ce hack peut ne pas fonctionner. Pour une plus grande portabilité, Toby Speight a proposé le 28 septembre 2005 que CHAR_BIT être utilisé ici et partout plutôt que dans l’hypothèse octets 8 bits de longs. Angus a recommandé les versions plus portables ci-dessus, impliquant la coulée sur 4 mars 2006. Rohit Garg a proposé la version pour les entiers non négatifs sur 12 septembre 2009.

Détecter si deux entiers ont des signes opposés

int x, y;               // input values to compare signs

bool f = ((x ^ y) < 0); // true iff x and y have opposite signs

Manfred Weis a suggéré de qu’ajouter cette entrée sur 26 novembre 2009.


Calculer la valeur absolue d’entier (abs), sans ramification

int v;           // we want to find the absolute value of v
unsigned int r;  // the result goes here
int const mask = v >> sizeof(int) * CHAR_BIT – 1;

r = (v + mask) ^ mask;

Variation brevetée :

r = (v ^ mask) - mask;
Certains processeurs n’est pas une instruction de valeur absolue du nombre entier (ou le compilateur ne parvient pas à les utiliser). Sur les machines la ramification est cher, l’expression ci-dessus peut être plus rapide que l’approche évidente, r = (v < 0) ? -v (non signé): v, même si le nombre d’opérations est le même.
Le 7 mars 2003, Angus Duggan a souligné que la spécification ANSI C de 1989 laisse le résultat du décalage vers la droite signé défini par l’implémentation, sur certains systèmes que ce hack peut ne pas fonctionner. J’ai lu que C ANSI ne nécessite pas de valeurs à représenter comme complément à deux, donc il ne fonctionne pas pour cette raison aussi bien (sur diminishingly quelques vieilles machines qui utilisent encore son complément). Le 14 mars 2004, Keith H. Duggar m’a envoyé la breveté de variation supérieure ; Il est supérieur à celui que je suis venu au départ avec, r = (+ () 1 | v>>(sizeof(int)*CHAR_BIT-1))) * v, car une multiplication n’est pas utilisée. Malheureusement, cette méthode a été brevetée aux États-Unis le 6 juin 2000 par Vladimir Yu Volkonsky et assignée à Sun Microsystems. Le 13 août 2006, Yuriy Kaminskiy m’a dit que le brevet est probablement non valide car la méthode a été publiée bien avant que le brevet était encore classé, comme par exemple comment optimiser pour le processeur de Pentium de brouillard Agner, datée du 9 novembre 1996. Yuriy a aussi mentionné que ce document a été traduit en russe, en 1997, ce qui aurait pu interpréter Vladimir. En outre, l’Internet Archive a également un vieux lien vers elle. Le 30 janvier 2007, Peter Kankowski a partagé avec moi une version abs qu’il a découvert et qui a été inspirée par la sortie de compilateur de Visual C++ de Microsoft. Il est présenté ici comme première solution. Le 6 décembre 2007, Hai Jin s’est plaint que le résultat a été signé, lors du calcul de l’abs de la valeur plus négative, c’est toujours négatif. Le 15 avril 2008 Andrew Shapira a souligné que l’approche évidente pourrait déborder, comme il lui manquait un casting (non signé) pour une portabilité maximale, il a proposé (v < 0) ? (1 + ((unsigned)(-1-v))): v (non signé). Mais citant les spécifications ISO C99 le 9 juillet 2008, Vincent Lefèvre m’a convaincu de l’enlever parce que même sur des machines non-2 s-complément – v (non signé) va faire la bonne chose. L’évaluation de – v (non signé) convertit d’abord la valeur négative de v en non en ajoutant 2 ** N, ce qui donne une 2 s complètent la représentation de la valeur de v ‘ s que je vais appeler U. Alors, U est niée, ce qui donne le résultat souhaité, -U = 0 – U = 2 ** N – U = 2 ** N – (2 ** N + v) = – v = abs(v).

Calculer le minimum (min) ou maximale (max) de deux entiers sans ramification

int x;  // we want to find the minimum of x and y
int y;
int r;  // the result goes here

r = y ^ ((x ^ y) & -(x < y)); // min(x, y)

Sur certaines machines rares la ramification est très cher et aucuns instructions move condition n’existent, l’expression ci-dessus peut être plus rapide que l’approche évidente, r = (x < y) ? x: y, même si cela implique plus de deux instructions. (En règle générale, l’approche évidente est préférable, cependant.) Cela fonctionne parce que si x < y, puis-(x < y) sera tous les zéros, alors r = y ^ (x ^ y) & ~ 0 = y ^ x ^ y = x. Autrement, si x > = y, puis-(x < y) sera tous les zéros, si ur = y ^ ((x ^ y) & 0) = y. Sur certaines machines, évaluation (x < y) 0 ou 1 selon une instruction de branchement, donc il ne peut y avoir aucun avantage.
Pour trouver la valeur maximale, utilisez :
r = x ^ ((x ^ y) & -(x < y)); // max(x, y)
Versions rapides et Sales :
Si vous savez que INT_MIN < = x y < = INT_MAX, alors vous pouvez utiliser ce qui suit, qui est plus rapides car (x y) ne doit être évaluée en une seule fois.

r = y + ((x – y) & ((x – y) >> (sizeof(int) * CHAR_BIT – 1))); // min(x, y)
r = x – ((x – y) & ((x – y) >> (sizeof(int) * CHAR_BIT – 1))); // max(x, y)

Notez que la spécification ANSI C de 1989 ne précise pas le résultat de signé décalage vers la droite, donc ce ne sont pas portables. Si des exceptions sont levées sur les débordements, puis les valeurs de x et y doit être non signé ou effectuer un cast en unsigned pour les soustractions à ne pas provoquer inutilement une exception, cependant le décalage vers la droite a besoin d’un opérande signé à tout ce qu’il produisent bits lorsque négatives, donc il a signé.
Le 7 mars 2003, Angus Duggan a souligné la question de la portabilité de décalage vers la droite. Le 3 mai 2005, Randal E. Bryant attiré mon attention sur le fait que la condition préalable, INT_MIN < = x y < = INT_MAX et a proposé la version non-rapide et sale comme un correctif. Ces deux problèmes concernent uniquement la version rapide et sale. Nigel Horspoon observée le 6 juillet 2005 que gcc produit le même code sur un Pentium comme la solution évidente en raison de la façon dont il prend la valeur (x < y). Le 9 juillet 2008, Vincent Lefèvre a souligné le potentiel des exceptions de dépassement de capacité avec soustractions en r = y + ((x-y) &-(x < y)), qui était la version précédente. Timothy b. Terriberry a proposé à l’aide de xor, plutôt que d’ajouter et subract pour éviter la coulée et le risque de débordements le 2 juin 2009.

Déterminer si un entier est une puissance de 2

unsigned int v; // we want to see if v is a power of 2
bool f;         // the result goes here

f = (v & (v – 1)) == 0;

Notz que 0 est considérée incorrectement comme une puissance de 2 ici. Pour résoudre ce problème, utilisez :
f = v && !(v & (v – 1));

Signe qui s’étend du bit-une largeur constante

Extension de signe est automatique pour les types intégrés, tels que les caractères et les entiers (ints). Mais supposez que vous avez signée deux compléter nombre, x, qui est stockée à l’aide uniquement de b bits. En outre, supposons que vous voulez convertir x en int, qui a plus de bits b. Une copie simple fonctionnera si x est positif, mais si il est négatif, le signe doit être étendu. Par exemple, si nous avons seulement 4 bits pour stocker un nombre, puis -3 est représenté comme 1101 en binaire. Si nous avons 8 bits, puis -3 est 11111101. Le bit plus significative de la représentation de 4 bits est répliqué sinistrally pour remplir la destination lorsque nous convertir une représentation possédant plus de bits ; C’est le signe qui s’étend. Dans C, extension de signe d’un bit-largeur constante est triviale, car les champs de bits peuvent être spécifiées dans les structures ou unions. Par exemple, pour convertir de 5 bits en entier complet :

int x; // convert this from using 5 bits to a full int
int r; // resulting sign extended number goes here
struct {signed int x:5;} s;
r = s.x = x;

Ce qui suit est une fonction de modèle C++ qui utilise la même fonctionnalité de langage pour convertir de B bits en une seule opération (bien que le compilateur génère plus, bien sûr).

template <typename T, unsigned B>
inline T signextend(const T x)
{
struct {T x:B;} s;
return s.x = x;
}

int r = signextend<signed int,5>(x);  // sign extend 5 bit number x to r

John Byrd a pris une faute de frappe dans le code (attribué à la mise en forme html) le 2 mai 2005. Le 4 mars 2006, Pat Wood a souligné que la norme ANSI C exige que le champ de bits ont le mot clé “signé” devant être signé ; dans le cas contraire, le signe n’est pas défini.

Signe qui s’étend d’un bit-largeur variable

Parfois nous avons besoin d’étendre le signe d’un nombre, mais nous ne savons pas a priori le nombre de bits, b, elle est représentée. (Ou nous pourrions être de programmation dans un langage tel que Java, qui n’a pas de champs de bits).

unsigned b; // number of bits representing the number in x
int x;      // sign extend this b-bit number to r
int r;      // resulting sign-extended number
int const m = 1U << (b – 1); // mask can be pre-computed if b is fixed

x = x & ((1U << b) – 1);  // (Skip this if bits in x above position b are already zero.)
r = (x ^ m) – m;

Le code ci-dessus nécessite quatre opérations, mais lorsque le bitwidth est une constante et non variable, elle nécessite seulement deux opérations rapides, en supposant que les bits supérieurs sont déjà égales à zéro.
Une méthode légèrement plus rapide mais moins portable qui ne dépend pas des bits dans x ci-dessus b position étant zéro est :
int const m = CHAR_BIT * sizeof(x) – b;

r = (x << m) >> m;

Sean A. Irvine a suggéré que j’ajouter signe les méthodes d’extension de cette page le 13 juin 2004, et il a donné m = (1 << (b 1)) 1 ; r = -(x & ~m) | x ; comme point de départ d’où j’ai optimisé pour obtenir m = 1U << (b 1) ; r =-(x & m) | x. mais puis, le 11 mai 2007, Shay vert a proposé la version ci-dessus, qui requiert une opération de moins que la mienne. Vipin Sharma a suggéré de qu’ajouter une étape à faire face aux situations x avait possibles en morceaux, autres que les bits b que nous voulions signe-s’étendent sur 15 octobre 2008. Sur 31 décembre 2009, Chris Pirazzi suggéré que j’ai ajouter la version plus rapide, ce qui nécessite deux opérations pour une largeur constante de bit et trois pour des largeurs variables.


Signe qui s’étend d’un bit-largeur variable en 3 opérations

Ce qui suit peut être lent sur certaines machines, en raison de l’effort requis pour la multiplication et la division. Cette version est 4 opérations. Si vous savez que votre première bit-largeur, b, est supérieur à 1, vous pourriez faire ce type d’extension de signe dans 3 opérations à l’aide de r = (x * multipliers[b]) / multiplicateurs [b], qui ne nécessite qu’un seul tableau de recherche.
unsigned b; // number of bits representing the number in x
int x;      // sign extend this b-bit number to r
int r;      // resulting sign-extended number
#define M(B) (1U << ((sizeof(x) * CHAR_BIT) – B)) // CHAR_BIT=bits/byte
static int const multipliers[] =
{
0,     M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
M(32)
}; // (add more if using more than 64 bits)
static int const divisors[] =
{
1,    ~M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
M(32)
}; // (add more for 64 bits)
#undef M
r = (x * multipliers[b]) / divisors[b];
La variation suivante n’est pas portable, mais sur les architectures qui emploient un droit-décalage arithmétique, maintenir le signe, il devrait être rapide.
const int s = -b; // OR:  sizeof(x) * CHAR_BIT – b;

r = (x << s) >> s;

Randal E. Bryant a signalé un bug sur le 3 mai 2005 dans une version antérieure (qui utilisé [] multiplicateurs pour divisors[]), il a échoué sur le cas de x = 1 et b = 1.


Conditionnellement définir ou supprimer des morceaux sans ramification

bool f;         // conditional flag

unsigned int m; // the bit mask

unsigned int w; // the word to modify:  if (f) w |= m; else w &= ~m;

w ^= (-f ^ w) & m;

// OR, for superscalar CPUs:
w = (w & ~m) | (-f & m);

Sur certaines architectures, l’absence de ramification peut plus que compenser pour ce qui semble être deux fois plus d’opérations. Par exemple, des tests de vitesse informel sur un AMD Athlon ™ XP 2100 + indiquent que c’était 5 à 10 % plus vite. Un Intel Core 2 Duo exécuté la version superscalaire environ 16 % plus rapide que la première. Glenn Slayden m’a informé de la première expression le 11 décembre 2003. Marco Yu la version superscalaire a partagé avec moi le 3 avril 2007 et a attiré mon attention sur une faute de frappe 2 jours plus tard.


Conditionnellement nier une valeur sans ramification

Si vous devez annuler uniquement quand un drapeau a la valeur false, puis utilisez ce qui suit afin d’éviter le branchement :

bool fDontNegate;  // Flag indicating we should not negate v.
int v;             // Input value to negate if fDontNegate is false.
int r;             // result = fDontNegate ? v : -v;

r = (fDontNegate ^ (fDontNegate – 1)) * v;

Si vous devez annuler uniquement quand un drapeau est true, puis utilisez ceci :

bool fNegate;  // Flag indicating if we should negate v.
int v;         // Input value to negate if fNegate is true.
int r;         // result = fNegate ? -v : v;

r = (v ^ -fNegate) + fNegate;

Avraham Plotnitzky a proposé de qu’ajouter la première version sur 2 juin 2009. Motivés pour éviter la multiplication, je suis venu avec la deuxième version le 8 juin 2009. Alfonso De Gregorio a souligné que certains parens, il manquait le 26 novembre 2009 et a reçu une prime de bogue.

Brèves de deux valeurs selon un masque de fusion

unsigned int a;    // value to merge in non-masked bits
unsigned int b;    // value to merge in masked bits
unsigned int mask; // 1 where bits from b should be selected; 0 where from a.
unsigned int r;    // result of (a & ~mask) | (b & mask) goes here

r = a ^ ((a ^ b) & mask);

Il rase, une opération de la manière évidente de la combinaison des deux ensembles de bits selon un masque de bits. Si le masque est une constante, alors il ne peut y avoir aucun avantage.

Ron Jeffery cela m’envoyé le 9 février 2006.

Compter les bits ensemble (naïve façon)

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

for (c = 0; v; v >>= 1)
{
c += v & 1;
}

L’approche naïve nécessite une itération par morceau, jusqu’à ce qu’aucuns plus de bits ne sont définis. Ainsi, sur un mot de 32 bits avec seulement le record établi, il passera par 32 itérations.

Compter les bits définie par la table de choix

static const unsigned char BitsSetTable256[256] =
{
#   define B2(n) n,     n+1,     n+1,     n+2
#   define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
#   define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
B6(0), B6(1), B6(1), B6(2)
};

unsigned int v; // count the number of bits set in 32-bit value v
unsigned int c; // c is the total bits set in v

// Option 1:
c = BitsSetTable256[v & 0xff] +
BitsSetTable256[(v >> 8) & 0xff] +
BitsSetTable256[(v >> 16) & 0xff] +
BitsSetTable256[v >> 24];

// Option 2:
unsigned char * p = (unsigned char *) &v;
c = BitsSetTable256[p[0]] +
BitsSetTable256[p[1]] +
BitsSetTable256[p[2]] +
BitsSetTable256[p[3]];

// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}

Le 14 juillet 2009 Hallvard Furuseth a suggéré la table compactés de macro.

Compter les bits ensemble, chemin de Brian Kernighan

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v – 1; // clear the least significant bit set
}

Méthode de Brian Kernighan traverse comme nombre d’itérations étant donné qu’il est définissez les bits. Donc si nous avons un mot de 32 bits avec uniquement le jeu peu élevé, alors il n’ira une fois dans la boucle.

2e éd. (par Brian W. Kernighan et Dennis M. Ritchie) publié en 1988, le langage de programmation C mentionne cela dans l’exercice 2-9. Le 19 avril 2006 Don Knuth m’a fait remarquer que cette méthode “a été publié par Peter Wegner dans MCAC 3 (1960), 322. (Également découvert indépendamment par Derrick Lehmer et publié en 1964 dans un livre édité par Beckenbach.) »

Compter les bits définis dans 14, 24 ou des mots de 32 bits à l’aide d’instructions 64-bit

unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL)
% 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) %
0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

Cette méthode nécessite un processeur 64 bits avec division modulo rapide être efficace. La première option prend seulement 3 opérations ; la deuxième option prend 10 ; et la troisième option prend 15.

Rich Schroeppel créé à l’origine une version 9 bits, semblable à l’option 1 ; Voir la section programmation Hacks de Beeler, M., Gosper, R. W. et Schrœppel, R. HAKMEM. MIT AI Memo 239 du 29 février 1972. Sa méthode était l’inspiration pour les variantes ci-dessus, conçu par Sean Anderson. Randal E. Bryant a offert quelques corrections de bugs sur le 3 mai 2005. Bruce Dawson tordu ce qui avait été une version de 12 bits et il fait adaptés pour 14 bits en utilisant le même nombre d’opérations sur Février 1, 2007.

Comptage de bits définis, en parallèle

unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};

c = v – ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];

Le tableau B, exprimé en binaire, est :

B [0] = 0X55555555 = 01010101 01010101 01010101 01010101
B [1] = 0X33333333 = 00110011 00110011 00110011 00110011
B [2] = 0X0F0F0F0F = 00001111 00001111 00001111 00001111
B [3] = 0X00FF00FF = 00000000 11111111 11111111 DE 00000000
B [4] = 0X0000FFFF = 00000000 00000000 11111111 11111111
Nous pouvons ajuster la méthode pour les grandes tailles de nombre entier en continuant avec les patrons de nombres binaires de magie, de B et S. S’il y a des morceaux de k, alors nous devons les baies S et B éléments de ceil(lg(k)) longue, et nous devons calculer le même nombre d’expressions pour c car S ou B sont longues. Pour un v 32-bit, 16 opérations sont utilisées.
La meilleure méthode pour compter les bits dans un entier 32 bits v est le suivant :
v = v – ((v >> 1) & 0x55555555);                    // reuse input as temporary

v = (v & 0x33333333) + ((v >> 2) & 0x33333333);     // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count

Le meilleur morceau méthode de comptage prend seulement 12 opérations, qui est identique à la méthode lookup tables, mais évite la mémoire et des éventuelles absences du cache d’une table. C’est un hybride entre la méthode purement parallèle ci-dessus et les méthodes précédentes en utilisant multiplie (dans la section sur le comptage de fers d’instructions 64-bit), bien qu’il n’utilise pas instructions 64 bits. Les comtes de bits définis dans les octets se fait en parallèle, et la somme totale des bits dans les octets est calculée en multipliant par 0x1010101 et décalage à droite de 24 bits.

Une généralisation de la mèche de meilleure méthode en entiers de bit-largeurs jusqu’à 128 (paramétré par le type T) de comptage est le suivant :
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(T) – 1) * CHAR_BIT; // count

Voir post sympa newsgroup de Ian Ashdown pour plus d’informations sur le comptage du nombre de bits défini (également connu sous le nom de sideways addition). Le meilleur morceau méthode de comptage a été porté à mon attention sur le 5 octobre 2005 par Andrew Shapira ; Il a trouvé en pages 187-188, de Software Optimization Guide pour AMD Athlon ™ 64 et Opteron ™ processeurs. Charlie Gordon a proposé une façon de se raser une seule opération de la version purement parallèle sur 14 décembre 2005, et Don Clugston garnis de trois autres de lui sur 30 décembre 2005. J’ai fait une faute de frappe avec suggestion de Don que Eric Cole repéré sur 8 janvier 2006. Plus tard, Eric a suggéré la généralisation de bit-largeur arbitraire à la meilleure méthode sur le 17 novembre 2006. Le 5 avril 2007, Al Williams a observé que j’ai eu une ligne de code mort en haut de la première méthode.


Compter les bits définis (grade) du bit le plus significatif jusqu’à une position donnée

Les trouvailles suivants le rang d’un bit, signifiant qu’il retourne la somme de bits définis à 1 de la majeure partie-heurter bit downto le bit à la position donnée.

uint64_t v;       // Compute the rank (bits set) in v from the MSB to pos.
unsigned int pos; // Bit position to count bits upto.
uint64_t r;       // Resulting rank of bit at pos goes here.

// Shift out bits after given position.
r = v >> (sizeof(v) * CHAR_BIT – pos);
// Count set bits in parallel.
// r = (r & 0x5555…) + ((r >> 1) & 0x5555…);
r = r – ((r >> 1) & ~0UL/3);
// r = (r & 0x3333…) + ((r >> 2) & 0x3333…);
r = (r & ~0UL/5) + ((r >> 2) & ~0UL/5);
// r = (r & 0x0f0f…) + ((r >> 4) & 0x0f0f…);
r = (r + (r >> 4)) & ~0UL/17;
// r = r % 255;
r = (r * (~0UL/255)) >> ((sizeof(v) – 1) * CHAR_BIT);

Juha Järvi m’a envoyé ceci sur 21 novembre 2009 comme une opération inverse pour le calcul de la position du bit avec le grade donné, ce qui suit.


Sélectionnez la position de bit (à partir de la mèche plus significative) avec le nombre donné (grade)

Le code 64 bits suivant sélectionne la position de la rth 1 bit en comptant de gauche à droite. En d’autres termes si nous attaquer au plus important, aller de l’avant vers la droite, compter le nombre de bits définis à 1 jusqu’à atteindre le rang, r désiré, puis la position nous nous arrêtons est retournée. Si la position demandée dépasse le nombre de bits définis, puis 64 est retourné. Le code peut être modifié pour 32-bit ou comptage de la droite.
  uint64_t v;          // Input value to find position with rank r.
unsigned int r;      // Input: bit’s desired rank [1-64].
unsigned int s;      // Output: Resulting position of bit with rank r [1-64]
uint64_t a, b, c, d; // Intermediate temporaries for bit count.
unsigned int t;      // Bit count temporary.

// Do a normal parallel bit count for a 64-bit integer,
// but store all intermediate steps.
// a = (v & 0x5555…) + ((v >> 1) & 0x5555…);
a =  v – ((v >> 1) & ~0UL/3);
// b = (a & 0x3333…) + ((a >> 2) & 0x3333…);
b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
// c = (b & 0x0f0f…) + ((b >> 4) & 0x0f0f…);
c = (b + (b >> 4)) & ~0UL/0x11;
// d = (c & 0x00ff…) + ((c >> 8) & 0x00ff…);
d = (c + (c >> 8)) & ~0UL/0x101;
t = (d >> 32) + (d >> 48);
// Now do branchless select!
s  = 64;
// if (r > t) {s -= 32; r -= t;}
s -= ((t – r) & 256) >> 3; r -= (t & ((t – r) >> 8));
t  = (d >> (s – 16)) & 0xff;
// if (r > t) {s -= 16; r -= t;}
s -= ((t – r) & 256) >> 4; r -= (t & ((t – r) >> 8));
t  = (c >> (s – 8)) & 0xf;
// if (r > t) {s -= 8; r -= t;}
s -= ((t – r) & 256) >> 5; r -= (t & ((t – r) >> 8));
t  = (b >> (s – 4)) & 0x7;
// if (r > t) {s -= 4; r -= t;}
s -= ((t – r) & 256) >> 6; r -= (t & ((t – r) >> 8));
t  = (a >> (s – 2)) & 0x3;
// if (r > t) {s -= 2; r -= t;}
s -= ((t – r) & 256) >> 7; r -= (t & ((t – r) >> 8));
t  = (v >> (s – 1)) & 0x1;
// if (r > t) s–;
s -= ((t – r) & 256) >> 8;
s = 65 – s;

Si la ramification est rapide sur votre unité centrale cible, envisager décommenter les instructions if et de commenter les lignes qui suivent.
Juha Järvi m’a envoyé ceci sur 21 novembre 2009.

Calcul de parité la naïve façon


unsigned int v;       // word value to compute the parity of
bool parity = false;  // parity will be the parity of v

while (v)
{
parity = !parity;
v = v & (v – 1);
}

Le code ci-dessus utilise une approche comme peu de Brian Kernigan comptage, ci-dessus. Le temps que nécessaire est proportionnel au nombre de bits définis.
Calculer la parité de la table de choix

static const bool ParityTable256[256] =
{
#   define P2(n) n, n^1, n^1, n
#   define P4(n) P2(n), P2(n^1), P2(n^1), P2(n)
#   define P6(n) P4(n), P4(n^1), P4(n^1), P4(n)
P6(0), P6(1), P6(1), P6(0)
};

unsigned char b;  // byte value to compute the parity of
bool parity = ParityTable256[b];

// OR, for 32-bit words:
unsigned int v;
v ^= v >> 16;
v ^= v >> 8;
bool parity = ParityTable256[v & 0xff];

// Variation:
unsigned char * p = (unsigned char *) &v;
parity = ParityTable256[p[0] ^ p[1] ^ p[2] ^ p[3]];

Randal E. Bryant a encouragé l’ajout de la dernière variation évidente (il est vrai) avec la variable p le 3 mai 2005. Bruce Rawles a trouvé une faute de frappe dans une instance du nom de la variable tableau sur 27 septembre 2005, et il a reçu une prime de bogue de 10 $. Le 9 octobre 2006, Fabrice Bellard a suggéré les variations de 32 bits ci-dessus, qui n’exigent qu’une recherche dans la table ; la version précédente avait quatre recherches (un par octet) et ont été plus lente. Le 14 juillet 2009 Hallvard Furuseth a suggéré la table compactés de macro.

Calculer la parité d’un octet à l’aide de 64-bit se multiplient et la division modulo

unsigned char b;  // byte value to compute the parity of
bool parity =
(((b * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF) & 1;

La méthode ci-dessus prend environ 4 opérations, mais ne fonctionne que sur des octets.

Calculer la parité de parole avec une multiply
La méthode suivante calcule la parité de la valeur de 32 bits dans seulement 8 opérations à l’aide d’une multiplication.

unsigned int v; // 32-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x11111111U) * 0x11111111U;
return (v >> 28) & 1;

Aussi pour le 64 bits, 8 opérations sont encore assez.

unsigned long long v; // 64-bit word
v ^= v >> 1;
v ^= v >> 2;
v = (v & 0x1111111111111111UL) * 0x1111111111111111UL;
return (v >> 60) & 1;

Andrew Shapira est venu avec cela et me l’a envoyé le 2 septembre 2007.

Calculer la parité en parallèle

unsigned int v ; valeur de mot pour calculer la parité de

v ^= v >> 16;
v ^= v >> 8;
v ^= v >> 4;
v &= 0xf;
return (0x6996 >> v) & 1;

La méthode ci-dessus utilise environ 9 opérations et fonctionne pour les mots de 32 bits. Il peut être optimisé pour travailler seulement sur octets de 5 opérations en supprimant les deux lignes immédiatement après « unsigned int v; ». La méthode premiers déplacements et Xor les huit grignote la valeur 32 bits ensemble, laissant le résultat dans le Quartet le plus bas de v. Ensuite, le nombre binaire 0110 1001 1001 0110 (0x6996 en hexadécimal) est décalé vers la droite de la valeur représentée dans le Quartet le plus bas de v. Ce numéro est comme une miniature 16 bits parité-table indexée par les quatre bits de poids faibles en v. Le résultat a la parité de v dans le bit 1, qui est masqué et retourné.

Merci à Mathew Hendry de remarquer l’idée de Maj-recherche à la fin le 15 décembre 2002. Cette optimisation rase deux opérations au large en utilisant uniquement le déplacement et Xor pour trouver la parité.

Permutation des valeurs avec la soustraction et l’addition

#define SWAP(a, b) ((&(a) == &(b)) || \
(((a) -= (b)), ((b) += (a)), ((a) = (b) – (a))))

Cela Permute les valeurs d’a et b sans utiliser une variable temporaire. La vérification initiale pour a et b étant le même emplacement en mémoire peut être omise lorsque vous savez que cela ne peut pas se produire. (Le compilateur peut omettre d’optimisation en tout cas.) Si vous activez les débordements exceptions, puis passez des valeurs non signées ce une exception n’est pas levée. La méthode XOR qui suit peut être un peu plus vite sur certaines machines. Ne pas utiliser ce avec nombres à virgule flottante (sauf si vous opérez sur leurs représentations entier).
Sanjeev Sivasankaran suggéré que cela ajouter le 12 juin 2007. Vincent Lefèvre a souligné le potentiel des exceptions de dépassement de capacité sur le 9 juillet 2008

Permutation des valeurs avec XOR

#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
Il s’agit d’un vieux truc d’échanger les valeurs des variables a et b sans utiliser d’espace supplémentaire pour une variable temporaire.
Le 20 janvier 2005, Iain A. Fleming a souligné que la macro ci-dessus ne fonctionne pas lorsque vous échanger avec le même emplacement de mémoire, tels que SWAP (a [i], a[j]) avec i == j. Donc si qui peuvent se produire, envisager de définir la macro comme ((a == b) || (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))). Le 14 juillet 2009, Hallvard Furuseth a suggéré que, sur certaines machines, (((a) ^ (b)) && ((b) ^ = (a) ^ = (b), (a) ^ = (b))) pourrait être plus rapide, puisque le (a) ^ expression (b) est réutilisée.

Permutation de bits individuels avec XOR

unsigned int i, j; // positions of bit sequences to swap
unsigned int n;    // number of consecutive bits in each sequence
unsigned int b;    // bits to swap reside in b
unsigned int r;    // bit-swapped result goes here

unsigned int x = ((b >> i) ^ (b >> j)) & ((1U << n) – 1); // XOR temporary
r = b ^ ((x << i) | (x << j));

À titre d’exemple de permutation de chaînes de bits Supposons que nous avons ont b = 00101111 (exprimé en binaire) et nous voulons échanger le n = 3 bits consécutifs commençant à i = 1 (le deuxième bit de la droite) avec les 3 bits consécutifs commençant à j = 5 ; le résultat serait r = 11100011 (binaire).

Cette méthode de permutation est similaire à l’usage général XOR swap truc, mais la destinée pour des opérations sur les bits individuels. La variable x stocke le résultat de XOR les paires de valeurs de bit, que nous voulons échanger, et puis les bits sont définis sur le résultat d’eux-mêmes fonction XOR avec x. Bien sûr, le résultat n’est pas défini si les séquences se chevauchent.
Le 14 juillet 2009 Hallvard Furuseth a suggéré que je change le 1 << n 1U << n parce que la valeur a été assignée à un non signé et afin d’éviter le déplacement dans un bit de signe.

Inverser bits la manière évidente

unsigned int v;     // input bits to be reversed
unsigned int r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT – 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{
r <<= 1;
r |= v & 1;
s–;
}
r <<= s; // shift when v’s highest bits are zero

Le 15 octobre 2004, Michael Hoisie a signalé un bug dans la version originale. Randal E. Bryant suggère d’abolir une opération supplémentaire le 3 mai 2005. Behdad Esfabod suggère une légère modification qui a éliminé une itération de la boucle sur 18 mai 2005. Puis, le 6 février 2007, Liyong Zhou a suggéré une meilleure version qui boucle tandis que v n’est pas 0, alors plutôt que d’itération dans l’ensemble peu il s’arrête au début.


Inverser bits dans word par table de correspondance

static const unsigned char BitReverseTable256[256] =
{
#   define R2(n)     n,     n + 2*64,     n + 1*64,     n + 3*64
#   define R4(n) R2(n), R2(n + 2*16), R2(n + 1*16), R2(n + 3*16)
#   define R6(n) R4(n), R4(n + 2*4 ), R4(n + 1*4 ), R4(n + 3*4 )
R6(0), R6(2), R6(1), R6(3)
};

unsigned int v; // reverse 32-bit value, 8 bits at time
unsigned int c; // c will get v reversed

// Option 1:
c = (BitReverseTable256[v & 0xff] << 24) |
(BitReverseTable256[(v >> 8) & 0xff] << 16) |
(BitReverseTable256[(v >> 16) & 0xff] << 8) |
(BitReverseTable256[(v >> 24) & 0xff]);

// Option 2:
unsigned char * p = (unsigned char *) &v;
unsigned char * q = (unsigned char *) &c;
q[3] = BitReverseTable256[p[0]];
q[2] = BitReverseTable256[p[1]];
q[1] = BitReverseTable256[p[2]];
q[0] = BitReverseTable256[p[3]];

La première méthode prend environ 17 opérations, et le second prend environ 12, en supposant que votre CPU peut charger et stocker les octets facilement.

Le 14 juillet 2009 Hallvard Furuseth a suggéré la table compactés de macro.

Inverser les bits dans un octet avec 3 opérations (64-bit se multiplient et division modulo) :

unsigned char b; // reverse this (8-bit) byte

b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

Le multiplier opération crée cinq copies distinctes du modèle d’octet de sortance en une valeur 64 bits. L’opération sélectionne les bits qui sont en position correcte (inversée), par rapport à chaque groupes de 10 bits de bits. La multiplication et les opérations et copient les bits de l’octet original pour chacun d’eux s’affichent dans une seule des ensembles de 10 bits. Les positions inversées des bits de l’octet initial coïncident avec leur position relative au sein de n’importe quel ensemble de 10 bits. La dernière étape, qui implique la division modulo par 2 ^ 101, a pour effet de fusionner ensemble chaque ensemble de 10 bits (à partir de positions 0-9, 10-19, 20-29,…) dans la valeur 64 bits. Ils ne se chevauchent pas, pour l’ajout les étapes qui sous-tendent que la division modulo se comporte comme ou opérations.

Cette méthode a été attribuée à Rich Schroeppel dans la section programmation Hacks de Gosper Beeler, M., R. W. et Schrœppel, R. HAKMEM. MIT AI Memo 239 du 29 février 1972.

Inverser les bits dans un octet avec 4 opérations (64-bit se multiplient, aucune division) :

unsigned char b; // reverse this byte

b = ((b * 0x80200802ULL) & 0x0884422110ULL) * 0x0101010101ULL >> 32;

Ce qui suit montre le flux des valeurs bit avec les variables booléennes a, b, c, d, e, f, g et h, qui forment un octet de 8 bits. Remarquez comment les premiers fans de multiplier le peu de mires à plusieurs copies, tandis que le dernier multiplier combine au cinquième octet de la droite.

                                                                                        abcd efgh (-> hgfe dcba)
*                                                      1000 0000  0010 0000  0000 1000  0000 0010 (0x80200802)
-------------------------------------------------------------------------------------------------
                                            0abc defg  h00a bcde  fgh0 0abc  defg h00a  bcde fgh0
&                                           0000 1000  1000 0100  0100 0010  0010 0001  0001 0000 (0x0884422110)
-------------------------------------------------------------------------------------------------
                                            0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
*                                           0000 0001  0000 0001  0000 0001  0000 0001  0000 0001 (0x0101010101)
-------------------------------------------------------------------------------------------------
                                            0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
                                 0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
                      0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
           0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
0000 d000  h000 0c00  0g00 00b0  00f0 000a  000e 0000
-------------------------------------------------------------------------------------------------
0000 d000  h000 dc00  hg00 dcb0  hgf0 dcba  hgfe dcba  hgfe 0cba  0gfe 00ba  00fe 000a  000e 0000
>> 32
-------------------------------------------------------------------------------------------------
                                            0000 d000  h000 dc00  hg00 dcb0  hgf0 dcba  hgfe dcba  
&                                                                                       1111 1111
-------------------------------------------------------------------------------------------------
                                                                                        hgfe dcba
Notez que les deux dernières étapes peuvent être combinés sur certains processeurs, car les registres sont accessibles sous forme d’octets ; multipliez simplement afin qu’un registre stocke les 32 bits supérieurs du résultat et de la prendre l’octet de poids faible. Ainsi, il peut prendre seulement 6 opérations.
Conçu par Sean Anderson, 13 juillet 2001.

Inverser les bits dans un octet avec 7 opérations (pas de 64-bit) :

b = ((b * 0x0802LU & 0x22110LU) | (b * 0x8020LU & 0x88440LU)) * 0x10101LU >> 16 ;
Veillez à attribuer ou effectuer un cast du résultat en un unsigned char pour enlever les ordures dans les bits supérieurs. Conçu par Sean Anderson, 13 juillet 2001. Typo repéré et correction fournie par Mike Keith, 3 janvier 2002.

Inverser une quantité de N bits en parallèle en 5 * opérations de lg(N) :

unsigned int v; // 32-bit word to reverse bit order

// swap odd and even bits
v = ((v >> 1) & 0x55555555) | ((v & 0x55555555) << 1);
// swap consecutive pairs
v = ((v >> 2) & 0x33333333) | ((v & 0x33333333) << 2);
// swap nibbles …
v = ((v >> 4) & 0x0F0F0F0F) | ((v & 0x0F0F0F0F) << 4);
// swap bytes
v = ((v >> 8) & 0x00FF00FF) | ((v & 0x00FF00FF) << 8);
// swap 2-byte long pairs
v = ( v >> 16             ) | ( v               << 16);

La variation suivante est aussi O(lg(N)), mais il nécessite des opérations plus revenir sur v. Sa vertu est en prenant le moins de mémoire légèrement en calculant les constantes à la volée.unsigned int s = sizeof(v) * CHAR_BIT; // bit size; must be power of 2
unsigned int mask = ~0;
while ((s >>= 1) > 0)
{
mask ^= (mask << s);
v = ((v >> s) & mask) | ((v << s) & ~mask);
}
Ces méthodes ci-dessus conviennent le mieux aux situations N est grand. Si vous utilisez ce qui précède avec les entiers 64 bits (ou plus), puis vous devez ajouter plusieurs lignes (suivant le modèle) ; Sinon, seulement les 32 bits de poids faible se renversera et le résultat sera dans les 32 bits de poids faible.

Voir Journal 1983 du Dr. Dobb, l’article de Edwin Freed sur les nombres magiques binaire pour plus d’informations. La deuxième variation a été suggérée par Ken Raeburn le 13 septembre 2005. Veldmeijer a mentionné que la première version pourrait faire sans PADN dans la dernière ligne sur 19 mars 2006.

Calculer la division modulo par 1 << s sans un opérateur de division

const unsigned int n;          // numerator
const unsigned int s;
const unsigned int d = 1U << s; // So d will be one of: 1, 2, 4, 8, 16, 32, …
unsigned int m;                // m will be n % d
m = n & (d – 1);

La plupart des programmeurs apprennent ce truc au début, mais il a été inscrit par souci d’exhaustivité.


Calculer la division modulo par (1 << s)1 sans un opérateur de division

unsigned int n;                      // numerator
const unsigned int s;                // s > 0
const unsigned int d = (1 << s) – 1; // so d is either 1, 3, 7, 15, 31, …).
unsigned int m;                      // n % d goes here.

for (m = n; n > d; n = m)
{
for (m = 0; n; n >>= s)
{
m += n & d;
}
}
// Now m is a value from 0 to d, but since with modulus division
// we want m to be 0 when it is d.
m = m == d ? 0 : m;

Cette méthode de division modulo un entier qui est un inférieur à une puissance de 2 prend au plus 5 + (4 + 5 * ceil(N / s)) * ceil (lg(N / s)) opérations, N est le nombre de bits dans le numérateur. En d’autres termes, il faut au plus de O (N * lg(N)) temps.
Conçu par Sean Anderson, 15 août 2001. Avant que Sean A. Irvine m’a corrigé le 17 juin 2004, j’ai commenté par erreur que nous pourrions vous pouvez également assigner m = ((m + 1) & d) 1 ; à la fin. Michael Miller a repéré une faute de frappe dans le code du 25 avril 2005.

Calculer la division modulo par (1 << s)1 en parallèle sans un opérateur de division

Ce qui suit est d’une taille de mot de 32 bits !
// The following is for a word size of 32 bits!

static const unsigned int M[] =
{
0x00000000, 0x55555555, 0x33333333, 0xc71c71c7,
0x0f0f0f0f, 0xc1f07c1f, 0x3f03f03f, 0xf01fc07f,
0x00ff00ff, 0x07fc01ff, 0x3ff003ff, 0xffc007ff,
0xff000fff, 0xfc001fff, 0xf0003fff, 0xc0007fff,
0x0000ffff, 0x0001ffff, 0x0003ffff, 0x0007ffff,
0x000fffff, 0x001fffff, 0x003fffff, 0x007fffff,
0x00ffffff, 0x01ffffff, 0x03ffffff, 0x07ffffff,
0x0fffffff, 0x1fffffff, 0x3fffffff, 0x7fffffff
};

static const unsigned int Q[][6] =
{
{ 0,  0,  0,  0,  0,  0}, {16,  8,  4,  2,  1,  1}, {16,  8,  4,  2,  2,  2},
{15,  6,  3,  3,  3,  3}, {16,  8,  4,  4,  4,  4}, {15,  5,  5,  5,  5,  5},
{12,  6,  6,  6 , 6,  6}, {14,  7,  7,  7,  7,  7}, {16,  8,  8,  8,  8,  8},
{ 9,  9,  9,  9,  9,  9}, {10, 10, 10, 10, 10, 10}, {11, 11, 11, 11, 11, 11},
{12, 12, 12, 12, 12, 12}, {13, 13, 13, 13, 13, 13}, {14, 14, 14, 14, 14, 14},
{15, 15, 15, 15, 15, 15}, {16, 16, 16, 16, 16, 16}, {17, 17, 17, 17, 17, 17},
{18, 18, 18, 18, 18, 18}, {19, 19, 19, 19, 19, 19}, {20, 20, 20, 20, 20, 20},
{21, 21, 21, 21, 21, 21}, {22, 22, 22, 22, 22, 22}, {23, 23, 23, 23, 23, 23},
{24, 24, 24, 24, 24, 24}, {25, 25, 25, 25, 25, 25}, {26, 26, 26, 26, 26, 26},
{27, 27, 27, 27, 27, 27}, {28, 28, 28, 28, 28, 28}, {29, 29, 29, 29, 29, 29},
{30, 30, 30, 30, 30, 30}, {31, 31, 31, 31, 31, 31}
};

static const unsigned int R[][6] =
{
{0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000001, 0x00000001},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x00000003, 0x00000003, 0x00000003},
{0x00007fff, 0x0000003f, 0x00000007, 0x00000007, 0x00000007, 0x00000007},
{0x0000ffff, 0x000000ff, 0x0000000f, 0x0000000f, 0x0000000f, 0x0000000f},
{0x00007fff, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f, 0x0000001f},
{0x00000fff, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f, 0x0000003f},
{0x00003fff, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f, 0x0000007f},
{0x0000ffff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff, 0x000000ff},
{0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff, 0x000001ff},
{0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff, 0x000003ff},
{0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff, 0x000007ff},
{0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff, 0x00000fff},
{0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff, 0x00001fff},
{0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff, 0x00003fff},
{0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff, 0x00007fff},
{0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff, 0x0000ffff},
{0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff, 0x0001ffff},
{0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff, 0x0003ffff},
{0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff, 0x0007ffff},
{0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff, 0x000fffff},
{0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff, 0x001fffff},
{0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff, 0x003fffff},
{0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff, 0x007fffff},
{0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff, 0x00ffffff},
{0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff, 0x01ffffff},
{0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff, 0x03ffffff},
{0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff, 0x07ffffff},
{0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff, 0x0fffffff},
{0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff},
{0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff, 0x3fffffff},
{0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff, 0x7fffffff}
};

unsigned int n;       // numerator
const unsigned int s; // s > 0
const unsigned int d = (1 << s) – 1; // so d is either 1, 3, 7, 15, 31, …).
unsigned int m;       // n % d goes here.

m = (n & M[s]) + ((n >> s) & M[s]);

for (const unsigned int * q = &Q[s][0], * r = &R[s][0]; m > d; q++, r++)
{
m = (m >> *q) + (m & *r);
}
m = m == d ? 0 : m; // OR, less portably: m = m & -((signed)(m – d) >> s);

Cette méthode pour trouver la division modulo un entier qui est un de moins d’un puissance de 2 prend à O(lg(N)) la plupart du temps, N est le nombre de bits dans le numérateur (32 bits, pour le code ci-dessus). Le nombre d’opérations est tout au plus 12 + 9 * ceil(lg(N)). Les tableaux peuvent être enlevées si vous connaissez le dénominateur au moment de la compilation ; juste extraire le peu d’entrées relevent et dérouler la boucle. Il peut être facilement étendu à plus de bits.
Il trouve le résultat en additionnant les valeurs de base (1 << s) en parallèle. Première toutes les autres bases (1 << s) est la valeur ajoutée à la précédente. Imaginer que le résultat est écrit sur un morceau de papier. Couper le papier en deux, afin que la moitié des valeurs sont sur chaque pièce coupée. Aligner les valeurs et les additionnez sur une nouvelle feuille de papier. Répéter en coupant ce papier en deux (ce qui sera un quart de la taille de la précédente) et en additionnant, jusqu’à ce que vous ne pouvez pas couper plus loin. Après que lg(N/s/2) des réductions, nous découpons pas plus ; juste continuer à ajouter les valeurs et mettre le résultat sur une nouvelle feuille de papier comme avant, bien qu’il existe au moins deux valeurs de s-bit.
Conçu par Sean Anderson, 20 août 2001. Une faute de frappe a été repéré par Randy E. Bryant le 3 mai 2005 (après le collage le code, j’avais ajouté plus tard “unsinged” à une déclaration de variable). Comme dans le précédent hack, j’ai commenté par erreur que nous pourrions vous pouvez également assigner m = ((m + 1) & d) 1 ; à la fin, et Don Knuth me corrigé le 19 avril 2006 et a proposé de m = m &-((signed)(m-d) >> s). Le 18 juin 2009 Sean Irvine a proposé un changement qui utilisé ((n >> s) & M[s]) au lieu de ((n & ~M[s]) >> s), qui nécessite généralement moins d’opérations car la constante M [s] est déjà chargée.

Trouver le log base 2 d’un entier avec la série MSB N en o (n) opérations (la manière évidente)

unsigned int v; // 32-bit word to find the log base 2 of
unsigned int r = 0; // r will be lg(v)

while (v >>= 1) // unroll for more speed…
{
r++;
}

Le journal base 2 d’un nombre entier est identique à la position du bit est défini plus haut (ou plus importantes bit défini, MSB). Les méthodes suivantes log base 2 sont plus rapides que celui-ci.


Trouver le journal entier base 2 d’un nombre entier avec un flotteur de IEEE 64 bits

int v; // 32-bit integer to find the log base 2 of

int r; // result of log_2(v) goes here
union { unsigned int u[2]; double d; } t; // temp

t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] = 0x43300000;
t.u[__FLOAT_WORD_ORDER!=LITTLE_ENDIAN] = v;
t.d -= 4503599627370496.0;
r = (t.u[__FLOAT_WORD_ORDER==LITTLE_ENDIAN] >> 20) – 0x3FF;

Le code ci-dessus charge double (à virgule flottante IEEE-754) 64-bit avec un entier de 32 bits (avec aucun bit paddding) en stockant l’entier dans la mantisse, l’exposant est fixée à 252. De cette double nouvellement frappée, 252 (exprimés en tant que double) est soustraite, qui définit l’exposant qui en résulte dans le journal de la base 2 de la valeur d’entrée, v. Tout ce qui reste est décalage de bits exposants en position (20 bits à droite) et en soustrayant la partialité, 0x3FF (ce qui est de 1023 décimal). Cette technique ne prend que 5 opérations, mais plusieurs UC est lents à manipuler les doubles et les boutien de l’architecture doit être logés.

Eric Cole m’a envoyé le 15 janvier 2006. Evan Felix fait remarquer une faute de frappe sur le 4 avril 2006. Vincent Lefèvre m’a dit le 9 juillet 2008 pour modifier le contrôle endian pour utiliser endian de flotteur, qui pourrait différer d’endian de l’entier.

Trouver le log base 2 d’un entier avec une table de choix

static const char LogTable256[256] =
{
#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, n
-1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3,
LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6),
LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)
};

unsigned int v; // 32-bit word to find the log of
unsigned r;     // r will be lg(v)
register unsigned int t, tt; // temporaries

if (tt = v >> 16)
{
r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];
}
else
{
r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];
}

La méthode de table de recherche prend seulement environ 7 opérations pour trouver le journal d’une valeur de 32 bits. Si étendu pour les quantités de 64 bits, il faudrait environ 9 opérations. Une autre opération peut être parée en utilisant quatre tables, avec les ajouts possibles intégrées à chacun. À l’aide d’éléments de table int peut être plus rapide, en fonction de votre architecture.
Le code ci-dessus est accordé aux valeurs de sortie uniformément distribuée. Si vos apports sont réparties uniformément dans l’ensemble de toutes les valeurs de 32 bits, alors envisager d’utiliser le texte suivant :

if (tt = v >> 24)
{
r = 24 + LogTable256[tt];
}
else if (tt = v >> 16)
{
r = 16 + LogTable256[tt];
}
else if (tt = v >> 8)
{
r = 8 + LogTable256[tt];
}
else
{
r = LogTable256[v];
}

Au départ de générer la table du journal par algorithme :
LogTable256[0] = LogTable256[1] = 0;
for (int i = 2; i < 256; i++)
{
LogTable256[i] = 1 + LogTable256[i / 2];
}
LogTable256[0] = -1; // if you want log(0) to return -1
Behdad Esfahbod et j’ai rasé une fraction d’une opération (en moyenne) sur 18 mai 2005. Encore une autre fraction d’une opération est démises le 14 novembre 2006 par Emanuel Hoogeveen. Butterfield a suggéré la variation qui est accordée aux valeurs d’entrée uniformément réparties sur le 19 septembre 2008. Venkat Reddy m’a dit le 5 janvier 2009 que log doit retourner -1 pour indiquer une erreur, alors j’ai changé la première entrée dans la table à celui.


Trouver le log base 2 d’un entier N bits dans les opérations de O(lg(N))

unsigned int v;  // 32-bit value to find the log2 of
const unsigned int b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000};
const unsigned int S[] = {1, 2, 4, 8, 16};
int i;

register unsigned int r = 0; // result of log2(v) will go here
for (i = 4; i >= 0; i–) // unroll for speed…
{
if (v & b[i])
{
v >>= S[i];
r |= S[i];
}
}

// OR (IF YOUR CPU BRANCHES SLOWLY):

unsigned int v;             // 32-bit value to find the log2 of
register unsigned int r; // result of log2(v) will go here
register unsigned int shift;

r =     (v > 0xFFFF) << 4; v >>= r;
shift = (v > 0xFF  ) << 3; v >>= shift; r |= shift;
shift = (v > 0xF   ) << 2; v >>= shift; r |= shift;
shift = (v > 0x3   ) << 1; v >>= shift; r |= shift;
r |= (v >> 1);

// OR (IF YOU KNOW v IS A POWER OF 2):

unsigned int v;  // 32-bit value to find the log2 of
static const unsigned int b[] = {0xAAAAAAAA, 0xCCCCCCCC, 0xF0F0F0F0,
0xFF00FF00, 0xFFFF0000};
register unsigned int r = (v & b[0]) != 0;
for (i = 4; i > 0; i–) // unroll for speed…
{
r |= ((v & b[i]) != 0) << i;
}

Bien sûr, pour étendre le code pour trouver le journal d’un certain nombre de 33 à 64 bits, nous ajouter un autre élément, 0xFFFFFFFF00000000, à b, ajouter 32 à S et une boucle allant de 5 à 0. Cette méthode est beaucoup plus lente que la version antérieure de la table-liste de choix, mais si vous ne voulez pas grande table ou votre architecture est lent pour accéder à une mémoire, c’est un bon choix. La deuxième variation implique des opérations un peu plus, mais il peut être plus rapide sur les machines avec des coûts d’agences élevé (p. ex. PowerPC).
La deuxième version a été envoyée à moi par Eric Cole le 7 janvier 2006. Par la suite, Andrew Shapira garnis de quelques opérations hors de lui et m’a envoyé sa variante (ci-dessus) le 1er septembre 2007. La troisième variation m’a été suggérée par John Owens sur 24 avril 2002 ; Il est plus rapide, mais il convient uniquement lorsque l’entrée est connue pour être une puissance de 2. Le 25 mai 2003, Ken Raeburn suggéra améliorant le cas général en utilisant un plus petit nombre de b [], qui se chargent plus rapidement sur certaines architectures (par exemple, si la taille du mot est 16 bits, puis charge qu’une seule instruction peut être nécessaire). Ces valeurs fonctionnent pour la version générale, mais pas pour la version spécial dessous, v est une puissance de 2 ; Glenn Slayden introduit cet oubli à mon attention le 12 décembre 2003.

Trouver le log base 2 d’un entier N bits dans les opérations de O(lg(N)) avec multiply et recherche

uint32_t v; // find the log base 2 of 32-bit v
int r;      // result goes here

static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};

v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;

r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];

Le code ci-dessus calcule le log base 2 d’un entier de 32 bits avec une recherche de la petite table et se multiplient. Il ne demande que 13 opérations contre (jusqu’à) 20 pour la méthode précédente. La méthode purement basée sur des tables requiert le moins d’opérations, mais cela offre un compromis raisonnable entre la vitesse et la taille de la table.
Si vous savez que v est une puissance de 2, alors vous avez seulement besoin de ce qui suit :

static const int MultiplyDeBruijnBitPosition2[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition2[(uint32_t)(v * 0x077CB531U) >> 27];

Eric Cole a conçu ce 8 janvier 2006 après avoir lu l’entrée ci-dessous pour arrondir à une puissance de 2 et de la méthode ci-dessous pour calculer le nombre de bits de fin avec un multiply et recherche à l’aide d’une séquence DeBruijn. Le 10 décembre 2009, Mark Dickinson a rasé quelques opérations en exigeant v arrondi à un de moins que la puissance de 2 suivante plutôt que la puissance de 2.


Trouver le journal entier base 10 d’un entier

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of
int r;          // result goes here
int t;          // temporary

static unsigned int const PowersOf10[] =
{1, 10, 100, 1000, 10000, 100000,
1000000, 10000000, 100000000, 1000000000};

t = (IntegerLogBase2(v) + 1) * 1233 >> 12; // (use a lg2 method from above)
r = t – (v < PowersOf10[t]);

L’entier log base 10 est calculée en premier en utilisant une des techniques ci-dessus pour trouver le log base 2. Par la relation log10(v) = log2(v) / log2(10), il faut multiplier par 1/log2(10), qui est approximativement 1233/4096, ou 1233 suivie d’un décalage de 12 vers la droite. En ajoutant un est nécessaire parce que la IntegerLogBase2 s’arrondit. Enfin, étant donné que la valeur t n’est qu’une approximation qui peut être éteint par l’un, la valeur exacte est obtenue en soustrayant le résultat de v < PowersOf10 [t].

Cette méthode prend 6 opérations plus que IntegerLogBase2. Il peut être accéléré (sur des ordinateurs avec accès à la mémoire rapide) en modifiant la méthode log de base 2-recherche dans la table ci-dessus pour que les entrées de tenir ce qui est calculé pour t (c’est-à-dire avant d’ajouter, – multiplier et – décaler). Cela nécessiterait un total de seulement 9 opérations pour trouver le log base 10, en supposant que 4 tables ont été utilisés (un pour chaque octet de v).
Eric Cole a suggéré de qu’ajouter une version de ceci le 7 janvier 2006.

Trouver le journal entier base 10 d’un nombre entier la manière évidente

unsigned int v; // non-zero 32-bit integer value to compute the log base 10 of
int r;          // result goes here

r = (v >= 1000000000) ? 9 : (v >= 100000000) ? 8 : (v >= 10000000) ? 7 :
(v >= 1000000) ? 6 : (v >= 100000) ? 5 : (v >= 10000) ? 4 :
(v >= 1000) ? 3 : (v >= 100) ? 2 : (v >= 10) ? 1 : 0;

Cette méthode fonctionne bien lorsque l’entrée est uniformément répartie sur 32 bits valeurs parce que 76 % des entrées sont captées par la première comparaison, 21 % sont captées par le deuxième comparer, 2 % sont captées par le troisième et ainsi de suite (hacher le reste vers le bas de 90 % avec chaque comparaison). Ainsi, moins de 2,6 opérations sont nécessaires en moyenne.

Le 18 avril 2007, Emanuel Hoogeveen a suggéré une variante sur celui-ci, les conditions utilisées divisions, qui n’étaient pas aussi rapides que les comparaisons simples.

Trouver le journal entier base 2 d’un flotteur de IEEE 32 bits

const float v; // find int(log2(v)), where v > 0.0 && finite(v) && isnormal(v)
int c;         // 32-bit int c gets the result;

c = *(const int *) &v;  // OR, for portability:  memcpy(&c, &v, sizeof c);
c = (c >> 23) – 127;

Ce qui précède est rapide, mais utilisent les architectures 754-compatible IEEE subnormal (également appelé denormal) nombres à virgule flottante. Ceux-ci ont les bits d’exposant mis zéro (ce qui signifie pow(2,-127)) et la mantisse n’est pas normalisé, alors elle contient des zéros non significatifs et donc les log2 doit être calculé à partir de la mantisse. Pour tenir compte du nombre inférieur à la normale, procédez comme suit :const float v;              // find int(log2(v)), where v > 0.0 && finite(v)
int c;                      // 32-bit int c gets the result;
int x = *(const int *) &v;  // OR, for portability:  memcpy(&x, &v, sizeof x);

c = x >> 23;

if (c)
{
c -= 127;
}
else
{ // subnormal, so recompute using mantissa: c = intlog2(x) – 149;
register unsigned int t; // temporary
// Note that LogTable256 was defined earlier
if (t = x >> 16)
{
c = LogTable256[t] – 133;
}
else
{
c = (t = x >> 8) ? LogTable256[t] – 141 : LogTable256[x] – 149;
}
}

Le 20 juin 2004, Sean A. Irvine a suggéré que j’inclure du code pour gérer les nombres inférieur à la normale. Sur 11 juin 2005, Falk Hüffner a souligné que l’ISO C99 6,5/7 spécifié un comportement non défini pour le commun de type fait idiome *(int *) &, bien qu’il ait travaillé sur 99,9 % des compilateurs C. Il a proposé d’utiliser memcpy pour une portabilité maximale ou une union avec un flotteur et un int pour la génération de code mieux que memcpy sur certains compilateurs.


Trouver le journal entier base 2 de la pow(2, r)-racine d’un flotteur de IEEE 32 bits (pour r de l’entier non signé)

const int r;
const float v; // find int(log2(pow((double) v, 1. / pow(2, r)))),
// where isnormal(v) and v > 0
int c;         // 32-bit int c gets the result;

c = *(const int *) &v;  // OR, for portability:  memcpy(&c, &v, sizeof c);
c = ((((c – 0x3f800000) >> r) + 0x3f800000) >> 23) – 127;

Ainsi, si r vaut 0, par exemple, nous avons c = v int(log2((double))). Si r est 1, alors nous avons c = v int(log2(sqrt((double)))). Si r est 2, alors nous avons c = v int(log2(pow((double), 1. / 4))).

Sur 11 juin 2005, Falk Hüffner indiqué sur cet ISO C99 6.5/7 à gauche le type fait idiome *(int *) & indéfini, et il a suggéré d’utiliser memcpy.

Compter les consécutives bits zéro (fuite) sur la droite linéaire

unsigned int v;  // input to count trailing zero bits
int c;  // output: c will count v’s trailing zero bits,
// so if v is 1101000 (base 2), then c will be 3
if (v)
{
v = (v ^ (v – 1)) >> 1;  // Set v’s trailing 0s to 1s and zero rest
for (c = 0; v; c++)
{
v >>= 1;
}
}
else
{
c = CHAR_BIT * sizeof(v);
}

Le nombre moyen de fuite les bits à zéro dans un nombre binaire aléatoire (uniformément réparti) est l’un, donc cette solution O (les zéros à droite) n’est pas si mauvais par rapport aux méthodes plus rapides ci-dessous.
Jim Cole a suggéré de qu’ajouter une méthode linéaire-temps pour compter les zéros de fin le 15 août 2007. Le 22 octobre 2007, Jason Cunningham a fait remarquer que j’avais négligé de coller le modificateur non signé pour v.

Compter les consécutives bits zéro (fuite) sur la droite en parallèle

unsigned int v;      // 32-bit word input to count zero bits on right
unsigned int c = 32; // c will be the number of zero bits on the right
v &= -signed(v);
if (v) c–;
if (v & 0x0000FFFF) c -= 16;
if (v & 0x00FF00FF) c -= 8;
if (v & 0x0F0F0F0F) c -= 4;
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;

Ici, nous faisons essentiellement les mêmes opérations que trouver le log base 2 en parallèle, mais nous tout d’abord isoler le bit 1 plus bas et puis poursuivez le c à partir de la valeur maximale et la diminution. Le nombre d’opérations est tout au plus 3 * lg(N) + 4, grosso modo, pour N bits de mots.

Bill Burdick a suggéré d’optimisation, réduction d’heures de 4 * lg(N) le 4 février 2011.

Compter les consécutives bits zéro (fuite) sur le droit de recherche binaire

unsigned int v;     // 32-bit word input to count zero bits on right
unsigned int c;     // c will be the number of zero bits on the right,
// so if v is 1101000 (base 2), then c will be 3
// NOTE: if 0 == v, then c = 31.
if (v & 0x1)
{
// special case for odd v (assumed to happen half of the time)
c = 0;
}
else
{
c = 1;
if ((v & 0xffff) == 0)
{
v >>= 16;
c += 16;
}
if ((v & 0xff) == 0)
{
v >>= 8;
c += 8;
}
if ((v & 0xf) == 0)
{
v >>= 4;
c += 4;
}
if ((v & 0x3) == 0)
{
v >>= 2;
c += 2;
}
c -= v & 0x1;
}
Le code ci-dessus est similaire à la méthode précédente, mais il calcule le nombre de zéros de fin par accumulation c d’une manière semblable à la recherche binaire. Dans la première étape, il vérifie si le fond de v 16 bits sont des zéros et dans l’affirmative, les déplacements droite v 16 bits et ajoute 16 c, ce qui réduit le nombre de bits dans v à considérer par moitié. Chacune des étapes subséquentes conditionnelles de même diminue de moitié le nombre de bits jusqu’à ce qu’il y a seulement 1. Cette méthode est plus rapide que le précédent (d’environ 33 %), parce que les organes de l’if, les instructions sont exécutées moins souvent.
Matt Whitlock a suggéré ceci sur 25 janvier 2006. Andrew Shapira rasé quelques opérations sur 5 septembre 2007 (en définissant c = 1 et en soustrayant inconditionnellement à la fin).

Compter les consécutives bits zéro (fuite) sur la droite en castant en float

unsigned int v;            // find the number of trailing zeros in v
int r;                     // the result goes here
float f = (float)(v & -v); // cast the least significant bit in v to a float
r = (*(uint32_t *)&f >> 23) – 0x7f;

Même si cela prend seulement environ 6 opérations, le temps de convertir un entier en float peut être élevé sur certaines machines. L’exposant de la représentation de point flottante 32 bits IEEE est déplacée vers le bas, et le parti pris est soustraite pour donner la position de la 1 bit le moins significatif en v. Si v est égal à zéro, le résultat est -127.

Compter les consécutives bits zéro (fuite) sur la droite avec la division modulo et recherche

unsigned int v;  // find the number of trailing zeros in v
int r;           // put the result in r
static const int Mod37BitPosition[] = // map a bit value mod 37 to its position
{
32, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 30, 28, 11, 0, 13, 4,
7, 17, 0, 25, 22, 31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5,
20, 8, 19, 18
};
r = Mod37BitPosition[(-v & v) % 37];

Le code ci-dessus recherche le nombre de zéros qui sont en fuite à droite, donc binaire 0100 produirait 2. Il utilise le fait que les premières valeurs de position de 32 bits sont relativement privilégiées avec 37, afin d’effectuer une division modulo avec 37 donne un numéro unique de 0 à 36 pour chacun. Ces chiffres peuvent ensuite être mappé sur le nombre de zéros à l’aide d’une petite table. Il utilise seulement 4 opérations, toutefois d’indexation dans un tableau et d’effectuer une division modulo peut rendre impropre à certaines situations. J’ai venu à ceci indépendamment puis cherché une sous-séquence des valeurs du tableau et trouvé qu’il a été inventé plus tôt par Reiser, selon Delight de Hacker.


Compter les consécutives bits zéro (fuite) sur la droite avec multiply et recherche

unsigned int v;  // find the number of trailing zeros in 32-bit v
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

Conversion des vecteurs de bits aux indices de bits set est un exemple d’utilisation pour cela. Elle nécessite une opération plus que la division modulo impliquant un plus tôt, mais la multiplication peut être plus rapide. L’expression (v & – v) extrait le bit 1 v. La constante 0x077CB531UL est une séquence de Bruijn, qui produit un unique modèle de bits dans les 5 bits de poids fort pour chaque position de bit possible qui elle est multipliée contre. Quand il n’y a aucun ensemble de bits, il retourne 0. Vous trouverez plus d’informations en lisant le papier à l’aide de Bruijn séquences à l’Index 1 dans un mot ordinateur par Charles E. Leiserson, Harald Prokof et Keith H. Randall.

Le 8 octobre 2005 Andrew Shapira a suggéré que j’ai ajouter ceci. Dustin Spicuzza m’a demandé le 14 avril 2009 pour effectuer un cast du résultat de la multiplier à un type de 32 bits, donc cela fonctionne lorsqu’il est compilé avec les entiers 64 bits.

Arrondir à la prochaine plus haute puissance de 2 par moulage de flotteur

const unsigned int v ; Autour de cette valeur de 32 bits à la prochaine plus haute puissance de 2

unsigned int const v; // Round this 32-bit value to the next highest power of 2
unsigned int r;       // Put the result here. (So v=3 -> r=4; v=8 -> r=8)

if (v > 1)
{
float f = (float)v;
unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) – 0x7f);
r = t << (t < v);
}
else
{
r = 1;
}

Le code ci-dessus utilise 8 opérations, mais fonctionne sur tous les v < = (1 << 31).

Version rapide et sale, pour domaine de 1 < v < (1 << 25) :
float f = (float)(v – 1);

r = 1U << ((*(unsigned int*)(&f) >> 23) – 126);

Bien que la version rapide et sale utilise uniquement des opérations autour de 6, c’est à peu près trois fois plus lente que la technique ci-dessous (qui comprend 12 opérations) lorsque comparés sur un CPU Athlon ™ XP 2100 +. Certains processeurs seront comporteront mieux avec elle, cependant.

Le 27 septembre 2005 Andi Smithers a suggéré que je comprend une technique de coulée à flotteurs pour trouver le lg d’un certain nombre d’arrondi vers le haut pour une puissance de 2. Similaire à la version rapide et sale ici, sa version a travaillé avec les valeurs inférieure à (1 << 25), en raison de la mantisse arrondi, mais c’était une opération plus.

Arrondir à la prochaine plus haute puissance de 2

unsigned int v ; calculer la puissance la plus élevée suivante 2 de 32 bits v
v–;
v |= v >> 1;
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
v++;
Dans 12 opérations, copiez le code suivant calcule la prochaine plus haute puissance de 2 pour un entier de 32 bits. Le résultat peut être exprimé par la formule 1U << (lg (v 1) + 1). Notez que dans le cas de bord v est à 0, elle retourne 0, ce qui n’est pas une puissance de 2 ; vous pourriez ajouter l’expression v += (v == 0) pour y remédier, si c’est important. Il serait plus rapide de 2 opérations d’utiliser la formule et la méthode 2 log base qui utilise une table de choix, mais dans certaines situations, tables de choix ne sont pas adaptés, le code ci-dessus peut être le meilleur. (Sur un Athlon ™ XP 2100 +, j’ai trouvé la Maj ci-dessus à gauche et puis code OR est aussi rapide qu’à l’aide d’une seule instruction de langage d’assemblage de la BSR, qui scanne en sens inverse pour trouver le bit set le plus élevé.) Il fonctionne en copiant le bit set le plus élevé de tous les bits de poids faible, puis en ajoutant un, qui se traduit par la porte que tous les bits de poids faible valeur 0 et un peu au-delà de la plus haut bit set à 1. Si le numéro d’origine était une puissance de 2, puis la décrémentation réduira il à un de moins, pour que nous arrondir à la valeur d’origine même.
Vous pourriez calculer alternativement la prochaine puissance supérieure de 2 opérations seulement 8 ou 9 en utilisant une table de recherche pour floor(lg(v)) et puis l’évaluation 1<<(1+floor(lg(v))) ; Atul Divekar suggéré que je mentionne cela le 5 septembre 2010.
Conçu par Sean Anderson, septembre 14, 2001. Pete Hart m’a signalé quelques messages de groupe de discussion par lui et William Lewis en février 1997, ils arrivent sur le même algorithme.

Interleave bits la manière évidente

unsigned short x;   // Interleave bits of x and y, so that all of the
unsigned short y;   // bits of x are in the even positions and y in the odd;
unsigned int z = 0; // z gets the resulting Morton Number.

for (int i = 0; i < sizeof(x) * CHAR_BIT; i++) // unroll for more speed…
{
z |= (x & 1U << i) << i | (y & 1U << i) << (i + 1);
}

Bits entrelacés (aka les numéros de Morton) sont utiles pour linéarisant coordonnées entières 2D, donc x et y sont combinés en un chiffre unique qui peut être comparé facilement et a la propriété qui a un certain nombre est habituellement à proximité un autre leur x et les valeurs y sont proches.

Interleave bits par recherche dans la table
static const unsigned short MortonTable256[256] =
{
0x0000, 0x0001, 0x0004, 0x0005, 0x0010, 0x0011, 0x0014, 0x0015,
0x0040, 0x0041, 0x0044, 0x0045, 0x0050, 0x0051, 0x0054, 0x0055,
0x0100, 0x0101, 0x0104, 0x0105, 0x0110, 0x0111, 0x0114, 0x0115,
0x0140, 0x0141, 0x0144, 0x0145, 0x0150, 0x0151, 0x0154, 0x0155,
0x0400, 0x0401, 0x0404, 0x0405, 0x0410, 0x0411, 0x0414, 0x0415,
0x0440, 0x0441, 0x0444, 0x0445, 0x0450, 0x0451, 0x0454, 0x0455,
0x0500, 0x0501, 0x0504, 0x0505, 0x0510, 0x0511, 0x0514, 0x0515,
0x0540, 0x0541, 0x0544, 0x0545, 0x0550, 0x0551, 0x0554, 0x0555,
0x1000, 0x1001, 0x1004, 0x1005, 0x1010, 0x1011, 0x1014, 0x1015,
0x1040, 0x1041, 0x1044, 0x1045, 0x1050, 0x1051, 0x1054, 0x1055,
0x1100, 0x1101, 0x1104, 0x1105, 0x1110, 0x1111, 0x1114, 0x1115,
0x1140, 0x1141, 0x1144, 0x1145, 0x1150, 0x1151, 0x1154, 0x1155,
0x1400, 0x1401, 0x1404, 0x1405, 0x1410, 0x1411, 0x1414, 0x1415,
0x1440, 0x1441, 0x1444, 0x1445, 0x1450, 0x1451, 0x1454, 0x1455,
0x1500, 0x1501, 0x1504, 0x1505, 0x1510, 0x1511, 0x1514, 0x1515,
0x1540, 0x1541, 0x1544, 0x1545, 0x1550, 0x1551, 0x1554, 0x1555,
0x4000, 0x4001, 0x4004, 0x4005, 0x4010, 0x4011, 0x4014, 0x4015,
0x4040, 0x4041, 0x4044, 0x4045, 0x4050, 0x4051, 0x4054, 0x4055,
0x4100, 0x4101, 0x4104, 0x4105, 0x4110, 0x4111, 0x4114, 0x4115,
0x4140, 0x4141, 0x4144, 0x4145, 0x4150, 0x4151, 0x4154, 0x4155,
0x4400, 0x4401, 0x4404, 0x4405, 0x4410, 0x4411, 0x4414, 0x4415,
0x4440, 0x4441, 0x4444, 0x4445, 0x4450, 0x4451, 0x4454, 0x4455,
0x4500, 0x4501, 0x4504, 0x4505, 0x4510, 0x4511, 0x4514, 0x4515,
0x4540, 0x4541, 0x4544, 0x4545, 0x4550, 0x4551, 0x4554, 0x4555,
0x5000, 0x5001, 0x5004, 0x5005, 0x5010, 0x5011, 0x5014, 0x5015,
0x5040, 0x5041, 0x5044, 0x5045, 0x5050, 0x5051, 0x5054, 0x5055,
0x5100, 0x5101, 0x5104, 0x5105, 0x5110, 0x5111, 0x5114, 0x5115,
0x5140, 0x5141, 0x5144, 0x5145, 0x5150, 0x5151, 0x5154, 0x5155,
0x5400, 0x5401, 0x5404, 0x5405, 0x5410, 0x5411, 0x5414, 0x5415,
0x5440, 0x5441, 0x5444, 0x5445, 0x5450, 0x5451, 0x5454, 0x5455,
0x5500, 0x5501, 0x5504, 0x5505, 0x5510, 0x5511, 0x5514, 0x5515,
0x5540, 0x5541, 0x5544, 0x5545, 0x5550, 0x5551, 0x5554, 0x5555
};

unsigned short x; // Interleave bits of x and y, so that all of the
unsigned short y; // bits of x are in the even positions and y in the odd;
unsigned int z;   // z gets the resulting 32-bit Morton Number.

z = MortonTable256[y >> 8]   << 17 |
MortonTable256[x >> 8]   << 16 |
MortonTable256[y & 0xFF] <<  1 |
MortonTable256[x & 0xFF];

Pour plus de vitesse, utilisez un tableau complémentaire avec les valeurs qui sont que mortontable256 préalablement déplacé un bit vers la gauche. Cette deuxième table pourrait alors servir pour les recherches de y, ce qui réduit les opérations par deux, mais presque doubler la mémoire requise. Étendre cette idée même, quatre tables permettait, avec deux d’entre eux avant décalés de 16 à gauche des deux précédentes, alors que nous aurions besoin seulement 11 opérations total.

Interleave multiplier les bits avec 64-bit

Dans les 11 opérations, cette version entrelace des morceaux de deux octets (plutôt que des shorts, comme dans les autres versions), mais beaucoup d’opérations sont 64 bits multiplie donc il n’est pas approprié pour toutes les machines. Les paramètres d’entrée, x et y, devraient être inférieure à 256.

unsigned char x;  // Interleave bits of (8-bit) x and y, so that all of the
unsigned char y;  // bits of x are in the even positions and y in the odd;
unsigned short z; // z gets the resulting 16-bit Morton Number.

z = ((x * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 49) & 0x5555 |
((y * 0x0101010101010101ULL & 0x8040201008040201ULL) *
0x0102040810204081ULL >> 48) & 0xAAAA;

Holger Bettag a été inspiré de proposer cette technique sur 10 octobre 2004 après avoir lu les inversions de base se multiplient peu ici.


Entrelacement de bits par des nombres binaires Magic

static const unsigned int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF};
static const unsigned int S[] = {1, 2, 4, 8};

unsigned int x; // Interleave lower 16 bits of x and y, so the bits of x
unsigned int y; // are in the even positions and bits from y in the odd;
unsigned int z; // z gets the resulting 32-bit Morton Number.
// x and y must initially be less than 65536.

x = (x | (x << S[3])) & B[3];
x = (x | (x << S[2])) & B[2];
x = (x | (x << S[1])) & B[1];
x = (x | (x << S[0])) & B[0];

y = (y | (y << S[3])) & B[3];
y = (y | (y << S[2])) & B[2];
y = (y | (y << S[1])) & B[1];
y = (y | (y << S[0])) & B[0];

z = x | (y << 1);

Déterminer si un mot possède un octet nul

Moins d’opérations :

// Fewer operations:
unsigned int v; // 32-bit word to check if any 8-bit byte in it is 0
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);

Le code ci-dessus peut être utile lorsque vous effectuez une copie de la chaîne rapide dans laquelle un mot est copié à la fois. Il utilise 5 opérations. En revanche, tests pour un octet null dans les manières évidentes (qui suivent) ont au moins 7 opérations (lorsqu’il est compté dans la manière plus avare) et au plus 12.// More operations:
bool hasNoZeroByte = ((v & 0xff) && (v & 0xff00) && (v & 0xff0000) && (v & 0xff000000))
// OR:
unsigned char * p = (unsigned char *) &v;
bool hasNoZeroByte = *p && *(p + 1) && *(p + 2) && *(p + 3);
Le code au début de cette section (étiquetée « Moins d’opérations ») objets de la première mise à zéro les bits de poids fort de 4 octets dans le mot. Par la suite, il ajoute un nombre qui entraîne un dépassement de capacité pour la haut bit d’un octet si les bits de poids faible étaient initialement ensemble. Ensuite les bits de poids fort du mot original sont ORed avec ces valeurs ; ainsi, le bit haut d’un octet est défini iff n’importe quel bit dans l’octet a été défini. Enfin, nous déterminons si un de ces bits de poids fort est zéro par ORing avec ceux dans le monde sauf les bits de poids fort et en l’inversant le résultat. S’étendant sur 64 bits est trivial ; tout simplement augmenter les constantes pour être 0x7F7F7F7F7F7F7F7F.

Pour une amélioration supplémentaire, un prétest rapide qui requiert seulement 4 opérations peut-être être réalisé pour déterminer si le mot peut avoir un octet nul. Le test retourne également true si l’octet est 0 x 80, donc il n’y a parfois de faux positifs, mais la version plus lente et plus fiable ci-dessus peut alors servir sur les candidats pour une augmentation globale de vitesse avec une sortie correcte.
bool hasZeroByte = ((v + 0x7efefeff) ^ ~v) & 0x81010100;

if (hasZeroByte) // or may just have 0x80 in the high byte
{
hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);
}

Il existe pourtant une méthode plus rapide utiliser hasless (v, 1), qui est défini ci-dessous ; Il fonctionne en 4 opérations et ne nécessite aucune vérification subsquent. Il se simplifie en

#define haszero(v) (((v) – 0x01010101UL) & ~(v) & 0x80808080UL)
La sous-expression (v 0x01010101UL), évalue à un peu de haut valeur dans n’importe quel octet, chaque fois que l’octet correspondant à v est égal à zéro ou supérieure à 0 x 80. La sous-expression ~ v & 0x80808080UL correspond à la valeur en octets l’octet de v n’a pas son peu élevé (l’octet était donc inférieure à 0 x 80) la valeur des bits de poids fort. Enfin, par ANDing ces deux sous-expressions, qu’il en résulte les bits de poids fort définir les octets dans v étaient nulles, car les bits de poids fort de la valeur en raison d’une valeur supérieures à 0 x 80 dans la première sous-expression sont masquées par le second.
Paul Messmer a suggéré l’amélioration rapide pré-test sur 2 octobre 2004. Juha Järvi suggéré plus tard hasless (v, 1) le 6 avril 2005, qu’il trouvait sur Lab de l’Assemblée de Paul Hsieh ; auparavant, il était écrit dans un post de forum de discussion sur le 27 avril 1987 par Alan Mycroft.

Déterminer si un mot possède un octet égal à n

On peut vouloir savoir si n’importe quel octet en un mot a une valeur spécifique. Pour ce faire, nous pouvons XOR la valeur à tester avec un mot qui a été rempli avec les valeurs d’octets dans lequel nous sommes intéressés. Car XORing une valeur avec lui-même se traduit par un octet nul et non nulle dans le cas contraire, nous pouvons passer le résultat à haszero.

#define hasvalue(x,n) \
(haszero((x) ^ (~0UL/255 * (n))))

Stephen M Bennet proposa cette sur 13 décembre 2009 après avoir lu l’entrée pour haszero.

Déterminer si un mot possède un octet inférieur à n

Tester si un mot x contient un octet non signé avec valeur < n. spécifiquement pour n = 1, il peut être utilisé pour trouver un 0 octet en examinant un long à la fois, ou n’importe quel octet de XOR x avec un masque premier. Utilise 4 opérations arithmétiques/logiques lorsque n est constante.

Requirements: x>=0; 0<=n<=128

#define hasless(x,n) (((x)-~0UL/255*(n))&~(x)&~0UL/255*128)
Pour compter le nombre d’octets dans x inférieurs à n dans 7 opérations, utilisez

#define countless(x,n) \
(((~0UL/255*(127+(n))-((x)&~0UL/255*127))&~(x)&~0UL/255*128)/128%255)

Juha Järvi m’a envoyé cette technique astucieuse sur 6 avril 2005. La macro d’innombrables a été ajoutée par Sean Anderson le 10 avril 2005, inspiré par les countmore de Juha, ci-dessous.

Déterminer si un mot possède un octet supérieur à n

Tester si un mot x contient un octet non signé avec valeur > n. utilise 3 opérations arithmétique/logique lorsque n est constante.

Requirements: x>=0; 0<=n<=127

#define hasmore(x,n) (((x)+~0UL/255*(127-(n))|(x))&~0UL/255*128)
Pour compter le nombre d’octets à x qui sont plus que n 6 opérations, utilisez :

#define countmore(x,n) \
(((((x)&~0UL/255*127)+~0UL/255*(127-(n))|(x))&~0UL/255*128)/128%255)

La macro hasmore a été suggéré par Juha Järvi, le 6 avril 2005, et il a ajouté countmore le 8 avril 2005.

Déterminer si un mot possède un octet entre m et n

Lorsque m < n, cette technique teste si un mot x contient une valeur d’octet non signé, tel que m < valeur < n. Il utilise 7 opérations arithmétique/logiques lorsque n et m sont constants.
Remarque : Octets que l’égalité n peuvent être signalées à likelyhasbetween comme de faux positifs, donc cela doit être vérifié en caractères si il faut un certain résultat.

Requirements: x>=0; 0<=m<=127; 0<=n<=128

#define likelyhasbetween(x,m,n) \
((((x)-~0UL/255*(n))&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)
Cette technique serait appropriée pour un test rapide. Une variante qui prend une seule opération plus (8 au total pour n et m constant), mais fournit la réponse exacte est :

#define hasbetween(x,m,n) \
((~0UL/255*(127+(n))-((x)&~0UL/255*127)&~(x)&((x)&~0UL/255*127)+~0UL/255*(127-(m)))&~0UL/255*128)

Pour compter le nombre d’octets dans le x qui se situent entre m et n (exclusif) dans 10 opérations, utilisez :
#define countbetween(x,m,n) (hasbetween(x,m,n)/128%255)
Juha Järvi proposé likelyhasbetween le 6 avril 2005. De , Sean Anderson a créé hasbetween et countbetween le 10 avril 2005.

Calculer la permutation lexicographique suivante de bit

Supposons que nous ayons un ensemble de N bits définis à 1 dans un nombre entier et nous voulons que la prochaine permutation de N 1 bits dans un sens lexicographique. Par exemple, si N est le 3 et le modèle binaire est 00010011, les patrons suivant serait 00010101, 00010110, 00011001,00011010, 00011100, 00100011 et ainsi de suite. Voici un moyen rapide de calculer la permutation suivante.
unsigned int v; // current permutation of bits

unsigned int w; // next permutation of bits

unsigned int t = v | (v – 1); // t gets v’s least significant 0 bits set to 1
// Next set to 1 the most significant bit to change,
// set to 0 the least significant ones, and add the necessary 1 bits.
w = (t + 1) | (((~t & -~t) – 1) >> (__builtin_ctz(v) + 1));

Le compilateur GNU C __builtin_ctz(v) intrinsèque pour x 86 CPUs retourne le nombre de zéros de fin. Si vous utilisez des compilateurs de Microsoft pour x 86, l’intrinsèque est _BitScanForward. Ces deux émettant une instruction de FSB, mais équivalents peuvent être disponibles pour les autres architectures. Si ce n’est pas le cas, alors envisager d’utiliser une des méthodes pour compter les consécutives bits zéro mentionnés précédemment.

Voici une autre version qui tend à être plus lent à cause de son opérateur de division, mais il ne nécessite pas de compter les zéros de fin.

unsigned int t = (v | (v – 1)) + 1;
w = t | ((((t & -t) / (v & -v)) >> 1) – 1);

Merci à Dario Sneidermanis de l’Argentine, qui a fourni ce le 28 novembre 2009.

Comments are closed.