Как выполнить круговое вращение байта?

Question

Я должен реализовать функцию, которая выполняет круговое вращение влево и вправо. Так что я написал одно и то же для обеих операций. Например, если вы вращаете влево, 1010 становится 0101. Это правильно?

unsigned char rotl(unsigned char c){
  int w;
  unsigned char s=c;
  for(w=7; w>=0; w--){
   int b=(int)getBit(c,w);//
   if(b==0){
     s=clearBit(s,7-w);
   }
   else if(b==1){
     s=setBit(s,7-w);
   }
  }
 return s;
}
unsigned char getBit(unsigned char c, int n) {
   return c=(c&(1<<n))>>n;

}

unsigned char setBit(unsigned char c, int n) {
   return c=c|(1<<n);
}

unsigned char clearBit(unsigned char c, int n) {
  return c=c &(~(1<<n));
}

Answer 1

В C нет оператора поворота, но если вы напишите:

unsigned char rotl(unsigned char c)
{
    return (c << 1) | (c >> 7);
}

затем, в соответствии с этим: http://www.linux-kongress.org/2009/slides/compiler_survey_felix_von_leitner.pdf (стр. 56), компиляторы выяснят, что вы хотите сделать, и выполните вращение всего за один (очень быстро).) инструкция.

Answer 2

Читая ответы и комментарии, кажется, что вы пытаетесь достичь некоторой путаницы - возможно, это из-за слов, которые вы используете. В битовых манипуляциях есть несколько "стандартных" вещей, которые вы можете сделать. Я суммирую некоторые из них, чтобы помочь прояснить различные концепции. Во всем, что следует, я буду использовать abcdefgh обозначить 8 бит (это могут быть единицы или нули) - и при их перемещении одна и та же буква будет относиться к одному и тому же биту (возможно, в другой позиции); если немного становится "определенно 0 или же 1Я буду обозначать это как таковой).

1) Сдвиг битов: по сути, это "быстрое умножение или деление на степень 2". Используемый символ << для "сдвига влево" (умножить) или >> для правого смещения (делить). таким образом

abcdefgh >> 2 = 00abcdef

(эквивалентно "разделить на четыре") и

abcdefgh << 3 = abcdefgh000 

(эквивалентно "умножить на восемь" - и предполагая, что было "пространство" для сдвига abc в; в противном случае это может привести к переполнению)

2) Битовая маскировка: иногда вы хотите установить определенные биты на ноль - вы делаете это, выполняя операцию И с числом, у которого есть те, где вы хотите сохранить бит, и ноль, где вы хотите очистить бит

abcdefgh & 01011010 = 0b0de0g0

Или, если вы хотите убедиться, что определенные биты равны единице, вы используете операцию ИЛИ:

abcdefgh | 01011010 = a1c11f1h

3) Сдвиг по кругу: это немного сложнее - есть случаи, когда вы хотите "перемещать биты", при этом те, которые "падают с одного конца", вновь появляются на другом конце. Для этого в Си нет символа и нет "быстрой инструкции" (хотя большинство процессоров имеют встроенную инструкцию, которую ассемблерный код может использовать для вычислений БПФ и тому подобного). Если вы хотите сделать "левый круговой сдвиг" на три позиции:

circshift(abcdefgh, 3) = defghabc

(примечание = нет circshift функция в стандартных библиотеках C, хотя она существует и в других языках - например, Matlab). К тому же, "сдвиг вправо" будет

circshift(abcdefgh, -2) = ghabcdef

4) Обращение битов: иногда вам нужно инвертировать биты в числе. При обращении битов нет ни "левого", ни "правого" - обратное обратное:

reverse(abcdefgh) = hgfedcba

Опять же, в стандартных библиотеках Си нет "обратной" функции.

Теперь давайте рассмотрим некоторые приемы реализации этих двух последних функций (circshift а также reverse) в C. Есть целые веб-сайты, посвященные "умным способам манипулирования битами" - см., например, превосходный http://graphics.stanford.edu/~seander/bithacks.html замечательный сборник "битовых хаков", хотя некоторые из них могут быть немного продвинутыми...

