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?
Look at the pattern in the bits for successive numbers. The LSB bit (denoted by say 0th bit) changes in every alternate number, 1st bit changes after every 2 times and so so on for other bits. Since, we are xoring, we only need to know the initial bit and (N-M+1) to find final value for a particular bit.