XOR의 합산을 위한 직접 공식

XOR의 합산을 위한 직접 공식

1부터 N까지의 XOR 번호를 입력해야 하는데, 직접 공식이 있나요?

예를 들어 만약N = 6그리고나서1^2^3^4^5^6 = 7루프를 사용하지 않고 진행하고 싶어서 O(1) 공식이 필요합니다(있을 경우)

당신의 공식은N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) ):

int main()
{
    int S = 0;
    for (int N = 0; N < 50; ++N) {
        S = (S^N);
        int check = N & (N % 2 ? 0 : ~0) | ( ((N & 2)>>1) ^ (N & 1) );
        std::cout << "N = " << N << ": "  << S << ", " << check << std::endl;
        if (check != S) throw;
    }

    return 0;
}

출력:

N = 0: 0, 0             N = 1: 1, 1             N = 2: 3, 3
N = 3: 0, 0             N = 4: 4, 4             N = 5: 1, 1
N = 6: 7, 7             N = 7: 0, 0             N = 8: 8, 8
N = 9: 1, 1             N = 10: 11, 11          N = 11: 0, 0
N = 12: 12, 12          N = 13: 1, 1            N = 14: 15, 15
N = 15: 0, 0            N = 16: 16, 16          N = 17: 1, 1
N = 18: 19, 19          N = 19: 0, 0            N = 20: 20, 20
N = 21: 1, 1            N = 22: 23, 23          N = 23: 0, 0
N = 24: 24, 24          N = 25: 1, 1            N = 26: 27, 27
N = 27: 0, 0            N = 28: 28, 28          N = 29: 1, 1
N = 30: 31, 31          N = 31: 0, 0            N = 32: 32, 32
N = 33: 1, 1            N = 34: 35, 35          N = 35: 0, 0
N = 36: 36, 36          N = 37: 1, 1            N = 38: 39, 39
N = 39: 0, 0            N = 40: 40, 40          N = 41: 1, 1
N = 42: 43, 43          N = 43: 0, 0            N = 44: 44, 44
N = 45: 1, 1            N = 46: 47, 47          N = 47: 0, 0
N = 48: 48, 48          N = 49: 1, 1            N = 50: 51, 51

설명:

1. 로우 비트는 로우 비트와 다음 비트 사이의 XOR입니다.

2. 로우 비트를 제외한 각 비트에 대해 다음을 유지합니다.

   • N이 홀수이면 해당 비트는 0입니다.
   • N이 짝수이면 해당 비트는 N의 대응 비트와 같습니다.

따라서 홀수 N의 경우 결과는 항상 0 또는 1입니다.

편집하다
GSerg H는 루프가 없는 공식을 올렸지만 어떤 이유로 삭제했습니다(지금은 삭제되지 않음).이 공식은 (약간의 실수를 제외하고) 완벽하게 유효합니다.여기 C++ 같은 버전이 있습니다.

if n % 2 == 1 {
    result = (n % 4 == 1) ? 1 : 0;
} else {
    result = (n % 4 == 0) ? n : n + 1;
}

귀납법으로 증명할 수 있고, 모든 분할의 알림을 확인할 수 있습니다.4. 하지만, 어떻게 산출물을 생성하지 않고 규칙성을 보지 않고 그것을 생각해 낼 수 있는지는 모릅니다.

당신의 접근 방식을 좀 더 설명해 주시기 바랍니다.
각 비트는 x 또는 연산에서 독립적이므로 개별적으로 계산할 수 있습니다.
또한, k번째 bit의 수를 보면0..n, 패턴을 형성할 겁니다예를 들어 이진 형태로 0에서 7 사이의 숫자.

000
001
010
011
100
101
110
111

k번째 비트(k는 0부터 시작함)에 대해 볼 수 있듯이2^k0,2^k하나, 그 다음에2^k다시 0점 등
따라서 실제로 1부터 n까지의 모든 숫자를 거치지 않고 각 비트에 대해 몇 개의 숫자가 있는지 계산할 수 있습니다.

예를 들어, 에 대해k = 2, 반복되는 블록들이 있습니다.2^2 == 40과 1그리고나서,

int ones = (n / 8) * 4; // full blocks
if (n % 8 >= 4) { // consider incomplete blocks in the end
    ones += n % 8 - 3;
}

홀수로N, 결과는 둘 중 하나입니다.1아니면0(영문, 0인 경우)N=3, 1에 대하여N=5, 에 대한 0.N=7등)

짝수로N, 결과는 둘 중 하나입니다.N아니면N+1(순환식, N+1인 경우)N=2, N 에 해당N=4, 의 경우 N+1N=6, N 에 해당N=8등).

의사 코드:

if (N mod 2) = 0
  if (N mod 4) = 0 then r = N else r = N+1
else
  if (N mod 4) = 1 then r = 1 else r = 0

1부터 N까지의 모든 값을 XOR로 하는 함수를 XOR(N)이라고 하자, 그러면

XOR(1) = 000 1 = 0 1 (0은 bin 000의 dec)XOR(2) = 0011 = 11XOR(3) = 000 0 = 0 0XOR(4) = 0100 = 20XOR(5) = 000 1 = 0 1XOR(6) = 0111 = 31XOR(7) = 000 0 = 0 0XOR(8) = 1000 = 40XOR(9) = 000 1 = 01XOR(10)= 1011 = 51XOR(11)= 000 = 00XOR(12)= 1100 = 60

