Проверка делимости на 3

Недавно ко мне обратился мой бывший ученик - он теперь студент МГУ. Они на первом курсе изучают предмет связанный с низкоуровневым программированием (ассемблер, nasm). Вопрос у него возник по идеи алгоритма для реализации следующего задания: написать программу проверки делимости на 3 без использования операции деления.

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

Сложить все цифры в десятичной системе не получается, так как для того, чтобы получить цифру в десятичной системе нужно выполнить деление на 10. Выход - использовать двоичную систему счисления и признак делимости на 11.

Число представленное в двоичной системе счисления делится на 3 тогда и только тогда, когда сумма его цифр стоящих на четных местах отличается от суммы цифр, стоящих на нечетных местах, на число, делящееся на 3

Сложение чисел на четных и нечетных позициях в двоичном представлении числа можно реализовать, например, с использованием операции поразрядной конъюнкции и двоичного сдвига вправо. Проверку делимости разницы - осуществить в соответствии с алгоритмом, использующим цикл и условие - описанным выше.

Реализация на C++

bool divisibility3(int n)
{
  int s[2] = {}, k = 0;
  while (n > 0)
  {
    s[k] += (n & 1);
    k = 1 - k;
    n = n >> 1;
  }
  int d = s[0] - s[1];
  if (d < 0) d = s[1] - s[0];
  while(d > 2) d -= 3;
  return (d == 0);
}