Найдите все M в диапазоне [2, N] такие, что выполняется побитовое ИЛИ до тех пор, пока M не будет равно значению до M-1

Учитывая целое число N , задача состоит в том, чтобы найти все возможные целые числа M в диапазоне [2, N] такие, что побитовое ИЛИ всех положительных значений до M совпадает с побитовым ИЛИ всех положительных значений до M-1 .

Примеры:

Input: N = 4
Output: 1
Explanation: Bitwise OR till 3 = 1 | 2 | 3 = 3.
Bitwise OR till 2 = 1 | 2 = 3.

Input: N = 7
Output: 4

Подход: Подход к решению этой проблемы основан на следующем наблюдении:

Consider p(x) to the bitwise OR till x. So p(x) = 1 | 2 | 3 | . . . | (x-1) | x
Given p(x) = 1 | 2 | 3 | . . . | x – 1 | x. Therefore, p(x + 1) will be different from p(x) if there is a new “1” bit in (x + 1) that isn’t present in the binary sequence of p(x).

Now, let us observe the pattern:

Decimal Number	Binary Number
1	1
2	10
3	11
4	100
5	101
6	110
7	111
8	1000
9	1001

We can see that a new “1” bit that hasn’t previously appeared in the range [1, x] appears at every power of 2.
As such,  p(x) = 1 | 2 | 3 | . . . | x – 1 | x 
                     = 2^a+1 – 1, where a = log₂x. 
This implies that, for a given a, there will be ( 2^{a + 1} – 2^a – 1 ) values of x where p(x) = p(x – 1).

Следуйте шагу ниже, чтобы решить эту проблему:

• Вычислите a = log ₂ N.
• Перебрать степени (скажем, используя переменную exp ) числа 2 от 1 до a и увеличить значение ans (первоначально 0) на ( 2 ^{exp + 1} – 2 ^exp – 1 ) .
• Наконец, подсчитайте пары между N и 2 ^a добавляя (n – 2 ^a ) к an .

Сложность времени: O(логарифм ₂ N)
Вспомогательное пространство: О(1)