Extraire les morceaux avec une simple multiplication

Question

J'ai vu une technique intéressante utilisé dans une réponse à une autre question, et aimerais comprendre un peu mieux.

Nous avez donné une 64 bits non signé entier, et nous sommes intéressés par les bits suivants:

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

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

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

Nous ne nous soucions pas de la valeur des bits indiqué par ., et ils n'ont pas à être conservées.

La solution a été de masquer les indésirables bits, et multiplier le résultat par 0x2040810204081. Cela, comme il s'avère, en fait le tour.

Comment le général est cette méthode? Cette technique peut-elle être utilisée pour extraire un sous-ensemble de bits? Si non, comment fait-on savoir si oui ou non la méthode qui fonctionne pour un ensemble particulier de bits?

Enfin, comment peut-on aller sur la recherche de la (une?) corriger multiplicateur pour extraire la donnée bits?

Answer 1

Question très intéressante, et l'astuce.

Regardons un exemple simple d'obtenir un seul octet manipulés. L'aide non signé de 8 bits pour des raisons de simplicité. Imaginez que votre nombre est xxaxxbxx et vous souhaitez ab000000.

La solution a consisté en deux étapes: un peu de masquage, suivie par la multiplication. Le masque de bits est une simple ET l'opération qui transforme inintéressant bits pour les zéros. Dans le cas ci-dessus, votre masque serait 00100100 et le résultat 00a00b00.

Maintenant, le plus dur: les transformant en ab.......

Une multiplication est un tas de shift-and-add opérations. La clé est de permettre à débordement à "l'abandon" les bits que nous n'avons pas besoin et de mettre ceux que nous voulons dans le bon endroit.

La Multiplication par 4 (00000100) passerait tout à gauche par 2 et vous obtenez à l' a00b0000 . Pour obtenir l' b de déplacer vers le haut nous avons besoin de multiplier par 1 (pour conserver l'un à la bonne place) + 4 (pour déplacer le b). Cette somme est 5, et combiné avec la plus tôt 4, nous avons un nombre magique de 20 00010100. L'original a été 00a00b00 après 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 est "cela peut-il être fait avec n'importe quel nombre de bits?" Je pense que la réponse est "non", sauf si vous permettez à plusieurs opérations de masquage, ou plusieurs multiplications. Le problème est le problème de "collisions" - par exemple, les "errants b" dans le problème ci-dessus. Imaginez que nous ayons besoin de le faire pour un certain nombre, comme xaxxbxxcx. À la suite de la première approche, on pourrait penser 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, il fonctionne toujours, mais "seulement". Ils clé ici est qu'il y a "suffisamment d'espace" entre les bits que nous voulons que l'on peut serrer le tout. Je ne pouvais pas ajouter un quatrième bit d à droite après le c, parce que je voudrais obtenir des instances où je reçois c+d, bits peut transporter, ...

Donc, sans preuve formelle, je répondrais les parties les plus intéressantes de votre question comme suit: "Non, cela ne fonctionnera pas pour un certain nombre de bits. Pour extraire les N bits, vous avez besoin de (N-1) espaces entre les morceaux que vous souhaitez extraire, ou avez d'autres masque de multiplier les étapes."

La seule exception que je peux penser pour le "must have (N-1) zéros entre les bits" la règle est la suivante: si vous voulez extraire deux bits qui sont adjacents les uns aux autres dans l'original, ET que vous voulez les garder dans le même ordre, alors vous pouvez toujours le faire. Et pour le but de la (N-1) de la règle, ils comptent plus de deux bits.

Il y a un autre aperçu inspiré par la réponse de @Ternaire ci-dessous (voir mon commentaire). Pour chaque morceau intéressant, vous avez seulement besoin d'autant de zéros à la droite de celui-ci que vous avez besoin de l'espace pour les bits qui ont besoin d'y aller. Mais aussi, il a besoin d'autant de bits vers la gauche comme il a raison bits vers la gauche. Donc, si un bit b se termine dans la position m de n, alors elle doit avoir m-1 zéros à sa gauche, et les n-m zéros à sa droite. Surtout lorsque les bits ne sont pas dans le même ordre et le nombre d'origine, ils seront après le re-commander, c'est une amélioration importante pour les critères d'origine. Cela signifie, par exemple, qu'un mot de 16 bits

a...e.b...d..c..

Peut être déplacé dans

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

même si il n'y a qu'un seul espace entre e et b, deux d'entre d et c, trois entre les autres. Ce qui est arrivé à N-1?? Dans ce cas, a...e devient "un bloc" - ils sont multipliés par 1 à la fin dans le bon endroit, et ainsi de "nous avons e gratuitement". Le même est vrai pour b et d (b, a besoin de trois espaces à droite, d les trois mêmes à sa gauche). Alors, quand on calcule le nombre magique, nous trouvons qu'il y a 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 voulais que ces nombres dans un ordre différent, vous avez de l'espace. Nous pouvons reformuler l' (N-1) règle: "Il sera toujours travailler si il y a au moins (N-1) les espaces entre les morceaux; ou, si l'ordre des bits dans le résultat final est connu, alors si un bit b se termine dans la position m de n, m-1 zéros à sa gauche, et les n-m zéros à sa droite."

@Ternaire a souligné que cette règle n'est pas tout à fait, comme il peut y avoir un carry à partir de morceaux d'ajouter "juste à droite de la zone cible" - à savoir, lorsque les bits que nous sommes à la recherche pour le sont toutes. En reprenant l'exemple que j'ai donné ci-dessus avec les cinq serrées bits en 16 bits mot: si nous commençons avec

a...e.b...d..c..

Pour des raisons de simplicité, je vais le nom de la position des bits ABCDEFGHIJKLMNOP

Les mathématiques nous allions faire était

ABCDEFGHIJKLMNOP

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

Jusqu'à maintenant, nous avons pensé à quelque chose en dessous de abcde (positions ABCDE) n'aurait pas d'importance, mais en fait, @Ternaire souligné, si b=1, c=1, d=1 alors (b+c) à la position G va causer un peu de porter à la position F, ce qui signifie qu' (d+1) à la position F va porter un peu en E - et notre résultat est abîmé. Veuillez noter que l'espace à droite du bit le moins significatif de l'intérêt (c dans cet exemple) n'a pas d'importance, puisque la multiplication sera la cause de remplissage avec des zéros de beyone le bit le moins significatif.

Donc, nous devons modifier notre (m-1)/(n-m) de la règle. Si il n'y a plus d'un bit qu'il a "exactement (n-m) les bits non utilisés vers la droite (sans compter le dernier bit dans le modèle de "c" dans l'exemple ci-dessus), alors nous avons besoin de renforcer l'état - et nous devons le faire de manière itérative!

