Chef was recently studying the Bitwise OR operation, and stumbled upon the following problem:
Let F(i)=1 \;| \;2\; |\; 3\; |\; … |\; i, where | denotes bitwise OR.
You are given an integer N. Find the number of distinct i such that 2≤i≤N and F(i)=F(i−1).
Note that F(i) represents the bitwise OR of integers from 1 to i. Thus F(i) changes when a new “1” is introduced to the already existing binary sequence. We calculate the number of i’s at which F(i) changes and subtract the count from N.
Consider i = 1, 2, 4, 8 ....
A new bit is introduced in each such i.
We need to find the highest power of $2 that is less than N. Let it be x. Then, the answer would be N-x-1.
The above calculation can be done in roughly constant time. Hence, the solution has a time complexity of O(1).