Проверка правил делимости с использованием побитовых операций

Question

Как проверить, делится ли число n на x с помощью побитовых операций?

Я нахожу много связанных ссылок на это, но я не совсем понимаю их, поскольку они не были в Python. Например, что, если я хочу проверить, является ли 81 делящимся на 3, 9 или 4?

Я хочу использовать побитовые операции, и я хочу понять, как реализовать это с помощью Python.

Answer 1

Побитовая операция как их имя позволяет угадывать работу с двоичным представлением чисел. Это означает, что они будут очень эффективны для проверки делимости силой или 2, но вряд ли пригодны для любого другого случая.

Примеры:

• п делится на 2: n & 1 == 0
• п делится на 4: n & 3 == 0
• п делится на 8: n & 7 == 0

Есть другие правила делимость, которые могут быть Используется: вы можете адаптировать casting out 9 or 11 для проверки делимости на 15 или 17 (базовая 16 использует до полубайта на каждый байт), но как одно целое число разделение часто быстрее, чем выполнение многих простых операций (аккумулятор непосредственно обрабатывает числа 32 или 64 бит), они редко используются ...

Если ваше требование - проверить делимость на 3 и 9, вы можете адаптировать выкидывать 9 для 3 = 4 - 1 и для 9 = 8 + 1. 81 = 0b1010001

• 3: сумма 2 битовых цифр должна быть кратна 3 - начиная с небольшими весами: 01 + 00 + 01 + 01 = 0b11 (= 3): делится
• 9: суммы нечетного 3 разрядных цифры минус сумма четных должна быть кратна 9 = 0b1001 - нечетная: 001 + 001 = 010, даже: 010 - разница составляет 0: делится

Вы можете закодировать это легко сдвиги (>>) и двоичный код &