XOR product


  • 0
    J

    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?


  • 0
    C

    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


  • 0
    J

    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.


Log in to reply
 

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