SanitLee SanitLee -4 years ago 221
Objective-C Question

Find XOR of all numbers between specific two numbers

Here I have a question about 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 = 12

Write a function:
int solution(int M, int N);
that, given two non-negative integers M and N, returns their bitwise XOR product.

So far, I only can do XOR of two numbers but not all numbers between them. If anyone could show me how, that'd be appreciated.

int solution(int M, int N) {

int result = 0; // Initial result

// Assuming 8-bit Integer due to its range [0..1,000,000,000]
for (int i = 7; i >= 0; i--)
{
// Find current bits in x and y
bool b1 = M & (1 << i);
bool b2 = N & (1 << i);

// If both are 1 then 0 else xor is same as OR
bool xoredBit = (b1 & b2) ? 0 : (b1 | b2);

// Update result
result <<= 1;
result |= xoredBit;
}
return result;
}

Answer Source

There is no need to mess about with bitwise operators to try and do xor one bit at a time.

ObjC, like its brethren, contains a perfectly adequate ^ xor operator so your entire current function could be replaced with:

int xorTwoNums (int M, int N) {
    return M ^ N;  // xor operator
}

Calculating the xor of a range of numbers can be done with a loop along the lines of:

int xorBetweenInclusive (int lo, int hi) {
    int i, res = 0;
    for (i = lo; i <= hi; i++ ) {
        res = res ^ i;
    }
    return res;
}
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download