# XOR product

• 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.

eg.
100101
100110
100111
101000
101001
101010
101011
101111
110000

• I am not sure how I can get the xorProduct from the initial bit and (N-M+1).

e.g.

...00 ...01
...01 ...10
...10 ...11

The initial bit of the first bit of the two cases are both 0 and (N - M + 1) are both 3, but the first bit of the xor product is different.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.