Я хочу знать, существует ли какое-либо делимое правило в двоичной системе для деления на 3.
Например: в десятичной форме, если сумма цифр делится на 3, число делится на 3. Для exmaple: 15 -> 1+5 = 6 -> 6 делится на 3, так что 15 делится на 3.
Важно понять, что я не ищу КОД, который сделает это. bool flag = (i% 3 == 0); is'nt ответ, который я ищу. Я ищу то, что легко для человека сделать так же, как десятичный закон.
Посетите этот веб-сайт: Как определить, делится ли двоичное число на три?
В основном, посчитайте количество ненулевых битов нечетных позиций и ненулевых битов четной позиции справа. Если их разность делится на 3, то число делится на 3.
Например:
15 = 1111, который имеет 2 нечетных и 2 четных ненулевых бита. Разница равна 0. Таким образом, 15 делится на 3.
185 = 10111001, который имеет 2 нечетных ненулевых бита и 3 четных ненулевых бита. Разница равна 1. Таким образом, 185 не делится на 3.
Объяснение
Рассмотрим значения 2^n. Мы знаем, что 2^0 = 1 является конгруэнтным 1 mod 3. Таким образом, 2^1 = 2 является конгруэнтным 2*1 = 2 mod 3. Продолжая паттерн, заметим, что для 2^n, где n нечетно, 2^n конгруэнтно 1 mod 3, а для четного конгруэнтно 2 mod 3, то есть -1 mod 3, Таким образом, 10111001 является конгруэнтным 1*1 + 0*-1 + 1*1 + 1*-1 + 1*1 + 0*-1 + 0*1 + 1*-1 mod 3, который является конгруэнтным 1 mod 3. Таким образом, 185 не делится на 3.