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

  • Автор темы temster
  • Дата начала
Статус
Закрыто для дальнейших ответов.
T

temster

#1
Предисловие. Не так давно столкнулся с задачей, которая сформулирована в заголовке поста. Если бы в задании не содержалось части после запятой все понятно: в языке С++ есть операция % - взятие остатка от деления, если остаток 0, то делится, иначе нет….., но! Как же это реализовать используя только сложение и побитовые операции… После часа раздумий вместе с великим мозгом по имени Интернет, у меня на листке созрел алгоритм. Вот его реализация: http://temster.ru/?p=7#more-7
 

grigsoft

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