Алгоритмы вычисления, если число кратно 3

При выполнении умственного исчисления можно сделать:

• Дано целое число k, суммировать все цифры (в базе 10), и если результат кратен 3, то k кратен 3.

Знаете ли вы о каком-либо алгоритме, работающем аналогично, но работающем с двоичными числами (битами)?

• Сначала я думал об использовании готовых функций моего языка для преобразования целых чисел в ascii, чтобы выполнить преобразование из базы 2 в базу 10, а затем применил трюк умственного исчисления. Но, конечно же, я мог бы также сам закодировать базовое преобразование от 2 до 10. Я еще этого не сделал, но попробую.

• Тогда я подумал о евклидовом делении в базе 2 ...

Однако мне интересно, есть ли другие средства, алгоритмы.

Рассмотрим следующие два замечания (оставленные в качестве упражнения для читателя):

1. Четные степени двух равны 1 по модулю 3.
2. Нечетные степени двойки -1 по модулю 3.

Мы заключаем, что число (в двоичном коде) делится на три тогда и только тогда, когда сумма битов в четных позициях равна сумме битов в нечетных позициях по модулю 3.

А как насчет конечного автомата для работы?

Конечно , магия просто вычисление по модулю 3. Добавление символов строки за й означает «двоичное значение» строка идет из об в л ( х ) для й до 2 ⋅ об в л ( х ) + для х . Следовательно, из состояния p и символа a мы переходим в состояние 2 p + a mod 3 для p ∈ { 0 , 1 , 2$a$$x$$val(x)$$x$$2\cdot val(x)+a$$xa$$p$$a$$2p+a \bmod 3$ и a ∈ { 0 , 1 } . Заметьте, что x ∈ { 0 , 1 } ∗ - строка, тогда как v a l ( x ) ∈ N - ее значение в виде двоичной строки.$p\in \{0,1,2\}$$a\in \{0,1\}$$x\in \{0,1\}^*$$val(x)\in \Bbb{N}$

В двоичном формате числа 1, 100, 10000 (= 100 × 100), 1000000 (= 100 × 100 × 100) и т. Д. Все дают одинаковый остаток после деления на 11 (три). Поэтому, если мы разделим двоичное число на части четной длины , сумма частей даст тот же остаток, что и исходное число.

(При разделении числа мы добавляем столько нулей, сколько необходимо для начала . Например, мы бы разбили 10111 на группы 01,01,11 или 0001,0111.)

Математически, просто разбейте число на группы из двух цифр, затем добавьте группы; и повторяйте это, пока ваш результат не станет 00 или 11 = исходное число было кратно трем; или 01 или 10 = исходное число не было кратно трем.

Для компьютерной программы использование групп из восьми, шести или тридцати двух бит может быть быстрее для вашего процессора. Например, если восьмибитное сложение происходит быстрее, просто сделайте сумму всех байтов и снова, пока результат не уместится в один байт. Затем используйте одну инструкцию для определения остатка после деления на три.

(Примечание: здесь мы предполагаем целые числа без знака . Для числа со знаком это требует немного большего внимания. Например, 129 кратно 3, но -127 нет, хотя биты 10000001 означают для первого как беззнаковый байт и последний как подписанный байт.)

Хотя в случае сомнений это не относится к двоичным файлам, повторное вычитание всегда является верным способом вычисления деления с остатком (и, таким образом, если число кратно 3).