Битовая задачка?

Question

[Umid]

Приветствую.
Есть задачка с олимпиады.
Возможно, перевод немного кривой, почему и не получается её решить у меня.
Пришёл за помощью к вам.

Comments

[sim3x]

Напиши текст задачи текстом

Answer 1

[jcmvbkbc]

a (+) x > x только тогда, когда самый старший ненулевой бит a соответствует нулевому биту x.
Нужно пройти по битам x и для каждой позиции i, в которой стоит 0 посчитать, сколько есть разных чисел со старшей 1 в этой позиции. Их, очевидно, 2^i.

Для контрольного примера:
2 в двоичном виде -- 10, 0 только в нулевом бите, количество подходящих a: 2^0 == 1
10 в двоичном виде -- 1010, 0 в нулевом бите даёт 2^0 == 1, 0 во втором бите даёт 2^2 == 4, всего подходящих a: 1 + 4 == 5.
Ответ -- 1 + 5 == 6.

Comments

[Umid]

А что такое нулевой бит?
Число в двоичной системе, что идёт самым первым?

[jcmvbkbc]

Umid: посмотри в разбор контрольного примера, должно быть понятно

Answer 2

[Boris Köln]

(+) - это XOR. Чтобы после XOR число увеличилось, надо:
- в любом битовом нуле у "x" (кроме самых верхних, иначе "a" будет больше "x") сделать у "a" битовую единицу (чтобы XOR увеличился)
- при этом во всех последующих (правых) битах могут быть любые значения (2^КоличествоОставшихсяБитов)

Мое решение: sandbox.onlinephpfunctions.com/code/e6c9bb63f63c26... (запускать на PHP7)