Par exemple, en PHP, comment puis-je inverser les bits de l'octet 11011111 à 11111011 ?
9 Réponses :
essayer d'obtenir ce livre, il y a un chapitre entier sur les bits Reversion: Le délice de Hacker . Mais veuillez vérifier le contenu d'abord si cela vous convient.
Le moyen le plus rapide, mais aussi celui qui nécessite plus d'espace est une recherche, dans laquelle chaque valeur possible d'un octet (256 si vous optez pour toute la plage) est associée à son équivalent "inversé".
Si vous Vous n'avez que quelques octets de ce type à gérer, les opérateurs bit-sisage le feront, mais cela sera plus lent, peut-être quelque chose comme:
Historiquement, j'ai découvert que la table de recherche de 256 octets est le moyen le plus rapide de le réaliser car il s'agit simplement d'une recherche. 256 octets n'est pas beaucoup d'espace pour consacrer à quelque chose comme ça si cela doit être rapide. Bien que la fonction de version versemblée ci-dessus soit aussi petite et serrée, car vous pouvez obtenir le code sans rechercher. Également pour une petite optimisation, vous pouvez modifier le premier {$ out | = 0x80;} à {$ OUT = 0x80;} Comme vous le savez à la première fois avec 0.
@skirmish, d'accord, j'avais tendance à utiliser la matrice de recherche dans la plupart des cas. Une solution intermédiaire serait d'avoir un tableau plus petit, pour 4 bits, et effectuera deux recherches avec la multiplication / division associée pour le bit-quad plus à gauche). Cette façon de faire peut également être utilisée pour faire face à des entiers plutôt que ces octets. (La vocation de l'approche de la recherche est que son exigence spatiale augmente de manière exponentielle, selon laquelle l'appréciation codée linéairement (w / considère le nombre de bits).
L'approche directe consiste à effectuer 8 masques, 8 pivote et 7 ajouts:
@Kinopiko: 3 upvotes, avec les miens. Avez-vous une meilleure solution. Postez-le et vous obtiendrez mon vote aussi!
Eh bien, il répond à la question :-)
quel théorème ou algorithme mathématique est cette réponse basée sur?
"Le principe de la force brute"
Ce n'est pas un théorème, c'est littéralement reconstruit simplement un octet en réorganisant les bits. Je devais utiliser des parenthèses et ou au lieu de + si: (128 & N) >> 7 | (64 & N) >> 5 | (32 & N) >> 3 | (16 & N) >> 1 | (8 & N) << 1 | (4 & N) << 3 | (2 & N) << 5 | (1 & N) << 7
Si vous avez déjà les bits sous la forme d'une chaîne, utilisez str devev < / a>.
Si non, convertissez d'abord l'octet en une représentation binaire en utilisant Décbin , puis inverser à l'aide de STRREV, puis revenez à l'octet (si nécessaire) en utilisant Bindec .
La meilleure réponse imo qui fonctionnera pour des cas généraux. Ces mouvements de bits, la rotation, etc. ciblent simplement l'exemple de valeur donnée et ne fonctionneront pas pour des chaînes binaires aléatoires.
+1 C'est ce que j'aurais suggéré que je n'ai pas notté la compréhension initiale.
Vérifiez la section sur les séquences de bits d'inverser dans Bit Twiddling Hacks . Devrait être facile d'adapter l'une des techniques en PHP.
Bien que probablement pas pratique pour PHP, il y a un élément particulièrement fascinant en utilisant 3 opérations 64 bits:
Pouvez-vous expliquer ce que signifie "ull" ici?
@mask c'est un peu signalé longtemps, le suffixe indique au compilateur que ce qui procède c'est un littéral entier non signé de 64 bits.
Pourquoi c'est une solution si ce n'est pas pratique pour PHP?
Je ne suis pas d'accord avec l'utilisation d'une table RECHERCHE comme (pour les entiers plus importants), le temps nécessaire pour le charger dans la mémoire en matière de traitement des performances de traitement.
J'utilise également une approche de masquage des bits pour une solution O (logn) qui On dirait: L'avantage de cette approche est-il gère la taille de votre entier comme argument dans PHP, cela pourrait ressembler à: sauf si je fous mon php quelque part: (
Si vous effectuez l'opération juste une fois, une table de recherche est mauvaise. Mais si c'est une opération fréquente, il devrait surperformer toute autre approche.
Ceci est O (N) avec la longueur du bit. Pensez simplement à l'entrée comme une pile et écrivez à la pile de sortie.
Ma tentative d'écrire cela en PHP. P>
function bitrev ($inBits, $bitlen){
$cloneBits=$inBits;
$inBits=0;
$count=0;
while ($count < $bitlen){
$count=$count+1;
$inBits=$inBits<<1;
$inBits=$inBits|($cloneBits & 0x1);
$cloneBits=$cloneBits>>1;
}
return $inBits;
}
Certaines personnes suggèrent une table de recherche, alors que je fais un: et voici une version de caractère:
En 1984, j'ai proposé cette solution (sur un commodore Vic20 et la mémoire était une prime à l'époque). Donc, mon calcul à deux lignes en basique a fait l'affaire. Table simple, rapide et sans mémoire-chargeuse.
depuis Le programme renvoie Programme: P> = 11001111 = 207 code>, entrez ceci dans w. P> v = 243 ... = 11110011 code> p> input w: v=0: for x=0 to 7
if w>(2^(7-x))-1 then v=v+(2^x): w=w-(2^(7-x))
next
print v
Eh bien, dans ce cas, tournez à droite par 5 positions: p
Votre question a besoin d'un peu plus de clarification. Par exemple, est-ce une chaîne ou un entier réel dont vous essayez de retourner? Le contexte est très important lorsque vous posez une question.
@ Klez - +1 lol, tu m'as presque fait cracher mon café sur mon clavier = p
+1 to kletz, mais pour ce cas, vous pouvez faire beaucoup plus simple: Attribuer une valeur 0B11111011 (pour certaines architectures, cela pourrait être très efficace;)).
@Roman +1, oui, le vôtre est beaucoup plus simple xD