Проверить делимость на число 3, используя только сложение и битовые оп

[temster]

Предисловие. Не так давно столкнулся с задачей, которая сформулирована в заголовке поста. Если бы в задании не содержалось части после запятой все понятно: в языке С++ есть операция % - взятие остатка от деления, если остаток 0, то делится, иначе нет….., но! Как же это реализовать используя только сложение и побитовые операции… После часа раздумий вместе с великим мозгом по имени Интернет, у меня на листке созрел алгоритм. Вот его реализация:

Ссылка скрыта от гостей

 

[grigsoft]

Традиционный метод - если сумма цифр делится на 3. У тебя - аналогичное, но число раскладывается по степеням 4. Доказательство тоже аналогичное - остаток от деления любой степени 4 на 3 - всегда 1, так что делимость определяется суммой коэффициентов разложения. Единственно, что у тебя считается не 219 -> 2+1+9, а 219 -> 21+9, но с точки зрения математики сути это не меняет.