Как инвертировать биты байта?

Например, в PHP, как я инвертировал бы биты байта 11011111 кому: 11111011?

6
задан FluorescentGreen5 20 July 2019 в 12:25
поделиться

7 ответов

Это O (n) с длиной в битах. Просто подумайте о вводе как о стеке и напишите в выходной стек.

Моя попытка написать это на 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;
}
3
ответ дан 8 December 2019 в 02:02
поделиться

Прямой подход состоит в том, чтобы выполнить 8 масок, 8 поворотов и 7 сложений:

$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;
17
ответ дан 8 December 2019 в 02:02
поделиться

Если у вас уже есть биты в форме строки, используйте strrev .

Если нет, сначала преобразуйте байт в его двоичное представление, используя ] decbin , затем переверните его с помощью strrev, затем вернитесь к байту (если необходимо) с помощью bindec .

16
ответ дан 8 December 2019 в 02:02
поделиться

Проверьте раздел об изменении битовых последовательностей в Bit Twiddling Hacks . Должно быть легко адаптировать один из методов в PHP.

Хотя это, вероятно, не практично для PHP, есть особенно интересный вариант, использующий 3 64-битных операции:

unsigned char b; // reverse this (8-bit) byte
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
16
ответ дан 8 December 2019 в 02:02
поделиться

Самый быстрый способ, но также тот, который требует больше места, - это поиск, при котором каждое возможное значение байта (256, если вы идете для всего диапазона) связано с его «обратным» эквивалентом.

Если у вас есть только несколько таких байтов для обработки, побитовые операторы будут работать, но это будет медленнее, может быть что-то вроде:

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;
}
8
ответ дан 8 December 2019 в 02:02
поделиться

Попытайтесь достать эту книгу, там целая глава о реверсии битов: Восторг хакера . Но сначала проверьте содержание, если это вам подходит.

2
ответ дан 8 December 2019 в 02:02
поделиться

Я не согласен с использованием таблицы поиска, поскольку (для больших целых чисел) время, необходимое для ее загрузки в память, превосходит производительность обработки.

Я также использую побитовое маскирование подход для решения O (logn), который выглядит так:

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))

Преимущество этого подхода в том, что он обрабатывает размер вашего целого числа в качестве аргумента

в php это может выглядеть так:

function bitrev($bitstring, $size){

  $mask = ~0;
  while ($size > 0){

    $size = $size >> 1;
    $mask = $mask ^ ($mask << $size);
    $bitstring = (($bitstring >> $size) & $mask) | ((~$mask) & ($bitstring << $size));
  }
}

, если я не напортачил php где-нибудь: (

1
ответ дан 8 December 2019 в 02:02
поделиться
Другие вопросы по тегам:

Похожие вопросы: