La Position du bit le moins significatif est définie
Je suis à la recherche d'un moyen efficace pour déterminer la position du bit le moins significatif est définie dans un entier, par exemple pour 0x0FF0 il serait de 4.
Une implémentation simple est: est-ce
unsigned GetLowestBitPos(unsigned value)
{
assert(value != 0); //handled separately
unsigned pos = 0;
while (!(value & 1))
{
value >>= 1;
++pos;
}
return pos;
}
Toutes les idées sur la façon de serrer quelques cycles hors de lui?
(Remarque: cette question est pour les gens qui aiment ce genre de choses, pas pour les gens de me dire xyzoptimization est le mal.)
[modifier] Merci à tous pour les idées! J'ai appris un peu d'autres choses, aussi. Cool!
- while ( (valeur _N >> (++pos)) != 0 );
- connexes: la position de la seule 1 dans un nombre en format binaire
Vous devez vous connecter pour publier un commentaire.
Peu Se Tourner Les Hacks offre une excellente collection de, er, peu se tourner les hacks, avec une performance/optimisation de la discussion ci-joint. Mon préféré la solution à votre problème (de ce site) est de «multiplier et de recherche»:
Références utiles:
__builtin_ffsl
ouffsl
?error C4146: unary minus operator applied to unsigned type, result still unsigned
Je suppose qu'il doit être(v & (0-v))
afin de ne pas provoquer les mises en gardePourquoi ne pas utiliser le haut -ffs? (J'ai attrapé une page de man de Linux, mais c'est plus largement que ce que.)
Il y a un x86 instruction de montage (
bsf
) qui va le faire. 🙂Plus optimisé?!
Note De Côté:
Optimisation à ce niveau est intrinsèquement dépendants de l'architecture. Aujourd'hui, les processeurs sont trop complexe (en termes de direction de la prévision, le cache, le pipelining) qu'il est donc difficile de prévoir si le code est exécuté plus rapidement sur l'architecture. La diminution des opérations de 32 à 9 ou des choses comme ça pourrait même diminuer les performances sur certaines architectures. Code optimisé sur une architecture unique peut entraîner dans les pires code dans l'autre. Je pense que vous auriez optimiser ce pour un PROCESSEUR ou de le laisser tel qu'il est et de laisser le compilateur de choisir ce qu'il pense que c'est mieux.
La plupart des architectures modernes va avoir des indications pour trouver la position la plus basse de bit, ou le plus haut de bit, ou de compter le nombre de zéros à gauche etc.
Si vous avez une instruction de cette classe, vous pouvez à moindre coût imiter les autres.
Prendre un moment pour travailler à travers elle sur le papier, et de réaliser que
x & (x-1)
sera clairement le plus bas de bit dans x, et( x & ~(x-1) )
sera de retour le plus de bit, indépendamment de l'achitecture, la longueur des mots, etc. Sachant cela, il est trivial d'utiliser du matériel de comptage de pointe-des zéros /haute-ensemble de bits pour trouver le plus bas de bit si il n'y a aucun enseignement explicite de le faire.Si il n'y a aucun support matériel, à tous, les multiplier et de recherche mise en œuvre du comte de pointe-des zéros donné ici ou l'un de ceux sur la Peu Se Tourner Les Hacks page peut trivialement être converti à donner le plus bas de bit en utilisant les identités et a l'avantage d'être dépourvu de branches.
La manière la plus rapide (non intrinsèque/non-assembleur) la solution à ce problème consiste à trouver le plus bas-octet, et ensuite utiliser cet octet dans un 256-entrée de la table de recherche. Cela vous donne un des cas les pires performances de quatre instructions conditionnelles et dans le meilleur des cas de 1. Non seulement est-ce le moins d'instructions, mais le moins de branches qui est super-important sur le matériel moderne.
Votre table (256 8 bits entrées) contient l'index de la LSB pour chaque nombre dans la plage de 0 à 255. Vous consultez chaque octet de votre valeur et de trouver le plus bas de la non-zéro octet, puis utiliser cette valeur pour la recherche de l'indice réel.
Cela impose de 256 octets de mémoire, mais si la vitesse de cette fonction est donc important alors que de 256 octets est bien la peine,
E. g.
Deee, des tas de solutions et non pas une référence dans la vue. Vous devriez avoir honte de vous-mêmes 😉
Ma machine est un Intel i530 (2,9 GHz), fonctionnant sous Windows 7 64 bits. J'ai compilé avec une version 32 bits de MinGW.
Mon code:
rand()
des données de test aura un zéro octet de poids faible d'un seul en 256 fois, de sorte que la direction de la prédit très bien. Sur Godbolt, gcc4.7.2-m32 -O2 -march=corei7
boucle interne va de.L13
àjne .L13
lorsque le premier octet est non nul, et devrait avoir un bon débit sur votre PROCESSEUR Nehalem, et juste un goulot d'étranglement sur son débit de 9 fusionnée de domaine uop, à proximité de l'théorique maximum de 4 par cycle d'horloge. J'ai dû découper le code des deux fonctions, sinon l'URL est trop longue pour godbolt à raccourcir avec goo.gl. :/BSF
a une fausse dépendance sur sa sortie (depuis le comportement réel lors de la saisie d'=0 est de laisser la sortie inchangée). gcc malheureusement, transforme ce dans une boucle-procédé de dépendance par pas de compensation le registre entre les itérations de boucle. Si la boucle doit s'exécuter à un par 5 cycles, un goulot d'étranglement sur la BSF(3) + CMOV(2) le temps de latence.ffs()
devrait avoir un débit de l'un par cycle d'horloge (3 uop, 1 pour le BSF et 2 pour CMOV, et ils peuvent s'exécuter sur des ports différents). Avec la même boucle de la surcharge, c'est 7 ALU uop qui peuvent s'exécuter (sur votre CPU) à 3 par cycle d'horloge. Les frais généraux domine! Source: agner.org/optimizebsf ecx, [ebx+edx*4]
ne pas traiterecx
comme une entrée qu'il devait attendre. (ECX dernière écrite par le précédent iteraton de CMOV). Mais le CPU ne se comporter de cette façon, à mettre en œuvre le "laisser dest non modifiée si la source est égal à zéro" comportement (il n'est donc pas vraiment un faux dep comme il est TZCNT; une dépendance de données est nécessaire, car il n'y a pas de branchement + spéculative de l'exécution sur l'hypothèse que l'entrée est non nul). Nous avons pu surmonter par l'ajout d'unxor ecx,ecx
avant labsf
, pour briser la dépendance à l'ECX.mov ecx, [ebx+edx*4]
/bsf ecx, ecx
. MOV sans condition écrit sa destination avec aucune dépendance à l'ancienne valeur, alors inscrivez-renommage fait de cette itération est ECX indépendante de la précédente itération de l'architecture ECX. c'est à dire qu'il rompt la chaîne de dépendances, tout comme un xor zéro serait.__builtin_ctz()
.OMG a ce juste en spirale.
Ce que la plupart de ces exemples sont le manque d'un peu de compréhension sur la façon dont tous le matériel fonctionne.
À tout moment vous avez une branche, le PROCESSEUR est de deviner quelle direction va prendre. L'instruction de la pipe est chargé avec les instructions que le conduire à l'aurez deviné chemin. Si le CPU a deviné mauvaise, l'instruction tuyau reçoit vidées, et l'autre branche doit être chargé.
Envisager la boucle while simple en haut. L'estimation sera de rester à l'intérieur de la boucle. Il va être à tort, au moins une fois au moment où il quitte la boucle. Cela se rincer l'instruction de la pipe. Ce comportement est légèrement mieux que de deviner qu'il va sortir de la boucle, dans ce cas qu'il chasse l'instruction de la pipe à chaque itération.
La quantité de cycles PROCESSEUR qui sont perdus varie fortement d'un type de processeur à l'autre. Mais vous pouvez vous attendre entre 20 et 150 perdu de cycles CPU.
La prochaine pire groupe est l'endroit où vous pensez que vous allez économiser un peu d'itérations en divisant la valeur en morceaux plus petits et l'ajout de plusieurs branches. Chacune de ces branches ajoute une occasion supplémentaire pour vider l'instruction de la pipe et du coût de 20 à 150 cycles d'horloge.
Permet de considérer ce qui se passe quand vous rechercher une valeur dans un tableau. Les Chances sont la valeur n'est pas en cache, au moins pas la première fois que la fonction est appelée. Cela signifie que le PROCESSEUR obtient l'impasse alors que la valeur est chargé à partir du cache. Encore cela varie d'une machine à l'autre. Les nouvelles puces d'Intel réellement utiliser cela comme une occasion pour échanger les threads alors que le thread est en attente pour le cache charge complète. Cela pourrait facilement être plus cher qu'une instruction tuyau de rinçage, cependant, si vous effectuez cette opération, un certain nombre de fois, il est probable qu'une seule fois.
Clairement la manière la plus rapide de la constante de temps de la solution implique déterministe de mathématiques. Pure et élégante solution.
Toutes mes excuses si cela a déjà été couvert.
Chaque compilateur que j'utilise, sauf XCODE autant que je sache, a compilateur intrinsèques de l'avant bitscan et l'inverse bitscan. Ces compiler en une seule instruction de montage sur la plupart des matériels avec pas de Cache Miss, aucune Branche ne Manquez Prédiction et Aucun autre programmeur généré des pierres d'achoppement.
Pour les compilateurs Microsoft utiliser _BitScanForward & _BitScanReverse.
Pour utiliser GCC __builtin_ffs, __builtin_clozapine, __builtin_ctz.
En outre, veuillez vous abstenir de poster une réponse et induire en erreur les nouveaux arrivants si vous ne sont pas suffisamment informés sur le sujet discuté.
Désolé j'ai totalement oublié de fournir une solution.. C'est le code que j'ai utiliser sur l'IPAD qui n'a pas d'assemblée niveau d'instruction de la tâche:
La chose à comprendre ici est que ce n'est pas le comparer c'est cher, mais la branche qui se produit après les comparer. La comparaison dans ce cas est forcé à une valeur de 0 ou 1 avec la .. == 0, et le résultat est utilisé pour combiner les mathématiques, qui se serait produite sur chaque côté de la branche.
Edit:
Le code ci-dessus est totalement rompu. Ce code fonctionne et est encore, dans la branche libre (si optimisée):
Cela renvoie -1 si 0. Si vous n'avez pas de soins sur 0 ou sont heureux de l'avoir 31 pour 0, retirez le i0 calcul, l'enregistrement d'un morceau de temps.
Inspiré par ce poste similaire qui implique la recherche d'un ensemble de bits, j'offre le suivant:
Pour:
Contre:
Mise à jour:
Comme l'a souligné dans les commentaires, une union est un nettoyeur de mise en œuvre (pour le C, au moins), et ressemblerait à:
Cela suppose 32 bits entiers avec little-endian de stockage pour tout (pensez à les processeurs x86).
int
estint32_t
, et qui a signé la touche maj droite est un décalage (en C++ c'est la mise en œuvre définies par l')cmp value, 1
/adc value, -1
pour évaluervalue - !!value
. gcc utilise test/setcc/sub.double
de conversion. Heureusement x86 pouvez le faire que par zéro en l'élargissant à un entier de 64 bits et à l'aide d'un entier signé de 64 bits->double conversion. (Pas de direct non signé->double conversions jusqu'à AVX512). De toute façon, je pense que cela signifie ce code est portable à compléter et à signer et l'ampleur des machines, mais tout dépend de FP boutisme. (Apparemment FP boutisme ne doit pas correspondre entier endianness).unsigned
que dans unsigned
, alors que ce serait une bonne raison pour utiliser ununsigned
type.cmp/adc
est au moins aussi bonne sur les Processeurs actuels, et de mieux en mieux sur de nombreux. (AMD et Intel depuis Broadwell). En fait, latest/setcc
a un supplément de xor-réinitialisation de l'instruction, de sorte que même sur Intel pré-Broadwell oùadc
est de 2 uop, il est probablement mieux (sauf en cas de multi-uop instruction frappe les décodeurs à un malheureux spot, sur des Processeurs sans une uop cache).Il peut être fait avec un pire des cas, de moins de 32 opérations:
Principe: Vérification pour 2 ou plus de bits est tout aussi efficace que la vérification de 1 bit.
Ainsi, par exemple, il n'y a rien qui vous empêche de vérification pour lesquelles le regroupement de ses en première, puis en vérifiant chaque bit de la plus petite à la plus grande dans le groupe.
Donc...
si vous cochez la case 2 bits à la fois, vous avez dans le pire des cas (Nbits/2) + 1 vérifie total.
si vous cochez la case 3 bits à la fois, vous avez dans le pire des cas (Nbits/3) + 2 chèques total.
...
Optimale serait de vérifier dans les groupes de 4. Qui aurait besoin, dans le pire des cas, 11 opérations à la place de votre 32.
Le meilleur des cas, va de votre algorithmes de 1 vérifiez bien que de 2 vérifie si vous utilisez ce regroupement idée. Mais ce supplément de 1 case dans le meilleur des cas est-il intéressant pour le pire des cas de l'épargne.
Note: je l'écris en entier au lieu d'utiliser une boucle car il est plus efficace de cette façon.
Pourquoi ne pas utiliser recherche binaire? Ce sera toujours complet après 5 opérations (en supposant int taille de 4 octets):
Une autre méthode (le module de la division et de la recherche) mérite une mention spéciale ici à partir de la même lien fournis par @anton-tykhyy. cette méthode est très similaire à la performance de DeBruijn de se multiplier et de méthode de recherche avec une légère différence importante.
module de division et de recherche
module de la division et de la méthode de recherche renvoie des valeurs différentes pour v=0 x 00000000 et v=FFFFFFFF alors que DeBruijn de se multiplier et de recherche de la méthode retourne la valeur zéro sur les deux entrées.
test:-
mod
est lente. Au lieu de cela, vous pouvez utiliser l'original se multiplient-et-méthode de recherche et de soustraire!v
der
pour gérer les cas de bord.Selon la Programmation du jeu d'échecs BitScan page et mes propres mesures, soustraire et xor est plus rapide que de nier et d'un masque.
(Notez que si vous allez compter les zéros à droite dans
0
, la méthode que je l'ai retourne63
alors que le nier et le masque renvoie0
.)Ici est une version 64 bits de soustraire et xor:
Pour référence, voici une version 64 bits de la nier et de la méthode du " masque:
(v ^ (v-1))
travaillev != 0
. En cas dev == 0
il retourne 0xFF....FF alors que(v & -v)
donne zéro (ce qui est faux, aussi, buf, au moins, il conduit à un résultat raisonnable).v ^ (v-1)
, il n'existe donc pas de les distinguer. Dans mon scénario, zéro ne sera jamais entrée.Vous pouvez vérifier si l'un des bits d'ordre inférieur sont fixés. Si oui, alors regardez le bas afin de les bits restants. par exemple,:
32 bits int - vérifier si l'un des 16 premiers sont définis.
Si oui, vérifier si l'un des 8 premiers sont définis.
si oui, ....
si non, vérifier si tout de la partie supérieure de 16 sont ensemble..
Essentiellement, c'est la recherche binaire.
Voir ma réponse ici pour comment le faire avec une seule instruction x86, sauf que pour trouver le moins ensemble important peu, vous aurez besoin de la
BSF
("bit scan forward") l'instruction au lieu deBSR
qui y sont décrits.Encore une autre solution, pas le plus rapide peut-être, mais semble assez bon.
Au moins, il n'a pas de branches. 😉
1
s de le moins significatif de 1 LSB, utilisez((x & -x) - 1) << 1
au lieux ^ (x-1)
50% de tous les numéros seront de retour sur la première ligne de code.
75% de tous les numéros sera de retour sur les 2 premières lignes de code.
87% de tous les numéros sera de retour dans les 3 premières lignes de code.
94% de tous les numéros sera de retour dans les 4 premières lignes de code.
97% de tous les numéros sera de retour dans les 5 premières lignes de code.
etc.
Je pense que les gens qui se plaignent sur la façon inefficace le pire des cas pour que ce code ne comprends pas comment rare que l'état va se passer.
Trouvé cette astuce à l'aide de la " magie des masques "dans" l'art de La programmation, de la partie 4", qui est en O(log(n)) pour n bits. [avec log(n) de l'espace supplémentaire]. Typique des solutions de contrôle pour le bit est soit O(n) ou besoin de O(n) de l'espace supplémentaire pour un look up table, donc c'est un bon compromis.
La magie des masques:
Idée clé:
Pas de zéros à droite en x = 1 * [(x & m0) = 0] + 2 * [(x & m1) = 0] + 4 * [(x & m2) = 0] + ...
Si C++11 est disponible pour vous, un compilateur, parfois, peut faire le travail pour vous 🙂
Résultat est 1-index de base.
ffs()
au moment de la compilation, de sorte que vous n'avez pas besoin d'utiliser cette fonction pour la constante de propagation de travail. (Vous n'avez pas à éviter les inline-asm, bien sûr.) Si vous avez vraiment besoin de quelque chose qui fonctionne comme un C++11constexpr
, vous pouvez toujours utiliser GNU C__builtin_ffs
.C'est en ce qui concerne de @Anton Tykhyy réponse
Voici mon C++11 constexpr mise en œuvre en faisant disparaître les dominantes de la suppression d'un avertissement sur VC++17 par la troncature d'un 64bit résultat sur 32 bits:
Pour obtenir autour de la question de la 0x1 et 0x0 tous deux de retour de 0 que vous pouvez faire:
mais si le compilateur ne peut pas ou ne veut pas le prétraitement de l'appel, il va ajouter un couple de cycles pour le calcul.
Enfin, si vous êtes intéressé, voici une liste statique de affirme pour vérifier que le code fait ce qui est prévu pour:
Ici est une alternative simple, même si trouver des logs est un peu coûteux.
récemment, je vois que singapour, le premier ministre a affiché un programme qu'il a écrit sur facebook, il y a une ligne à le mentionner..
La logique est tout simplement "valeur & -de la valeur", supposons que vous avez 0x0FF0, puis,
0FF0 & (F00F+1) , ce qui équivaut à 0x0010, cela signifie que la plus faible 1 est dans la 4ème peu.. 🙂
Si vous avez les ressources, vous pouvez sacrifice de la mémoire afin d'améliorer la vitesse:
Remarque: Ce tableau de la consommer au moins 4 GO (16 GO si nous laissons le type de retour comme
unsigned
). Ceci est un exemple de séance d'une ressource limitée (RAM) pour un autre (vitesse d'exécution).Si votre fonction doit rester portable et courir aussi vite que possible à n'importe quel prix, ce serait la voie à suivre. Dans la plupart des applications du monde réel, de 4 go de table est irréaliste.
:)
@Dan: Vous avez raison à propos de la mémoire cache. Voir Mikeage du commentaire ci-dessus.