We can define the bitwise XOR product. If M and N are two non-negative integers, such that M <= N, then their bitwise XOR product is the bitwise XOR of all integers from M to N:

M bitxor (M + 1) bitxor ... bitxor (N - 1) bitxor N

Note that the bitwise XOR is associative; that is, the order in which this operation is performed does not matter.

For example, the bitwise XOR product of M = 5 and N = 8 is 12 because:

5 bitxor 6 bitxor 7 bitxor 8 =

3 bit xor 15 =

Write a function:

int solution(int M, int N);

that, given two non-negative integers M and N, returns their bitwise XOR product.

expected worst-case time complexity is O(log(N));

expected worst-case space complexity is O(1)

I couldn't come up with an O(log(N)) solution. Can anyone help me?