CODEWITHSUNDEEP
c++algorithmxor
larry david
larry david

Reputation: 23

give an integer number ,count the xor value from zero to the number

count "0 xor 1 xor 2 xor......xor N",for instance,i give number three as N , the program should return 0,now i put my code to the online jundge ,the result is time limt exceed,i can hardly find where the error is ,can any one give me some advice,thanks in advance. 

 long long xorSum(long long  x) {   
   long long j =0;//we supposed x is big enough ,less than 10^18.
   for (long long i=1 ;i<=x;i++) {
     j  ^= i;
   }
    return j;
  }

Upvotes: 2

Views: 177

Answers (1)

Pham Trung
Pham Trung

Reputation: 11284

Simple logic, which work in O(1)

long long xorSum(long long k) {
    switch (k % 4) {
        case 0: return k;
        case 1: return 1;
        case 2: return k + 1;
        case 3: return 0;
    }
}

Proof, using induction: From, 1 to 4, we can easily see that the logic is correct. Assuming that the above logic is correct until a number x, which x % 4 = 3, so the current sum is 0.

  • Starting from x + 1 which (x + 1) % 4 = 0, so binary representation is always xxx00 (xxx represents any binary number), so xor with last sum, which is 0 we will get xxx00.
  • The next number will have the form xxx01 -> the xor will be xxx00 xor xxx01 = 00001.
  • From xxx01 to xxx10 -> xor will be 00001 xor xxx10 = xxx11
  • From xxx10 to xxx11 -> xor will be xxx11 xor xxx11 = 00000 -> Notice xxx11 % 4 = 3 which restarts the whole sequence and completes the proof.

Upvotes: 3

Related Questions