Алгоритм: ограниченный XOR чисел в диапазоне

Question

Скажем, нам дано число n. Нам нужно найти число значений S^(S + n), лежащих в диапазоне [L, R]. (где S - любое неотрицательное целое число, а^- побитовый оператор xor).

я могу легко это сделать, если п двойки (у них есть очень полезный образец)

Я не знаю, как решить эту проблему для любого общего п. Любые предложения?

РЕДАКТИРОВАТЬ:

п также неотрицательное целое число. n, L, R все меньше 10^18.

Это был вопрос программирования в каком-то практическом тесте, который я когда-то возвращал, я просто вспомнил об этом, увидев аналогичный вопрос в StackOverflow сегодня.

EDIT 2: Объясняя с примером, сказать, п ​​= 1. Тогда мы знаем, что S^(S + 1) будет всегда иметь двоичное представление всех из них. например: 1,3,7, ...

Так что решить это легко, нам просто нужно подсчитать количество таких чисел в пределах диапазона [L, R], это довольно просто.

Для n = любая сила 2 подобных методов работы. Но я понятия не имею, что делать, если n не является степенью 2.

Answer 1

Позвольте C(n) быть (бесконечным) набором чисел, которые могут быть записаны как S^(S + n) для некоторых S.

Мы имеем следующие рекуррентные соотношения на множествах C(n):

• Если n = 2k четно, то C(n) = {2x : x in C(k)};
• Если n = 2k + 1 нечетное, то C(n) = {2x + 1 : x in C(k)} union {2x + 1 : x in C(k + 1)}.

Алгоритм может быть выведен из этих отношений. Точнее, пара (C(n), C(n + 1)) может быть выведена из (C(n/2), C(n/2 + 1)). Обратите внимание, что приведенное выше union действительно является несвязным объединением, поскольку каждый элемент в C(n) имеет такую ​​же четность, что и n, поэтому C(k) и C(k + 1) не пересекаются.

---

Доказательство рекуррентных соотношений:

Просто посмотрите на последние двоичных цифр n и S.