Nous devons examiner non seulement le nombre de bits qui répondent à la (n-m) critère, mais également ceux qui sont à (n-m+1), etc. Appelons leur nombre Q0 ( n-m à la prochaine bits), T1 (n-m+1), Q(N-1) (n-1). On risque d'en 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, alors vous avez besoin pour augmenter la RHS critère par un bit d' (n-m+1). À ce stade, l'opération est sans danger tant que W < 4; si cela ne fonctionne pas, augmenter le critère de l'un plus, etc.

Je pense qu'à la suite de la ci-dessus, vous obtiendrez un long chemin de votre réponse...

Answer 2

Question très intéressante en effet. Je suis carillon avec mes deux cents, qui est que, si vous pouvez gérer à l'état de ce type de problèmes, en termes de la logique du premier ordre sur la bitvector théorie des démonstrateurs sont vos amis, et peut éventuellement vous fournir très rapidement les réponses à vos questions. Nous allons re-état le problème étant posé comme un théorème:

"Il existe une certaine 64 bits constantes 'masque' et 'multiplicande' tel que, pour tous 64-bit bitvectors x, dans l'expression y = (x & masque) * multiplicande, nous avons qui y de la.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 'masque' et 'multiplicande' satisfaire cette propriété. Donc, nous allons expression en termes de quelque chose d'un prouveur peut comprendre, à savoir SMT-LIB 2 entrée:

(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, nous allons demander au prouveur Z3 si c'est 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 post original en 0,06 secondes.

En regardant cela à partir d'un point de vue plus général, on peut considérer cela comme étant une instance de premier ordre du programme de synthèse du problème, qui est un nouveau domaine de recherche sur lequel peu d'articles ont été publiés. Une recherche d' "program synthesis" filetype:pdf devrait vous obtenir a commencé.

Answer 3

Chaque 1 bit dans le multiplicateur est utilisé pour copier un des bits dans sa position correcte:

• 1 est déjà dans la bonne position, afin de multiplier par 0x0000000000000001.
• 2 doit être décalé 7 positions de bits vers la gauche, on multiplie donc par 0x0000000000000080 (bit 7 est réglé).
• 3 doit être décalée de 14 positions de bits vers la gauche, on multiplie donc par 0x0000000000000400 (14 bits est définie).
• et ainsi de suite jusqu'à
• 8 doit être décalé 49 positions de bits vers la gauche, on multiplie donc par 0x0002000000000000 (bit 49 est réglé).

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

Cela ne fonctionne que parce que les bits à être collectées ne sont pas trop rapprochées, de sorte que la multiplication des bits, qui ne vont pas ensemble dans notre schéma, soit à l'automne au-delà de la 64 bits ou dans la partie inférieure n'avez pas de soins.

Notez que les autres bits dans le numéro d'origine doit être 0. Ceci peut être réalisé par les masquer avec un ET de l'exploitation.

Answer 4

(Je n'avais jamais vu avant. Ce truc est génial!)

Je vais développer un peu sur Floris l'affirmation que lors de l'extraction d' n bits vous avez besoin d' n-1 de l'espace entre les non-consécutifs bits:

Ma première pensée (nous allons voir dans un instant comment ce n'est pas tout à fait) était que l'on pouvait faire de mieux: Si vous voulez extraire n bits, vous aurez une collision lors de l'extraction/déplacer les bits i si vous avez quelqu'un (non consécutifs avec bit i) en i-1 bits ou précédente en n-i bits de la suite.

Je vais vous donner quelques exemples pour illustrer:

...a..b...c... Travaux (personne dans les 2 bits après l' a, peu avant et peu après l' b,, et personne n'est dans les 2 bits avant d' c):

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

...a.b....c... Échoue en raison d' b est dans les 2 bits après l' a (et tire sur quelqu'un d'autre endroit où nous passons a):

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

...a...b.c... Échoue en raison d' b est dans les 2 bits précédant c (et est poussé en quelqu'un d'autre endroit où nous passons c):

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

...a...bc...d... Fonctionne car consécutives de bits de décalage ensemble:

  a000bc000d
+ 0bc000d000
+ 000d000000
= abcd000000

Mais nous avons un problème. Si nous utilisons n-i au lieu de n-1 nous avons pu le scénario suivant: si nous avons une collision à l'extérieur de la partie que nous nous soucions, ce que nous ne masque pas à la fin, mais dont l'transporter des bits de fin d'interférer dans les importants de l'onu-masqué de gamme? (et note: le n-1 exigence permet de s'assurer que cela n'arrive pas en vous assurant que l' i-1 bits d'après les nations unies masqué gamme sont claires lorsque l'on passe de la de la i- ième bit)

...a...b..c...d... D'échec potentiel à transporter bits, c est n-1 après b, mais satisfait n-i critères de:

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

Alors, pourquoi ne pas simplement revenir à cette "n-1 bits de l'espace"? Parce que nous pouvons faire mieux:

...a....b..c...d.. D'échec de l' "n-1 bits de l'espace" test", mais travaille pour notre peu-l'extraction de truc:

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

Je peux pas trouver un bon moyen de caractériser ces champs qui n' ont n-1 de l'espace entre les choses importantes, mais encore à travailler pour notre opération. Cependant, depuis que nous savons à l'avance les bits qui nous intéresse, nous pouvons vérifier notre filtre pour s'assurer que nous ne rencontrez pas de transporter des bits des collisions:

Comparer (-1 AND mask) * shift contre les attendus de tous ceux conséquent, -1 << (64-n) (pour la version 64 bits non signé)

La magie maj/multiplier à l'extrait de notre bits fonctionne si et seulement si les deux sont égaux.

Answer 5

En plus de la déjà d'excellentes réponses à cette question très intéressante, il peut être utile de savoir que ce bit à bit multiplication astuce a été connu dans l'ordinateur d'échecs de la communauté depuis 2007, où elle s'en va sous le nom de Magie BitBoards.

De nombreux moteurs d'échecs utiliser plusieurs entiers 64 bits (appelé bitboards) pour représenter les différents ensembles de pièces (1 bit par case occupée). Supposons qu'une pièce coulissante (tour, évêque, la reine) sur une certaine case d'origine peut se déplacer à plus K des places si pas de blocage des pièces étaient présents. L'aide au niveau du bit et de ceux qui sont dispersés K bits avec le bitboard de places occupées donne une K-bit, mot intégré au sein d'un entier de 64 bits.

La magie de multiplication peut être utilisé pour mapper ces éparpillés K bits pour le bas K bits d'un entier de 64 bits. De plus en plus ces K bits peut ensuite être utilisé pour indexer un tableau de pré-calculé bitboards que representst le permis de carrés que la pièce sur sa case d'origine peut réellement de se déplacer (en prenant soin de blocage des pièces etc.)

Typique d'un moteur d'échecs à l'aide de cette approche a 2 tables (une pour les tours, l'une pour les évêques, les reines à l'aide de la combinaison des deux) de 64 entrées (une par case d'origine) qui contiennent de telles pré-calculé résultats. À la fois la cote la plus élevée à code source fermé (Houdini) et open source, moteur d'échecs (Stockfish) à l'heure actuelle d'utiliser cette approche pour sa très haute performance.

La conclusion de ces magie des multiplicateurs se fait soit à l'aide d'une recherche exhaustive (optimisé avec les premiers seuils) ou avec de l'essai et erorr (par exemple, en essayant de nombreuses et aléatoires entiers 64 bits). Il n'y a eu aucun modèles de bits utilisés pendant le déménagement, génération pour qui la magie de la constante a pu être trouvé. Cependant, au niveau du bit transporter les effets sont généralement nécessaire lors de l'être mappé bits ont (presque) à côté des indices.

Autant que je sache, la très général SAT-solveur approachy par @Syzygie n'a pas été utilisé dans l'ordinateur d'échecs, et il ne semble y avoir aucune formelle de la théorie concernant l'existence et l'unicité de ces constantes magiques.