Обращение двоичного числа с использованием битовых хаков - PullRequest
Новая
       7

Обращение двоичного числа с использованием битовых хаков

0 голосов
/ 24 мая 2018

Может кто-нибудь объяснить, как двоичное число переворачивается. 

unsigned rev = 0;
unsigned k = n;

while (k)
{
// add rightmost bit to rev 
    rev = (rev << 1) | (k & 1);
    k = k >> 1;     // drop last bit
            cout<<"k val is "<<bitset<8>(k)<<endl;
    cout<<"rev val is "<<{bitset<8>(rev)<<endl;
}

Вывод, если n = 9

k val равен 00000100
rev valis 00000001
k val это 00000010
rev, значение 00000010
k val, 00000001
rev, значение 00000100
k val, 00000000
rev, значение 00001001
9, палиндром

Я имел в виду вопрос 2 отсюда: http://www.techiedelight.com/bit-hacks-part-6-random-problems/

Насколько я знаю, только первое выражение выполняется, если оно истинно для "|"УсловиеТаким образом, здесь rev << 1 будет false только для первого выполнения цикла, но не для остальных.Следовательно, как rev получает 1 в конце для последнего условия, потому что (k & 1) не будет выполнено.Только левый сдвиг будет выполнен верно?</p>

Ответы [ 3 ]

0 голосов
/ 24 мая 2018

Переменная rev инициализируется с 0, она будет содержать результат.Цикл while повторяется, в то время как у k, который является входом, остались все установленные биты.Первая инструкция тела цикла маскирует последний бит k и копирует его в rev, который в процессе сдвигается на один бит влево (оператором shift).В итерации цикла и вход, и выход смещены - вход смещен вправо, выход - влево.

0 голосов
/ 24 мая 2018

Одной визуализацией, которая может быть полезна, является стек: представьте, что ваше число n представлено стеком двоичных цифр, причем наименее значимая цифра находится вверху стека.

Общий алгоритм дляинверсия битов заключается в том, чтобы итеративно извлекать цифры одну за другой из стека n и складывать их в другой стек (представляющий rev в вашем случае).

  • k = k >> 1;извлекает одну двоичную цифру из стека n (переименовывается в ваш код как k)

  • rev = (rev << 1) | (k & 1); укладывает двоичную цифру на вершину стека k.

В коде операции pop / stack меняются местами, чтобы избежать временных.

Наконец, эту операцию pop / stack следует повторять до тех пор, пока в ней есть цифрыстек n.Это связано с тем, что условие while имеет значение k, оно проверяет, равно ли k 0 (не осталось цифр).

PS: на веб-сайте Bit Twiddling Hacks есть несколько низкоуровневых алгоритмов для выполнения бит-реверсирования .Алгоритмы нацелены на производительность и поэтому не могут быть легко понятны.

0 голосов
/ 24 мая 2018

Насколько я знаю, только первое выражение выполняется, если оно истинно для "|"оператор условия.

The |оператор является побитовым ИЛИ: его значение является операцией ИЛИ для битовых комбинаций двух его операндов.Он всегда оценивал оба операнда, потому что ему нужны их полные значения.Пример: 3 |5 - это 7.

||является логическим ИЛИ: это правда, если любой из операндов (как целое значение) является истиной.Он не оценивает вторые операнды, если первый был истинным.

Код использует |побитовое ИЛИ для построения ответа по одному биту за раз.

...