Comment inverser les bits d'un octet?

Par exemple, en PHP, comment pourrais-je inverser les bits de l'octet 11011111 à 11111011?

  • eh bien, dans ce cas, tourner à droite en 5 positions 😛
  • Votre question a besoin d'un peu plus de précisions. Par exemple, est-ce une chaîne ou un entier dont les bits que vous essayez de flip? Le contexte est très important lorsque vous posez une question.
  • lol, vous avez failli m'a fait cracher mon café sur mon clavier =P
  • +1 pour Kletz, mais pour ce cas vous pouvez faire beaucoup plus simple chose: attribuer avec 0b11111011 valeur (pour certaines architectures, il pourrait être beaucoup plus efficace 😉 ).
  • oui, le vôtre est beaucoup plus simple XD
InformationsquelleAutor secret | 2009-11-06
  1. 17

    La droite de l'avant l'approche est d'effectuer 8 masques, 8 tourne, et 7 ajouts:

    $blah = $blah & 128 >> 7 + $blah & 64 >> 5 + $blah & 32 >> 3 + $blah & 16 >> 1 + $blah & 8 << 1 + $blah & 4 << 3 + $blah & 2 << 5 + $blah & 1 << 7;
    • Qui a obtenu deux upvotes?
    • 3 upvotes, avec le mien. Avez-vous une meilleure solution. Poste et vous aurez mon vote aussi!
    • Eh bien, c'est répondre à la question 🙂
    • qui théorème mathématique ou de l'algorithme est que cette réponse est basée sur?
    • "Le Principe de la Force Brutale"
    • Ce n'est pas un théorème, ses littéralement juste la reconstruction d'un octet par la réorganisation de l'bits. J'ai dû 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

    InformationsquelleAutor Epsilon Prime
  2. 16

    Si vous avez déjà les bits sous la forme d'une chaîne de caractères, utilisez strrev.

    Si pas, convertissez d'abord l'octet de sa représentation binaire en utilisant decbin, puis en sens inverse à l'aide de strrev, puis revenir à l'octet (si nécessaire) à l'aide de bindec.

    • La meilleure réponse de l'OMI qui va travailler pour les cas généraux. Ces bits de décalage, rotation, etc, sont tout simplement le ciblage de l'exemple de la valeur donnée et de ne pas travailler pour binaire aléatoire des chaînes ..
    • +1 c'est Ce que j'aurais suggéré avais-je pas bâclé la compréhension initiale.
    • Je suis vraiment curieux de savoir pourquoi j'ai été downvoted ici...
    InformationsquelleAutor Konamiman
  3. 16

    Voir la section sur l'inversion de séquences de bits dans Peu Se Tourner Les Hacks. Doit être facile à adapter l'une des techniques en PHP.

    Bien que probablement pas pratique pour PHP, il y a de particulièrement fascinant, une aide de 3 64bit opérations:

    unsigned char b; //reverse this (8-bit) byte
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
    • Pouvez-vous expliquer ce "ULL" signifie ici?
    • c'est un unsigned long long, le suffixe indique au compilateur que ce produit c'est un 64 bits non signé entier littéral.
    • pourquoi c'est une solution si elle n'est pas pratique pour php?
    InformationsquelleAutor Paul Dixon
  4. 8

    Le moyen le plus rapide, mais aussi le seul nécessitant plus d'espace est un lieu de recherche, dans lequel chaque valeur possible d'un octet (256, si vous allez pour l'ensemble de la gamme), est associé à son "inversé" équivalent.

    Si vous avez seulement quelques octets à traiter, des opérateurs bit par bit vais faire, mais qui sera plus lent, peut-être quelque chose comme:

    function reverseBits($in) {
  $out = 0;

  if ($in & 0x01) $out |= 0x80;
  if ($in & 0x02) $out |= 0x40;
  if ($in & 0x04) $out |= 0x20;
  if ($in & 0x08) $out |= 0x10;
  if ($in & 0x10) $out |= 0x08;
  if ($in & 0x20) $out |= 0x04;
  if ($in & 0x40) $out |= 0x02;
  if ($in & 0x80) $out |= 0x01;

  return $out;
}
    • Historiquement, j'ai trouvé que le fait d'avoir un 256 octets table de recherche est le moyen le plus rapide à réaliser que c'est juste une recherche. 256 octets n'est pas beaucoup d'espace à consacrer à quelque chose de ce genre si il faut être rapide. Bien que le ci-dessus reverseBits fonction est petit et serré que vous pouvez obtenir le code sans avoir une liste de choix. Aussi pour une petite optimisation on pouvait changer la première { $out |= 0x80;} pour { $out = 0x80;} comme vous le savez, la première fois que vous vous êtes joint torique avec de 0.
    • d'accord, j'avais tendance à utiliser la recherche de tableau dans la plupart des cas. Une solution intermédiaire serait d'avoir un petit tableau, pour 4 bits, et de faire deux recherches associée à la multiplication/division de la gauche des bits quad). Cette façon de faire peut également être utilisé pour traiter les dire des entiers plutôt que des octets. (L'inconvénient de l'approche de recherche est que son besoin d'espace se développe de façon exponentielle, en vertu de laquelle le code d'appraoch linéaire (w/ en ce qui concerne le nombre de bits).
    InformationsquelleAutor mjv
  5. 3

    C'est O(n) avec la longueur de la mèche. Il suffit de penser de l'entrée comme une pile et d'écrire sur la sortie de la pile.

    Ma tentative de l'écriture de ce en PHP.

    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;
}
    InformationsquelleAutor Jeffery Williams
  6. 2

    Essayez de vous procurer ce livre, il y a tout le chapitre sur les bits de réversion:
    Hacker Plaisir. Mais s'il vous plaît vérifiez d'abord du contenu, si cela vous convient.

    InformationsquelleAutor Roman Nikitchenko
  7. 2

    Certaines personnes ont été suggérant une table de recherche, alors que j'ai été faire un:

    [
0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0, 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8, 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4, 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC, 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2, 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA, 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6, 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE, 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1, 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9, 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5, 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED, 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3, 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB, 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7, 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF, 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF,
][$byte]

    Et voici une version en caractères:

    [
"\x00", "\x80", "\x40", "\xC0", "\x20", "\xA0", "\x60", "\xE0", "\x10", "\x90", "\x50", "\xD0", "\x30", "\xB0", "\x70", "\xF0",
"\x08", "\x88", "\x48", "\xC8", "\x28", "\xA8", "\x68", "\xE8", "\x18", "\x98", "\x58", "\xD8", "\x38", "\xB8", "\x78", "\xF8",
"\x04", "\x84", "\x44", "\xC4", "\x24", "\xA4", "\x64", "\xE4", "\x14", "\x94", "\x54", "\xD4", "\x34", "\xB4", "\x74", "\xF4",
"\x0C", "\x8C", "\x4C", "\xCC", "\x2C", "\xAC", "\x6C", "\xEC", "\x1C", "\x9C", "\x5C", "\xDC", "\x3C", "\xBC", "\x7C", "\xFC",
"\x02", "\x82", "\x42", "\xC2", "\x22", "\xA2", "\x62", "\xE2", "\x12", "\x92", "\x52", "\xD2", "\x32", "\xB2", "\x72", "\xF2",
"\x0A", "\x8A", "\x4A", "\xCA", "\x2A", "\xAA", "\x6A", "\xEA", "\x1A", "\x9A", "\x5A", "\xDA", "\x3A", "\xBA", "\x7A", "\xFA",
"\x06", "\x86", "\x46", "\xC6", "\x26", "\xA6", "\x66", "\xE6", "\x16", "\x96", "\x56", "\xD6", "\x36", "\xB6", "\x76", "\xF6",
"\x0E", "\x8E", "\x4E", "\xCE", "\x2E", "\xAE", "\x6E", "\xEE", "\x1E", "\x9E", "\x5E", "\xDE", "\x3E", "\xBE", "\x7E", "\xFE",
"\x01", "\x81", "\x41", "\xC1", "\x21", "\xA1", "\x61", "\xE1", "\x11", "\x91", "\x51", "\xD1", "\x31", "\xB1", "\x71", "\xF1",
"\x09", "\x89", "\x49", "\xC9", "\x29", "\xA9", "\x69", "\xE9", "\x19", "\x99", "\x59", "\xD9", "\x39", "\xB9", "\x79", "\xF9",
"\x05", "\x85", "\x45", "\xC5", "\x25", "\xA5", "\x65", "\xE5", "\x15", "\x95", "\x55", "\xD5", "\x35", "\xB5", "\x75", "\xF5",
"\x0D", "\x8D", "\x4D", "\xCD", "\x2D", "\xAD", "\x6D", "\xED", "\x1D", "\x9D", "\x5D", "\xDD", "\x3D", "\xBD", "\x7D", "\xFD",
"\x03", "\x83", "\x43", "\xC3", "\x23", "\xA3", "\x63", "\xE3", "\x13", "\x93", "\x53", "\xD3", "\x33", "\xB3", "\x73", "\xF3",
"\x0B", "\x8B", "\x4B", "\xCB", "\x2B", "\xAB", "\x6B", "\xEB", "\x1B", "\x9B", "\x5B", "\xDB", "\x3B", "\xBB", "\x7B", "\xFB",
"\x07", "\x87", "\x47", "\xC7", "\x27", "\xA7", "\x67", "\xE7", "\x17", "\x97", "\x57", "\xD7", "\x37", "\xB7", "\x77", "\xF7",
"\x0F", "\x8F", "\x4F", "\xCF", "\x2F", "\xAF", "\x6F", "\xEF", "\x1F", "\x9F", "\x5F", "\xDF", "\x3F", "\xBF", "\x7F", "\xFF",
][ord($byte)];
    InformationsquelleAutor FluorescentGreen5
  8. 1

    Je suis en désaccord avec l'aide d'une table comme (pour de plus grands nombres entiers) la quantité de temps nécessaire pour le charger en mémoire l'emporte sur les performances de traitement.

    J'ai aussi utiliser un bit à bit de masquage approche pour un O(logn) solution, qui ressemble à:

    MASK = onescompliment of 0    
while SIZE is greater than 0
SIZE = SIZE shiftRight 1
MASK = MASK xor (MASK shiftLeft SIZE)
output = ((output shiftRight  SIZE) bitwiseAnd MASK) bitwiseOR ((onescompliment of MASK) bitwiseAnd (output shfitLeft SIZE))

    L'avantage de cette approche est qu'il gère la taille de votre entier comme un argument

    en php ce qui pourrait ressembler à:

    function bitrev($bitstring, $size){
$mask = ~0;
while ($size > 0){
$size = $size >> 1;
$mask = $mask ^ ($mask << $size);
$bitstring = (($bitstring >> $size) & $mask) | ((~$mask) & ($bitstring << $size));
}
}

    à moins que j'ai foiré mon php quelque part 🙁

    • si vous effectuez l'opération qu'une seule fois, d'une table de recherche est mauvais. Mais si c'est souvent l'opération, il devrait surpasser toute autre approche.
    InformationsquelleAutor tzenes