Битшифтинг на Яве

Question

Я пытаюсь понять, как работает сдвиг битов.Может кто-нибудь объяснить, пожалуйста, значение этой строки:

while ((n&1)==0) n >>= 1;

, где n - целое число, и приведите пример n при выполнении сдвига.

Answer 1

Разбивка:

n & 1 выполнит двоичное сравнение между n и 1, что составляет 00000000000000000000000000000001 в двоичном виде.Таким образом, он вернет 00000000000000000000000000000001, когда n оканчивается на 1 (положительное нечетное или отрицательное четное число) и 00000000000000000000000000000000 в противном случае.

(n & 1) == 0, следовательно, будет истинным, если n четное (или отрицательное нечетное) и false в противном случае.

n >> = 1 эквивалентно n = n >> 1.Как таковой он сдвигает все биты вправо, что примерно эквивалентно делению на два (округление вниз).

Если, например, n начинается с 12, то в двоичном виде это будет 1100. После одного цикла это будет110 (6), после другого это будет 11 (3), и затем цикл остановится.

Если n равно 0, то после следующего цикла оно все равно будет 0, и цикл будет бесконечным.

Answer 2

Позволяет n быть 4, что в двоичном виде представляется как:

00000000 00000000 00000000 00000100

(n&1) по битам и n с 1.
1 имеет двоичное представление:

00000000 00000000 00000000 00000001

Результат побитового обращения: 0:

00000000 00000000 00000000 00000100 = n
00000000 00000000 00000000 00000001 = 1
------------------------------------
00000000 00000000 00000000 00000000 = 0

так что условие while верно.
Эффективно (n&1) был использован для извлечения младшего значащего бита n.

В цикле while вы сдвигаете вправо (>>) n на 1. Сдвиг вправо числа на k аналогичен делению числа на 2^k.

n, который теперь 00000000 00000000 00000000 00000100 при смещении вправо становится 00000000 00000000 00000000 00000010, что 2.

Затем мы снова извлекаем младший значащий бит из n, который равен 0, и снова сдвига вправо, чтобы получить 00000000 00000000 00000000 0000001, что составляет 1.

Затем мы снова извлекаем LSB из n, который теперь равен 1 и цикл прерывается.

Таким образом, вы продолжаете делить свой номер n на 2, пока он не станет нечетным , поскольку для нечетных чисел установлен LSB.

Также обратите внимание, что если n равно 0, для начала вы попадете в бесконечный цикл, потому что независимо от того, сколько раз вы поделите 0 на 2, вы не получите нечетное число.

Answer 3

Предположим, что n = 12. Биты для этого будут 1100 (1 * 8 + 1 * 4 + 0 * 2 + 0 * 1 = 12). Первый раз в цикле n & 1 == 0, потому что последняя цифра 1100 равна 0, а когда вы И с 1, вы получите 0. Таким образом, n >> = 1 приведет к изменению n с 1100 (12) на 110 (6). Как вы можете заметить, сдвиг вправо имеет тот же эффект, что и деление на 2. Последний бит по-прежнему равен нулю, поэтому n & 1 будет равно 0, поэтому он сместится вправо еще раз. n >> = 1 заставит его сдвинуть еще одну цифру вправо, изменив n со 110 (6) на 11 (3).

Теперь вы можете видеть, что последний бит равен 1, поэтому n & 1 будет равно 1, что приведет к остановке цикла while. Целью цикла, по-видимому, является смещение числа вправо, пока не будет найден первый включенный бит (пока результат не будет нечетным).

Answer 4

Предположим, равняется 42 (только потому, что):

int n = 42;

while ((n & 1) == 0) {
  n >>= 1;
}

Итерация 0:

• n = 42 (или 0000 0000 0000 0000 0000 0000 0010 1010)
• n & 1 == 0 равно true (потому что n & 1 = 0 или 0000 0000 0000 0000 0000 0000 0000 0000)

Итерация 1:

• n = 21 (или 0000 0000 0000 0000 0000 0000 0001 0101)
• n & 1 == 0 - это false (потому что n & 1 == 1 или 0000 0000 0000 0000 0000 0000 0000 0001)

Что он делает:

По сути, вы делите n на 2, пока n является четным числом:

• n & 1 - это простая проверка четности,
• n >> = 1 сдвигает биты вправо, что просто делит на 2.

Answer 5

например, если n было

n=    b11110000

, то

n&1=  b11110000 &
      b00000001 
      ---------
      b00000000

n>>=1 b11110000 >> 1
      ---------
      b01111000

n=    b01111000

, если цикл продолжается, он должен быть

n=    b00001111

Answer 6

n & 1 на самом деле является побитовой операцией AND.Здесь битовая комбинация n была бы ANDED против битовой комбинации 1. Результат кого будет сравниваться с нулемЕсли да, то n сдвигается вправо 1 раз.Вы можете принять одно правое смещение в качестве деления на 2 и т. Д.