Праздничные вычисления по сахарному модулю

Для начала узнаем, какие биты являются единичными в $$$x \oplus y$$$. Тогда мы сможем представить результат в виде суммы $$$2^i$$$, по всем битам i, равным $$$1$$$ в $$$x \oplus y$$$.

Не умоляя общности предположим, что $$$x > y$$$. Затем получим $$$2^0 = 1$$$, деля число $$$y$$$ целочисленно на $$$2$$$, пока не получим $$$1$$$. На это у нас уйдет не более O($$$\log(y)$$$) операций. Теперь достаточно с помощью операции умножить на $$$2$$$, получить из $$$2^0$$$ нужные степени двойки и сложить их. Нужных степеней двоек будет порядка O($$$\log(x)$$$).

Для удобства обращения к памяти можно было сначала получить все степени двойки, а уже потом выполнять сложение.

Всего нужно будет хранить порядка $$$O(\log{x})$$$ переменных.