J'ai écrit du code pour vérifier si une séquence de bits peut être trouvée dans une séquence de bits différente.
Par exemple, ci-dessous, la séquence de bits de 9 se trouve dans la séquence de bits de 25, mais pas dans celle de 15 .
La façon dont je fais cela maintenant est de prendre la représentation binaire de chaîne et d'exécuter une regex pour vérifier si l'une correspond à l'autre. Idéalement, j'aimerais le faire en utilisant des opérations au niveau du bit, et j'ai examiné la vérité sur l'opération au niveau du bit table et apparemment XNOR semble faire ce dont j'ai besoin .. mais je n'a pas eu beaucoup de succès avec cela.
Comment feriez-vous ce type de correspondance en utilisant des opérations au niveau du bit?
Merci
#!/usr/bin/python3
N=9
H1=15
H2=25
for x in [N,H1,H2]:
print('{:032b}'.format(x))
Nb,H1b,H2b=[format(x,"b") for x in [N,H1,H2]]
import re
for x in [H1b,H2b]:
print(bool(re.search(Nb,x)))
p>
3 Réponses :
En supposant que votre chaîne de bits et vos motifs ne sont pas trop longs (c'est-à-dire qu'ils tiennent dans un long long), voici comment cela peut être écrit en C.
// searchs if pattern is present within bit string tosearch
// patternlenth is the number of bits in the pattern
// returns the required shift for the firt match is found
// assumes the number of bits in tosearch bit sting is 64
// returns -1 is pattern is not found
int bitstringsearch(unsigned long long tosearch, long long pattern, int patternlength){
long long mask = (1<<patternlength) -1 ;
// mask is a set of patternlength consecutive ones at lsb
printf("%llx\n",mask);
for (int i=0; i<64-patternlength; i++){
if ( (~(tosearch ^ pattern) & mask) == mask)
// checks is the patternlenth LSB bits of tosearch are equal
// to pattern
return i; // yes, returns the current shift
tosearch >>=1; // shift bitsting to search search
}
return -1; // not found
}
La traduction en python devrait être évidente . Cela peut facilement être étendu pour rechercher toutes les correspondances.
J'ai le sentiment que cela peut être réalisé en vérifiant une relation (simple) entre les 2 nombres, mais je ne peux pas mettre le doigt dessus. Ci-dessous, une alternative.
code00.py :
[cfati@CFATI-5510-0:e:\Work\Dev\StackOverflow\q057744847]> "e:\Work\Dev\VEnvs\py_064_03.07.03_test0\Scripts\python.exe" code00.py Python 3.7.3 (v3.7.3:ef4ec6ed12, Mar 25 2019, 22:22:05) [MSC v.1916 64 bit (AMD64)] 64bit on win32 0 (0) contains 9 (1001): False 1 (1) contains 9 (1001): False 8 (1000) contains 9 (1001): False 9 (1001) contains 9 (1001): True 15 (1111) contains 9 (1001): False 18 (10010) contains 9 (1001): True 25 (11001) contains 9 (1001): True 51 (110011) contains 9 (1001): True 54 (110110) contains 9 (1001): False 90 (1011010) contains 9 (1001): False 549 (1000100101) contains 9 (1001): True 17477 (100010001000101) contains 9 (1001): False Done.
Remarques :
#!/usr/bin/env python3
import sys
import math
def get_mask(n, base=2):
magnitude = math.ceil(math.log(n, base))
return base ** magnitude - 1
def contains_binary(container, containee):
mask = get_mask(containee)
while containee <= container:
if container & mask == containee:
return True
containee <<= 1
mask <<= 1
return False
def main():
op1 = 9
numbers = [
0,
1,
8,
9,
15,
18,
25,
51,
54,
90,
549,
17477,
]
for op0 in numbers:
print("{0:d} ({1:s}) contains {2:d} ({3:s}): {4:}".format(op0, bin(op0)[2:], op1, bin(op1)[2:], contains_binary(op0, op1)))
if __name__ == "__main__":
print("Python {0:s} {1:d}bit on {2:s}\n".format(" ".join(item.strip() for item in sys.version.split("\n")), 64 if sys.maxsize > 0x100000000 else 32, sys.platform))
main()
print("\nDone.")
pour vérifier si votre séquence Nb est dans l'autre séquence, vous pouvez utiliser:
Nb in H1b Nb in H2b
ou vous pouvez utiliser:
H1b.find(Nb) != -1 H2b.find(Nb) != -1
XNOR peut être réalisé par exemple par
(~ (N ^ H1)), mais pourriez-vous expliquer pourquoi pensez-vous que XNOR est la solution? que vérifierez-vous sur le résultat du XNOR pour déterminer s'il est vrai ou faux?Je pensais vérifier
(~ (N ^ H1)) == Nmais j'ai essayé et le XNOR a donné un résultat négatif, ce qui ... est loin de ce à quoi je m'attendais. Mais c'est peut-être parce que le XNOR en Python est effectué sur des entiers signés. La raison pour laquelle j'ai mentionné XNOR est que sa table ressemble à un contrôle d'égalité petit à petit et que cela lui a semblé un bon ajustement.Il vous donne tous les 1 si les bits sont complètement égaux, nous pouvons l'utiliser pour déterminer si le motif de bits est contenu "aligné à droite". mais disons, qu'en est-il de
H3 = 51? Le motif de bits deN = 9y est toujours contenu (et votre solution regex retournera en effet vrai), mais toute solution au niveau du bit nécessitera un certain décalage, cela devient beaucoup moins élégant.@ Adam.Er8 c'est bien de ne gérer que la casse alignée. Les autres peuvent être gérés en déplaçant N dans différentes positions.
OK, je vais essayer