패턴을 보실 수 있으면 좋겠습니다.다른 숫자들도 비슷해야 합니다.

시도해 보기:

N이 홀수일 때마다 LSB가 토글되므로 다음과 같이 말할 수 있습니다.

 rez & 1 == (N & 1) ^ ((N >> 1) & 1)

나머지 비트에 대해서도 동일한 패턴을 관찰할 수 있습니다.가올다다h가B그리고.B+1) (LSB작) inN bit야, bit.B결과를 설정해야 합니다.

N 는 과 (N )rez = N ^ (N >> 1)

편집: 죄송합니다. 틀렸습니다.정답:

N: N:rez = (N ^ (N >> 1)) & 1

N: N:rez = (N & ~1) | ((N ^ (N >> 1)) & 1)

알렉세이 말리스토프의 훌륭한 답변!그의 공식의 변형:n & 1 ? (n & 2) >> 1 ^ 1 : n | (n & 2) >> 1는와게게와rn & 1 ? !(n & 2) : n | (n & 2) >> 1.

을 하지 은 를 사용하지 않습니다.F(N)=(N&((N&1)-1))|((N&1)^((N&3)>>1)

F(N)= (N&(b0-1)) | (b0^b1)

처음 몇 개의 숫자를 XOR하면 다음을 얻을 수 있습니다.

N     |  F(N)
------+------
0001  |  0001
0010  |  0011
0011  |  0000
0100  |  0100
0101  |  0001
0110  |  0111
0111  |  0000
1000  |  1000
1001  |  0001

패턴을 알아차리기를 바랍니다.

한다면N mod 4 = 1F(N)=1
한다면N mod 4 = 3F(N)=0
한다면N mod 4 = 0F(N)=N
한다면N mod 4 = 2F(N)=N하지만 첫번째 부분은1그렇게N|1

까다로운 부분은 조건 없이 이것을 하나의 진술로 얻는 것입니다. 제가 이것을 하던 논리를 설명해 드리겠습니다.

N의 첫 번째 의미 있는 비트 2개를 다음과 같이 부릅니다.

b0그리고.b1그리고 다음과 같이 구할 수 있습니다.

b0 = N&1
b1 = N&3>>1

ㅇb0 == 1다 해야 .0첫 번째 비트를 제외한 모든 비트가 아닌 경우에는 모든 비트가 그대로 유지됩니다.다음을 통해 이 동작을 수행할 수 있습니다.

N & (b0-1)로 작용합니다. :어 2에가다은의다ef2가ss에'2어은s-1든가된와다로와다o된으로 설정된 숫자와 같습니다.1그리고.1-1=0그래서 언제b0=1로로 됩니다.F(N)=0의 첫 이것이 이 기능의 첫 번째 부분입니다.

F(N)= (N&(b0-1))...

이제 이것은 에 효과가 있을 것입니다.N mod 4 == 3그리고.0 두 는 에 만 만 에 b1,b0그리고.F(N)0:

b0|b1|F(N)0
--+--+-----
 1| 1|    0
 0| 0|    0
 1| 0|    1
 0| 1|    1

좋아요, 이 진리표가 익숙해보이기를 바랍니다!그렇다.b0 XOR b1 (b1^b0) 이를 이제 마지막 비트를 얻는 방법을 알게 되었으므로 이를 우리 기능에 적용합니다.

F(N)=(N&(b0-1))|b0^b1

사용하지 않는 기능입니다 조건부를 양수 유용합니다 또한 때 계산하고자 할 로 에서 을 유용합니다 때 a numbers b b XOR positive 양수 to 또한 this로 do you 조건부를 the : if 사용하지 also is 않는 기능입니다 a useful 에서 x want from x b to or or 할 you 계산하고자 compute a 을 can 다음을 수행할 수 있습니다.F(a) XOR F(b).

원래 로직에 대한 최소한의 변경으로:

int xor = 0;
for (int i = 1; i <= N; i++) {
    xor ^= i;
}

우리는 다음을 가질 수 있습니다.

int xor = 0;
for (int i = N - (N % 4); i <= N; i++) {
    xor ^= i;
}

루프가 있지만 실행하는 데 일정한 시간이 걸릴 것입니다.for-loop을 반복하는 횟수는 1에서 4 사이에서 달라집니다.

이건 어때?

!(n&1)*n+(n%4&n%4<3)

이것은 어떤 문제에도 상관없이 잘 작동합니다.

unsigned int xorn(unsigned int n)
{

    if (n % 4 == 0)
      return n;
   else if(n % 4 == 1)
       return 1;
   else if(n % 4 == 2)
       return n+1;
  else
       return 0;
}

이것 좀 봐.이렇게 하면 문제가 해결됩니다.

https://stackoverflow.com/a/10670524/4973570

1부터 N까지의 XOR 합을 계산하는 방법:

int ans,mod=N%4;
if(mod==0) ans=N;
else if(mod==1) ans=1;
else if(mod==2) ans=N+1;
else if(mod==3) ans=0;

여전히 필요한 사람이 있다면 간단한 파이썬 솔루션:

def XorSum(L):
    res = 0        
    if (L-1)%4 == 0:
        res = L-1
    elif (L-1)%4 == 1:
        res = 1
    elif (L-1)%4 == 2:
        res = (L-1)^1
    else: #3
        res= 0
    return res

언급URL : https://stackoverflow.com/questions/3932346/direct-formula-for-summing-xor