时间戳

首页 > 解决方案 > 你如何找到 l 到 r 范围内所有整数的异或，其中 -(10^18) <= l,r <= 10^18？

c++ - 你如何找到 l 到 r 范围内所有整数的异或，其中 -(10^18) <= l,r <= 10^18？

问题描述

我知道这就是当 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;
    }

标签： c++bitwise-operators

解决方案

如果 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) 留给你。

推荐阅读