unsigned char circshift(unsigned char x, int n) {
  return (x << n) | (x >> (8 - n));
}

При этом используются две хитрости из вышеперечисленного: сдвиг битов и использование операции ИЛИ для установки битов в конкретные значения. Давайте посмотрим, как это работает, для n = 3 (примечание - я игнорирую биты выше 8-го, поскольку возвращаемый тип функции unsigned char):

(abcdefgh << 3)       = defgh000
(abcdefgh >> (8 - 3)) = 00000abc

Принимая побитовое ИЛИ этих двух дает

defgh000 | 00000abc = defghabc

Это именно тот результат, который мы хотели. Обратите внимание, что a << n такой же как a >> (-n) - другими словами, смещение вправо на отрицательное число такое же, как смещение влево на положительное число, и наоборот.

Теперь давайте посмотрим на reverse функция. Есть "быстрые способы" и "медленные способы" сделать это. Ваш код, приведенный выше, дал "очень медленный" способ - позвольте мне показать вам "очень быстрый" способ, предполагая, что ваш компилятор допускает использование 64-битной (long long) целые числа.

unsigned char reverse(unsigned char b) {
  return (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;
}

Вы можете спросить себя "что только что произошло"??? Позволь мне показать тебе:

b = abcdefgh

* 0x0000000202020202 = 00000000 00000000 0000000a bcdefgha bcdefgha bcdefgha bcdefgha bcdefgh0
& 0x0000010884422010 = 00000000 00000000 00000001 00001000 10000100 01000010 00100000 00010000
                     = 00000000 00000000 0000000a 0000f000 b0000g00 0c0000h0 00d00000 000e0000

Обратите внимание, что теперь у нас есть все биты ровно один раз - они просто в довольно странном порядке. Разделение по модулю 1023 "сворачивает" интересующие друг друга кусочки - это как магия, и я не могу этого объяснить. Результат действительно

hgfedcba

Немного менее туманный способ достижения того же самого (менее эффективный, но работающий для больших чисел довольно эффективно) признает, что если вы меняете соседние биты, затем соседние битовые пары, затем соседние полубайты (4-битные группы) и т. Д. - в итоге вы получите полное обращение немного. В этом случае обращение байта становится

unsigned char bytereverse(unsigned char b) {
  b = (b & 0x55) << 1 | (b & 0xAA) >> 1; // swap adjacent bits
  b = (b & 0x33) << 2 | (b & 0xCC) >> 2; // swap adjacent pairs
  b = (b & 0x0F) << 4 | (b & 0xF0) >> 4; // swap nibbles
  return b;
}

В этом случае происходит следующее байта b = abcdefgh:

b & 0x55 = abcdefgh & 01010101 = 0b0d0f0h << 1 = b0d0f0h0
b & 0xAA = abcdefgh & 10101010 = a0c0e0g0 >> 0 = 0a0c0e0g
OR these two to get badcfehg

Следующая строка:

b & 0x33 = badcfehg & 00110011 = 00dc00hg << 2 = dc00hg00
b & 0xCC = badcfehg & 11001100 = ba00fe00 >> 2 = 00ba00fe
OR these to get dcbahgfe

Последняя линия:

b & 0x0F = dcbahgfe & 00001111 = 0000hgfe << 4 = hgfe0000
b * 0xF0 = dcbahgfe & 11110000 = dcba0000 >> 4 = 0000dcba
OR these to get hgfedcba

Какой байт, за которым ты был, обращен? Должно быть легко увидеть, как всего пара строк (аналогично приведенным выше) приводит вас к обращенному целому числу (32 бита). Поскольку размер числа увеличивается, этот трюк становится все более и более эффективным, сравнительно.

Я верю, что вы искали ответ "где-то" в приведенном выше. Надеюсь, у вас есть более четкое понимание возможностей манипуляции битами в C.

Answer 3

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

unsigned char rotl(unsigned char c)
{
    return((c << 1) | (c >> 7));
}

То, что делает ваш код, обращает биты; не вращая их. Например, это будет 10111001 в 10011101, а не 01110011.