1
import random

# длина блока кодирования
CHUNK_LENGTH = 8

# проверка длины блока
assert not CHUNK_LENGTH % 8, 'Длина блока должна быть кратна 8'

# вычисление контрольных бит
CHECK_BITS = [i for i in range(1, CHUNK_LENGTH + 1)if not i & (i - 1)]
print(CHECK_BITS)

Как работает часть кода if not i & (i - 1) ? Без неё выводит [1, 2, 3, 4, 5, 6, 7, 8]. С ней [1, 2, 4, 8], то есть степени двойки. В чём логика работы?

1 ответ 1

3

& - это операция побитовое и. Результат получается побитовым сравнением двух чисел, и в соответствующем бите будет 0, если хотя бы у одного из операндов этот бит равен 0.

Степень двойки в двоичном виде имеет представление:

10000...0000

Т.е. в старшем разряде единица, а все остальные разряды нули. При вычитании единицы (i-1), получается, что все биты числа меняются на противоположные. А значит побитовое и вернет 0 для i & (i - 1), если i - степень двойки. Этим мы установили, что для всех степеней двойки i & (i - 1) == 0.

Теперь, если же i не степень двойки, то отнимание единицы, никогда не изменит самый старший разряд числа (т.к. это возможно только в случае если во всех остальных разрядах нули, т.е. для степени двойки). А это значит, что в двоичном представлении i и (i - 1) в старшем разряде всегда 1, и значит, что и в i & (i - 1) в старшем разряде тоже 1, т.е. i & (i - 1) != 0.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.