J'ai trouvé un moyen d'acquérir le nombre de zéros traînants dans un numéro. J'ai trouvé un peu twiddling Université Stanford Ecrivez ici ici qui donne ce qui suit explication. P> signé () code> être utilisé. Ne marquez pas cette question en tant que duplicata. 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;
3 Réponses :
Ce code (du Net) est principalement C, bien que Tout d'abord, si Sinon, le fonctionnement Le V & = -Signed (v); n'est pas correct C. L'intention est pour elle de se comporter comme V & = ~ v + 1;
v est zéro, alors il reste zéro après l'opération & Opération, ainsi que tous les instructions si sont ignorées. Vous obtenez 32.
& (lorsqu'il est corrigé) efface toutes les bits à gauche du plus à droite 1, donc à ce point v contient un seul 1 bit. Ensuite, C est décrémenté à 31, c'est-à-dire tous les 1 bits dans la gamme de résultats possible.
si Les instructions déterminent ensuite sa position numérique un bit à la fois (un bit du numéro de position, non de V ), effacement des bits qui doivent être 0 .
Le code est cassé (le comportement non défini est présent). Voici une version fixe qui est également légèrement plus facile à comprendre (et probablement plus rapide): une fois que nous savons qu'un seul bit est défini, nous déterminons un bit du résultat à la fois, par Tester simultanément tous les bits où le résultat est impair, alors tous les bits où le résultat a le jeu de la place de 2 ans, etc. Le code d'origine a fonctionné en sens inverse, en commençant par tous les bits du jeu de résultats (après le Puisque nous apprenons un bit de la sortie à la fois, je pense Il est plus clair de construire la sortie à l'aide des opérations bits non arithmétiques. si (c) c -; ) puis déterminer ce qui devait être zéro et les effacer.
Le code Premier Transforms V est une telle manière qui est entièrement nulle, à l'exception de la première gauche qui reste. Ensuite, il détermine la position de ce premier.
Voyons d'abord voir comment nous supprimons tous les autres mais la gauche la plus unique. P>
suppose que k est la position de la gauche la plus à v. V = (vn-1, vn-2, .. vk + 1,1,0,. 0). p>
-v est le numéro ajouté à V donnera 0 (en fait, il donne 2 ^ n, mais bit 2 ^ n est ignoré si nous gardons seulement les n morts moins significatifs). P>
Quelle doit la valeur des bits in -v afin que v + -v = 0? p>
Les bits évidemment K-1..0 de -k doivent être à 0 de sorte qu'ajoué aux zéros de fin en V qu'ils donnent un zéro. p> li>
bit k doit être à 1. Ajouté à celui de VK, il donnera un zéro et un port à un à l'ordre K + 1 P> li>
BIT K + 1 de -V sera ajouté à VK + 1 et au transport généré à l'étape k. Ce doit être le complément logique de VK + 1. Donc, quelle que soit la valeur de vk + 1, nous aurons 1 + 0 + 1 si vk + 1 = 0 (ou 1 + 1 + 0 si vk + 1 = 1) et le résultat sera 0 à la commande K + 1 avec un transport généré à l'ordre K + 2. P> li>
Ceci est similaire pour les bits n-1..k + 2 et ils doivent tous être le complément logique du bit correspondant dans v. p> li> ul>
Par conséquent, nous obtenons le résultat bien connu que pour obtenir -v, il faut P>
laisser tomber inchangé tous les zéros traînants de v p> li>
laissez inchangée la gauche la plus partie de v p> li>
compléter tous les autres bits. P> li> ul>
Si nous calculons V &V, nous avons p>
if (v) c--; // no 1 in result? -> 32 trailing zeros.
// Otherwise it will be in range c..0=31..0
if (v & 0x0000FFFF) c -= 16; // If there is a one in left most part of v the range
// of possible values for the location of this one
// will be 15..0.
// Otherwise, range must 31..16
// remaining range is c..c-15
if (v & 0x00FF00FF) c -= 8; // if there is one in either byte 0 (c=15) or byte 2 (c=31),
// the one is in the lower part of range.
// So we must substract 8 to boundaries of range.
// Other wise, the one is in the upper part.
// Possible range of positions of v is now c..c-7
if (v & 0x0F0F0F0F) c -= 4; // do the same for the other bits.
if (v & 0x33333333) c -= 2;
if (v & 0x55555555) c -= 1;
Je vous suggère de faire toutes les opérations sur papier, en utilisant des bits binaires actuels au lieu de représentations décimales ou hexadécimales. «Step» à travers les opérations une par une, comme vous le feriez dans un débogueur.