Количество различных значений для побитового исключающего ИЛИ X и Y для X, Y не более N

Для заданного целого числа N задача состоит в том, чтобы найти количество различных значений, возможных для побитового XOR X и Y , где 1 ≤ X, Y ≤ N.

Примеры:

Input: N = 1
Output: 1
Explanation: The possible xor values are 1⊕1=0 which has 1 unique value.

Input: N = 2
Output: 2
Explanation: The possible xor values are 1⊕1 = 0, 1⊕2 = 1, 2⊕2 = 0 which has 2 unique values.

Подход: для значений N , равных 1 и 2 , ответ прост. Для остальных случаев рассмотрим N≥3. Рассмотрим p как наивысшую степень, для которой 2^p ≤ N. Предположим, что 2^p < N , тогда можно получить все числа от 0 до 2^{p+1} -1 . Этого можно достичь следующим образом:

For example,  
let N = 12, then x = 3. 
Number 12 (1100 in binary ) can be formed by (2^3(1000), 4(0100)).
By the property of xor, num⊕1 is either num +1 or num -1. 
So if  1 < num ≤ 2^p < N, 1 ≤ num⊕1 ≤ N. 
Hence these pairs of numbers will always be valid.

А что произойдет, если 2^p = N? Все вышеперечисленные случаи верны, кроме случая num = 2^p. Это не может быть получено из любой пары xor (X, Y), где (1 ≤ X, Y ≤ 2^p) . Поскольку единственным числом с установленным битом p является 2^p , мы должны сохранить i = 2^p . Тогда для X ⊕ Y=2*p сохраните Y = 0 , что невозможно сделать, поскольку Y ≥ 1 . Следовательно, в этом случае, кроме 2^p , может быть получена пара xor для любого числа от 0 до 2^{p + 1} -1 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте переменную ans как 1.
• Если N равно 2 , выведите 2 и вернитесь.
• Пройдите в цикле while до тех пор, пока an не станет меньше N , и умножьте an на 2.
• Если ans равно N , то умножьте ans на 2 и уменьшите его значение на 1.
• После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O (log (N))
Вспомогательное пространство: O(1)