J'ai vu une technique intéressante utilisée dans une réponse à une autre question , et j'aimerais mieux la comprendre.
On nous donne un entier 64 bits non signé, et nous sommes 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 n'ont pas besoin d'être conservés.
La solution était de masquer les bits indésirables et de multiplier le résultat par 0x2040810204081
. Il s'avère que cela fait l'affaire.
Quelle est la généralité de cette méthode? Cette technique peut-elle être utilisée pour extraire n'importe quel sous-ensemble de bits? Sinon, comment déterminer si la méthode fonctionne ou non pour un ensemble particulier de bits?
Enfin, comment procéder pour trouver le multiplicateur (a?) Correct pour extraire les bits donnés?
Réponses:
Question très intéressante et astuce astucieuse.
Regardons 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 voulezab000000
.La solution consistait en deux étapes: un peu de masquage, suivi d'une multiplication. Le masque de bits est une opération ET simple qui transforme les bits non intéressants en zéros. Dans le cas ci-dessus, votre masque serait
00100100
et le résultat00a00b00
.Maintenant, la partie difficile: transformer cela en
ab......
.Une multiplication est un ensemble d'opérations de décalage et d'ajout. La clé est de permettre au débordement de «déplacer» les bits dont nous n'avons pas besoin et de mettre ceux que nous voulons au bon endroit.
La multiplication par 4 (
00000100
) déplacerait tout ce qui reste par 2 et vous amènerait àa00b0000
. Pour faireb
monter le nous devons multiplier par 1 (pour garder le a au bon endroit) + 4 (pour déplacer le b vers le haut). Cette somme est 5, et combinée avec les 4 précédentes, nous obtenons un nombre magique de 20, ou00010100
. L'original était00a00b00
après le masquage; la multiplication donne:De cette approche, vous pouvez étendre à de plus grands nombres et plus de bits.
L'une des questions que vous avez posées était "est-ce que cela peut être fait avec n'importe quel nombre 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 "b errant" dans le problème ci-dessus. Imaginez que nous devons faire cela à un nombre comme
xaxxbxxcx
. En suivant l'approche précédente, on pourrait penser que nous avons besoin de {x 2, x {1 + 4 + 16}} = x 42 (oooh - la réponse à tout!). Résultat:Comme vous pouvez le voir, cela fonctionne toujours, mais "seulement". La clé ici est qu'il y a "suffisamment d'espace" entre les bits que nous voulons pour pouvoir tout serrer. Je ne pouvais pas ajouter un quatrième bit d juste après c, car j'obtiendrais des instances où j'obtiens c + d, des bits pourraient porter, ...
Donc, sans preuve formelle, je répondrais aux parties les plus intéressantes de votre question comme suit: "Non, cela ne fonctionnera pas pour n'importe quel nombre de bits. Pour extraire N bits, vous avez besoin (N-1) d'espaces 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) des zéros entre les bits" est la suivante: si vous voulez extraire deux bits qui sont adjacents l'un à l'autre dans l'original, ET vous voulez les garder dans le même ordre, alors vous pouvez toujours le faire. Et aux fins de la règle (N-1), ils comptent comme deux bits.
Il y a un autre aperçu - inspiré par la réponse de @Ternary ci-dessous (voir mon commentaire là-bas). Pour chaque bit intéressant, vous avez seulement besoin d'autant de zéros à sa droite que vous avez besoin d'espace pour les bits qui doivent y aller. Mais aussi, il a besoin d'autant de bits à gauche qu'il y a de bits de résultat à gauche. Donc, si un bit b se retrouve en position m de n, il doit avoir m-1 zéros à sa gauche et nm zéros à sa droite. Surtout 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
Peut être déplacé en
même s'il n'y a qu'un seul 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". Il en va de même pour b et d (b a besoin de trois espaces à droite, d a besoin des mêmes trois à gauche). Ainsi, lorsque nous calculons le nombre magique, nous constatons qu'il y a des doublons:De toute évidence, si vous vouliez ces chiffres dans un ordre différent, vous devriez les espacer davantage. Nous pouvons reformuler la
(N-1)
règle: "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 retrouve en position m de n, il doit avoir m-1 zéros à sa gauche et nm zéros à sa droite. "@Ternary a souligné que cette règle ne fonctionne pas tout à fait, car il peut y avoir un report de bits ajoutant "juste à droite de la zone cible" - à savoir, lorsque les bits que nous recherchons sont tous un. 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
Pour simplifier, je nommerai les positions des bits
ABCDEFGHIJKLMNOP
Le calcul que nous allions faire était
Jusqu'à présent, nous pensions que tout ce qui était en dessous
abcde
(positionsABCDE
) n'aurait pas d'importance, mais en fait, comme l'a souligné @Ternary, sib=1, c=1, d=1
alors(b+c)
en positionG
, un peu se poursuivra en positionF
, ce qui signifie qu'en(d+1)
position,F
cela portera un peu dansE
- et notre le résultat est gâté. Notez que l'espace à droite du bit d'intérêt le moins significatif (c
dans cet exemple) n'a pas d'importance, car la multiplication provoquera un remplissage avec des zéros de au-delà du bit le moins significatif.Nous devons donc modifier notre règle (m-1) / (nm). S'il y a plus d'un bit qui a "exactement (nm) bits inutilisés vers la droite (sans compter le dernier bit du motif -" c "dans l'exemple ci-dessus), alors nous devons renforcer la règle - et nous devons faites-le de manière itérative!
Nous devons regarder non seulement le nombre de bits qui répondent au critère (nm), mais aussi ceux qui sont à (n-m + 1), etc. Appelons leur nombre Q0 (exactement
n-m
au bit suivant), Q1 ( n-m + 1), jusqu'à Q (N-1) (n-1). Ensuite, nous risquons de porter siSi vous regardez cela, vous pouvez voir que si vous écrivez une expression mathématique simple
et le résultat est
W > 2 * N
, alors vous devez augmenter le critère RHS d'un bit à(n-m+1)
. À ce stade, l'opération est sûre tant queW < 4
; si cela ne fonctionne pas, augmentez encore le critère, etc.Je pense qu'en suivant ce qui précède, vous obtiendrez un long chemin vers votre réponse ...
la source
Question très intéressante en effet. J'interviens avec mes deux cents, ce qui est que, si vous parvenez à énoncer des problèmes comme celui-ci en termes de logique de premier ordre sur la théorie des vecteurs de bits, alors les prouveurs de théorèmes sont votre ami, et peuvent potentiellement vous fournir très rapidement réponses à vos questions. Reprenons le problème posé comme théorème:
"Il existe des constantes 64 bits" masque "et" multiplicande "telles que, pour tous les vecteurs binaires 64 bits x, dans l'expression y = (x & masque) * multiplicande, nous avons que 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 «masque» et «multiplicande» satisfont cette propriété. Exprimons donc ceci en termes de quelque chose qu'un prouveur de théorème peut comprendre, à savoir l'entrée SMT-LIB 2:
Et maintenant, demandons au prouveur de théorème Z3 s'il s'agit d'un théorème:
Le résultat est:
Bingo! Il reproduit le résultat donné dans le message d'origine en 0,06 seconde.
En examinant cela d'un point de vue plus général, nous pouvons voir cela comme un exemple d'un problème de synthèse de programme de premier ordre, qui est un 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.la source
Chaque 1 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 par0x0000000000000001
.2
doit être décalé de 7 positions vers la gauche, donc nous multiplions par0x0000000000000080
(le bit 7 est défini).3
doit être décalé de 14 positions vers la gauche, donc nous multiplions par0x0000000000000400
(le bit 14 est défini).8
doit être décalé de 49 positions vers la gauche, donc nous multiplions par0x0002000000000000
(le bit 49 est défini).Le multiplicateur est la somme 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 tombe au-delà du 64 bits ou dans la partie inférieure ne se soucie pas.
Notez que les autres bits du numéro d'origine doivent être
0
. Ceci peut être réalisé en les masquant avec une opération ET.la source
(Je ne l'avais jamais vu auparavant. Cette astuce est géniale!)
Je développerai un peu l'assertion de Floris selon laquelle lors de l'extraction de
n
bits, vous avez besoin d'n-1
espace entre les bits non consécutifs:Ma pensée initiale (nous verrons dans une minute comment cela ne fonctionne pas tout à fait) était que vous pourriez faire mieux: si vous voulez extraire des
n
bits, vous aurez une collision lors de l'extraction / décalage de bitsi
si vous avez quelqu'un (non - consécutif avec biti
) dans lesi-1
bits précédents ou lesn-i
bits suivants.Je vais donner quelques exemples pour illustrer:
...a..b...c...
Fonctionne (personne dans les 2 bits aprèsa
, le bit avant et le bit aprèsb
, et personne n'est dans les 2 bits avantc
):...a.b....c...
Échoue car seb
trouve dans les 2 bits aprèsa
(et se fait tirer à la place de quelqu'un d'autre lorsque nous passonsa
):...a...b.c...
Échoue car seb
trouve dans les 2 bits précédentsc
(et est poussé à la place de quelqu'un d'autre lorsque nous passonsc
):...a...bc...d...
Fonctionne parce que les bits consécutifs se déplacent ensemble:Mais nous avons un problème. Si nous utilisons à la
n-i
place den-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 masquons à la fin, mais dont les bits de transport finissent par interférer dans la plage non masquée importante ? (et remarque: l'n-1
exigence fait en sorte que cela ne se produise pas en s'assurant que lesi-1
bits après notre plage non masquée sont clairs lorsque nous décalons lei
th bit)...a...b..c...d...
La défaillance potentielle sur les bits de portage sec
situen-1
aprèsb
, mais satisfait auxn-i
critères:Alors pourquoi ne revenons-nous pas simplement à cette
n-1
exigence de " bits d'espace"? Parce que nous pouvons faire mieux :...a....b..c...d..
Échoue len-1
test " bits d'espace", mais fonctionne pour notre astuce d'extraction de bits:Je ne peux pas trouver un bon moyen de caractériser ces champs qui n'ont pas d'
n-1
espace entre les bits importants, mais qui fonctionneraient quand même pour notre opération. Cependant, puisque nous savons à l'avance quels bits nous intéressent, nous pouvons vérifier notre filtre pour nous assurer que nous ne subissons pas de collisions de bits de transport:Comparer
(-1 AND mask) * shift
avec le résultat tout-en-un attendu,-1 << (64-n)
(pour 64 bits non signé)Le décalage / multiplication magique pour extraire nos bits fonctionne si et seulement si les deux sont égaux.
la source
b
se retrouve en positionm
den
, il doit avoir desm-1
zéros à sa gauche et desn-m-1
zéros à sa droite. Surtout 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. C'est marrant!En plus des réponses déjà excellentes à cette question très intéressante, il pourrait être utile de savoir que cette astuce de multiplication au niveau du bit est connue dans la communauté des échecs informatiques depuis 2007, où elle s'appelle Magic BitBoards .
De nombreux moteurs d'échecs informatiques utilisent plusieurs entiers 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 la plupart des
K
cases si aucune pièce de blocage n'était présente. L'utilisation au niveau du bit et de cesK
bits dispersés avec le bitboard des carrés occupés donne unK
mot bits incorporé dans un entier de 64 bits.La multiplication magique peut être utilisée pour mapper ces
K
bits dispersés aux bits inférieursK
d'un entier 64 bits. Ces plus basK
bits peuvent ensuite être utilisés pour indexer un tableau de tableaux de bord pré-calculés qui représentent les carrés autorisés vers lesquels la pièce sur son carré d'origine peut réellement se déplacer (en prenant soin de bloquer les pièces, etc.)Un moteur d'échecs typique utilisant cette approche a 2 tables (une pour les tours, une pour les évêques, les reines utilisant la combinaison des deux) de 64 entrées (une par carré d'origine) qui contiennent de tels résultats pré-calculés. La source fermée la mieux notée ( Houdini ) et le moteur d'échecs open source ( Stockfish ) 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 coupures précoces), soit avec des essais et des erreurs. (par exemple en essayant de nombreux nombres entiers aléatoires de 64 bits). Il n'y a eu aucun motif de bits utilisé pendant la génération de mouvement pour lequel aucune constante magique n'a pu être trouvée. Cependant, des effets de transport au niveau du bit sont généralement nécessaires lorsque les bits à mapper ont des indices (presque) adjacents.
AFAIK, l'approche très générale du solveur SAT par @Syzygy n'a pas été utilisée 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.
la source