您将如何找到范围l至r的所有整数的XOR，其中-（10 ^ 18）<= l，r <= 10 ^ 18？

Question

我知道这是当1 <= l，r <= 10 ^ 18时如何实现的，但是如何处理负数？

long long int xorf(long long int n){
    long long int mod=n%4;
    switch(mod){
        case 0:return n;
            break;
        case 1:return 1;
            break;
        case 2:return n+1;
            break;
        case 3:return 0;
            break;
    }
    int main(){
    long long int l,r;
    long long int xo=0;
        cin>>l>>r;
        xo = (xorf(l-1)^xorf(r));
        cout<<xo<<endl;
    }

Answer 1

如果n> = 0，那么（如您所说）1 ^ 2 ^ ... ^ n可以通过以下方式计算：

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

类似地，如果n < 0，则n ^ (n+1) ^ ... ^ -1可以通过以下方式计算：

long long NegativeXor(long long n){
  switch ((-n) % 4){
        case 0: return 0 ;
        case 1: return n ;
        case 2: return 1 ;
        case 3: return n-1 ;
    }
}

（（假设2的补码表示。）

因此，如果l >= 0，答案为PositiveXor(r) ^ PositiveXor(l-1)；如果为l < 0和r >= 0，则答案为NegativeXor(l) ^ PositiveXor(r)。我将第三种情况（r < 0）留给您。