Extraire des bits avec une seule multiplication

J’ai vu une technique intéressante utilisée dans une réponse à une autre question et j’aimerais la comprendre un peu mieux.

On nous donne un entier non signé de 64 bits, et nous sums intéressés par les bits suivants:

1.......2.......3.......4.......5.......6.......7.......8....... 

Plus précisément, nous aimerions les déplacer vers les huit premières positions, comme ceci:

 12345678........................................................ 

Nous ne nous soucions pas de la valeur des bits indiqués par . , et ils ne doivent pas être préservés.

La solution consistait à masquer les bits indésirables et à multiplier le résultat par 0x2040810204081 . Ceci, en fait, fait l’affaire.

Quelle est la généralité de cette méthode? Cette technique peut-elle être utilisée pour extraire un sous-ensemble de bits? Sinon, comment peut-on déterminer si la méthode fonctionne ou non pour un ensemble de bits particulier?

Enfin, comment procéder pour trouver le multiplicateur correct (a?) Pour extraire les bits donnés?

    Question très intéressante et astuce.

    Examinons un exemple simple de manipulation d’un seul octet. Utilisation de 8 bits non signés pour plus de simplicité. Imaginez que votre numéro est xxaxxbxx et que vous voulez ab000000 .

    La solution consistait en deux étapes: un masquage de bits, suivi d’une multiplication. Le masque de bits est une opération ET simple qui transforme les bits inintéressants en zéros. Dans le cas ci-dessus, votre masque serait 00100100 et le résultat 00a00b00 .

    Maintenant, la partie difficile: transformer cela en ab......

    Une multiplication est un ensemble d’opérations de décalage et d’ajout. L’essentiel est de permettre au débordement de “déplacer” les bits inutiles et de mettre ceux que nous voulons au bon endroit.

    La multiplication par 4 ( 00000100 ) 00000100 tout ce qui rest de 2 et vous a00b0000 à a00b0000 . Pour que le b progresse, il faut multiplier par 1 (pour garder le a au bon endroit) + 4 (pour déplacer le b). Cette sum est égale à 5 et combinée avec la précédente 4, nous obtenons un nombre magique de 20, ou 00010100 . L’original était 00a00b00 après le masquage; la multiplication donne:

     000000a00b000000 00000000a00b0000 + ---------------- 000000a0ab0b0000 xxxxxxxxab...... 

    À partir de cette approche, vous pouvez étendre à un plus grand nombre et à plus de bits.

    L’une des questions que vous avez posées était “Est-ce que cela peut être fait avec un nombre quelconque de bits?” Je pense que la réponse est “non”, sauf si vous autorisez plusieurs opérations de masquage ou plusieurs multiplications. Le problème est la question des “collisions” – par exemple, le “stray b” dans le problème ci-dessus. Imaginez que nous devions faire cela à un nombre comme xaxxbxxcx . Suivant l’approche précédente, vous penseriez que nous avons besoin de {x 2, x {1 + 4 + 16}} = x 42 (oooh – la réponse à tout!). Résultat:

     00000000a00b00c00 000000a00b00c0000 0000a00b00c000000 ----------------- 0000a0ababcbc0c00 xxxxxxxxabc...... 

    Comme vous pouvez le voir, cela fonctionne toujours, mais “seulement juste”. La clé ici est qu’il y a “assez d’espace” entre les bits que nous voulons pour que nous puissions tout resserrer. Je ne pouvais pas append un quasortingème bit juste après c, car j’obtiendrais des exemples où j’obtiendrais c + d, des bits pourraient être portés, …

    Donc, sans preuve formelle, je répondrais aux parties les plus intéressantes de votre question comme suit: “Non, cela ne fonctionnera pas pour un nombre de bits. Pour extraire N bits, vous avez besoin d’espaces (N-1) entre les bits que vous voulez extraire, ou avoir des étapes supplémentaires de multiplication de masque. ”

    La seule exception à laquelle je peux penser pour la règle “doit avoir (N-1) zéros entre les bits” est la suivante: si vous souhaitez extraire deux bits adjacents dans l’original ET que vous souhaitez les conserver dans le même ordre, alors vous pouvez toujours le faire. Et pour les besoins de la règle (N-1), ils comptent comme deux bits.

    Il y a une autre idée – inspirée par la réponse de @Ternary ci-dessous (voir mon commentaire ici). Pour chaque bit intéressant, vous n’avez besoin que du nombre de zéros à droite, car vous avez besoin d’espace pour les bits qui doivent y aller. Mais aussi, il faut autant de bits vers la gauche que de bits de résultat vers la gauche. Donc, si un bit b se retrouve en position m de n, il doit avoir des zéros de gauche à gauche et des zéros à droite. En particulier lorsque les bits ne sont pas dans le même ordre dans le numéro d’origine qu’ils le seront après la réorganisation, il s’agit d’une amélioration importante par rapport aux critères d’origine. Cela signifie, par exemple, qu’un mot de 16 bits

     a...eb..d..c.. 

    Peut être déplacé dans

     abcde........... 

    même s’il n’y a qu’un espace entre e et b, deux entre d et c, trois entre les autres. Qu’est-il arrivé à N-1 ?? Dans ce cas, a...e devient “un bloc” – ils sont multipliés par 1 pour se retrouver au bon endroit, et donc “nous avons eu e gratuitement”. La même chose est vraie pour b et d (b nécessite trois espaces à droite, d nécessite les trois mêmes à sa gauche). Donc, quand on calcule le nombre magique, on trouve des doublons:

     a: < < 0 ( x 1 ) b: << 5 ( x 32 ) c: << 11 ( x 2048 ) d: << 5 ( x 32 ) !! duplicate e: << 0 ( x 1 ) !! duplicate 

    Clairement, si vous vouliez que ces nombres soient dans un ordre différent, vous devriez les espacer davantage. On peut reformuler la règle (N-1) : "Cela fonctionnera toujours s'il y a au moins (N-1) espaces entre les bits ou si l'ordre des bits dans le résultat final est connu, alors si un bit b se termine en position m de n, il doit avoir des zéros à sa gauche, et des zéros à sa droite. "

    @Ternary a fait remarquer que cette règle ne fonctionnait pas tout à fait, car il peut y avoir un report des bits en ajoutant "juste à droite de la zone cible", à savoir lorsque les bits que nous recherchons sont tous. Poursuivant l’exemple que j’ai donné ci-dessus avec les cinq bits serrés dans un mot de 16 bits: si nous commençons par

     a...eb..d..c.. 

    Pour simplifier, je ABCDEFGHIJKLMNOP positions de bits ABCDEFGHIJKLMNOP

    Le calcul que nous allions faire était

     ABCDEFGHIJKLMNOP a000e0b000d00c00 0b000d00c0000000 000d00c000000000 00c0000000000000 + ---------------- abcded(b+c)0c0d00c00 

    Jusqu'à présent, nous pensions que tout ce qui est en-dessous de abcde (positions ABCDE ) n'aurait pas d'importance, mais en fait, comme l'a souligné @Ternary, si b=1, c=1, d=1 alors (b+c) en position G bit à porter à la position F , ce qui signifie que (d+1) en position F entraînera un bit dans E - et notre résultat est gâché. Notez que l'espace à la droite du bit d'intérêt le moins significatif ( c dans cet exemple) n'a pas d'importance, car la multiplication provoquera un bourrage avec des zéros à partir du bit le moins significatif.

    Nous devons donc modifier notre règle (m-1) / (nm). S'il y a plus d'un bit ayant "exactement (nm) bits inutilisés à droite (sans compter le dernier bit du motif -" c "dans l'exemple ci-dessus), nous devons renforcer la règle - et nous devons faites-le itérativement!

    Nous devons regarder non seulement le nombre de bits correspondant au critère (nm), mais aussi ceux qui sont à (n-m + 1), etc. Appelons leur nombre Q0 (exactement nm à bit suivant), Q1 (n-m + 1), jusqu'à Q (N-1) (n-1). Alors nous risquons de porter si

     Q0 > 1 Q0 == 1 && Q1 >= 2 Q0 == 0 && Q1 >= 4 Q0 == 1 && Q1 > 1 && Q2 >=2 ... 

    Si vous regardez cela, vous pouvez voir que si vous écrivez une expression mathématique simple

     W = N * Q0 + (N - 1) * Q1 + ... + Q(N-1) 

    et le résultat est W > 2 * N , vous devez alors augmenter le critère RHS d'un bit à (n-m+1) . A ce stade, l'opération est sûre tant que W < 4 ; si cela ne fonctionne pas, augmentez le critère un de plus, etc.

    Je pense que suivre ce qui précède vous mènera à un long chemin vers votre réponse ...

    Question très intéressante en effet. Je me fie à mes deux cents, à savoir que si vous parvenez à énoncer des problèmes comme celui-ci en termes de logique du premier ordre sur la théorie du bitvector, alors les démonstrateurs de théorèmes sont vos amis et peuvent potentiellement vous fournir très rapidement réponses à vos questions. Ré-énonçons le problème posé comme théorème:

    “Il existe des constantes de 64 bits ‘mask’ et ‘multiplicand’ telles que, pour tous les binarys 64 bits x, dans l’expression y = (x & mask) * multiplicande, nous avons cette y.63 == x.63 , y.62 == x.55, y.61 == x.47, etc. ”

    Si cette phrase est en fait un théorème, alors il est vrai que certaines valeurs des constantes ‘mask’ et ‘multiplicand’ satisfont cette propriété. Donc, formulons ceci en termes de quelque chose qu’un prouveur de théorème peut comprendre, à savoir l’entrée SMT-LIB 2:

     (set-logic BV) (declare-const mask (_ BitVec 64)) (declare-const multiplicand (_ BitVec 64)) (assert (forall ((x (_ BitVec 64))) (let ((y (bvmul (bvand mask x) multiplicand))) (and (= ((_ extract 63 63) x) ((_ extract 63 63) y)) (= ((_ extract 55 55) x) ((_ extract 62 62) y)) (= ((_ extract 47 47) x) ((_ extract 61 61) y)) (= ((_ extract 39 39) x) ((_ extract 60 60) y)) (= ((_ extract 31 31) x) ((_ extract 59 59) y)) (= ((_ extract 23 23) x) ((_ extract 58 58) y)) (= ((_ extract 15 15) x) ((_ extract 57 57) y)) (= ((_ extract 7 7) x) ((_ extract 56 56) y)) ) ) ) ) (check-sat) (get-model) 

    Et maintenant, demandons au prouveur de théorème Z3 s’il s’agit d’un théorème:

     z3.exe /m /smt2 ExtractBitsThroughAndWithMultiplication.smt2 

    Le résultat est:

     sat (model (define-fun mask () (_ BitVec 64) #x8080808080808080) (define-fun multiplicand () (_ BitVec 64) #x0002040810204081) ) 

    Bingo! Il reproduit le résultat donné dans le message original en 0.06 secondes.

    Dans une perspective plus générale, nous pouvons y voir un exemple de problème de synthèse de programmes de premier ordre, domaine de recherche naissant sur lequel peu d’articles ont été publiés. Une recherche de "program synthesis" filetype:pdf devrait vous aider à démarrer.

    Chaque bit du multiplicateur est utilisé pour copier l’un des bits dans sa position correcte:

    • 1 est déjà dans la bonne position, donc multipliez par 0x0000000000000001 .
    • 2 doit être décalé de 7 bits vers la gauche, donc on multiplie par 0x0000000000000080 (le bit 7 est défini).
    • 3 doivent être décalés de 14 bits vers la gauche, nous multiplions donc par 0x0000000000000400 (le bit 14 est défini).
    • et ainsi de suite jusqu’à
    • 8 doit être décalé de 49 bits vers la gauche, nous multiplions donc par 0x0002000000000000 (le bit 49 est défini).

    Le multiplicateur est la sum des multiplicateurs pour les bits individuels.

    Cela ne fonctionne que parce que les bits à collecter ne sont pas trop proches les uns des autres, de sorte que la multiplication des bits qui n’appartiennent pas ensemble dans notre schéma se situe au-delà du bit 64 ou de la partie inférieure non sensible.

    Notez que les autres bits du numéro d’origine doivent être 0 . Cela peut être réalisé en les masquant avec une opération AND.

    (Je ne l’avais jamais vu auparavant. Ce truc est génial!)

    Je vais développer un peu plus sur l’assertion de Floris que lors de l’extraction de n bits, vous avez besoin de n-1 espace entre des bits non consécutifs:

    Ma première pensée (nous verrons dans une minute comment cela ne fonctionne pas) était que vous pouviez faire mieux: si vous voulez extraire n bits, vous aurez une collision lors de l’extraction / du transfert de bit i si vous avez quelqu’un (non consécutif avec le bit i ) dans les bits i-1 précédents ou ni suivants.

    Je donnerai quelques exemples pour illustrer:

    ...a..b...c... Fonctionne (personne dans les 2 bits après a , le bit avant et le bit après b , et personne n’est dans les 2 bits avant c ):

      a00b000c + 0b000c00 + 00c00000 = abc..... 

    ...ab...c... échoue parce que b est dans les 2 bits après a (et est tiré à l’endroit de quelqu’un d’autre quand on décale a ):

      a0b0000c + 0b0000c0 + 00c00000 = abX..... 

    ...a...bc.. Échec parce que b est dans les 2 bits précédant c (et est poussé à l’endroit de quelqu’un d’autre quand on décale c ):

      a000b0c0 + 0b0c0000 + b0c00000 = Xbc..... 

    ...a...bc...d... Fonctionne car les bits consécutifs se déplacent ensemble:

      a000bc000d + 0bc000d000 + 000d000000 = abcd000000 

    Mais nous avons un problème. Si nous utilisons ni au lieu de n-1 nous pourrions avoir le scénario suivant: que se passe-t-il si nous avons une collision en dehors de la partie qui nous intéresse, quelque chose que nous masquerions à la fin, mais dont gamme non masquée? (et remarque: l’exigence n-1 garantit que cela ne se produit pas en s’assurant que les bits i-1 après notre plage non masquée sont clairs lorsque nous décalons le iième bit)

    ...a...b..c...d... Échec potentiel sur les bits de report, c est dans n-1 après b , mais satisfait aux critères:

      a000b00c000d + 0b00c000d000 + 00c000d00000 + 000d00000000 = abcdX....... 

    Alors pourquoi ne pas simplement revenir à cette exigence de ” n-1 bits d’espace”? Parce que nous pouvons faire mieux :

    ...a....b..c...d.. réussit pas le test ” n-1 bits de l’espace”, mais fonctionne pour notre astuce d’extraction de bits:

     + a0000b00c000d00 + 0b00c000d000000 + 00c000d00000000 + 000d00000000000 = abcd...0X...... 

    Je ne peux pas trouver un bon moyen de caractériser ces champs qui n’ont pas d’espace n-1 entre les bits importants, mais cela fonctionnerait quand même pour notre opération. Cependant, comme nous soaps à l’avance quels bits nous intéressent, nous pouvons vérifier notre filtre pour nous assurer que nous ne rencontrons pas de collisions de type carry-bit:

    Compare (-1 AND mask) * shift rapport au résultat attendu pour tous, -1 < < (64-n) (pour les fichiers 64 bits non signés)

    Le changement / multiplication magique pour extraire nos bits fonctionne si et seulement si les deux sont égaux.

    En plus des réponses déjà excellentes à cette question très intéressante, il pourrait être utile de savoir que cette technique de multiplication par bit est connue dans la communauté des échecs informatiques depuis 2007, où elle est connue sous le nom de Magic BitBoards .

    De nombreux moteurs d’échecs informatiques utilisent plusieurs entiers de 64 bits (appelés bitboards) pour représenter les différents ensembles de pièces (1 bit par carré occupé). Supposons qu’une pièce coulissante (tour, évêque, reine) sur une certaine case d’origine puisse se déplacer sur au plus K carrés si aucune pièce bloquante n’était présente. L’utilisation du bit bit et de ces bits K dispersés avec le bitboard des carrés occupés donne un mot K -bit spécifique intégré dans un entier de 64 bits.

    La multiplication magique peut être utilisée pour mapper ces bits K dispersés aux K bits inférieurs d’un entier de 64 bits. Ces bits K plus bas peuvent alors être utilisés pour indexer un tableau de bitboards pré-calculés représentant les carrés autorisés que le morceau sur son carré d’origine peut réellement déplacer (en prenant soin de bloquer les pièces, etc.).

    Un moteur d’échecs typique utilisant cette approche a deux tables (une pour les tours, une pour les évêques, des reines utilisant la combinaison des deux) de 64 entrées (une par carré d’origine) contenant de tels résultats pré-calculés. Le moteur d’échecs fermé ( Houdini ) et le moteur d’échecs open source ( Stockfish ) les mieux notés utilisent actuellement cette approche pour ses très hautes performances.

    La recherche de ces multiplicateurs magiques se fait soit en utilisant une recherche exhaustive (optimisée avec des seuils au début), soit avec des essais et erorr (par exemple, en essayant de nombreux entiers aléatoires de 64 bits). Il n’y a eu aucun modèle de bit utilisé pendant la génération de déplacement pour lequel aucune constante magique n’a pu être trouvée. Cependant, les effets de transport binary sont généralement nécessaires lorsque les bits à mapper ont des index (presque) adjacents.

    AFAIK, le résolveur de SAT très général par @Syzygy n’a pas été utilisé dans les échecs informatiques, et il ne semble pas non plus y avoir de théorie formelle concernant l’existence et l’unicité de ces constantes magiques.