XOR 선형 기저 계산기

수들의 비트열을 GF(2) 위의 벡터로 보았을 때의 기저입니다. XOR이 덧셈인 두 원소짜리 체에서는 「부분집합 XOR」이 곧 선형결합이므로, 만들 수 있는 값 전체가 벡터공간이 됩니다. 기저 크기가 k면 만들 수 있는 서로 다른 값이 정확히 2^k개입니다.

기저 원소들의 최고 비트가 서로 다르기 때문입니다. 높은 비트부터 「켤 수 있으면 켠다」로 진행하면 되는데, 어떤 비트를 켜는 선택이 그보다 낮은 비트에만 영향을 주고 이진법에서는 한 자릿수가 그 아래 전부를 합친 것보다 크기 때문입니다. 뒤에서 후회할 일이 생기지 않습니다.

언제나 0입니다. 아무것도 고르지 않으면 XOR이 0이기 때문입니다. 뜻이 있는 물음은 「0이 아닌 최솟값」이고, 그것은 기약 사다리꼴 기저에서 최고 비트가 가장 낮은 원소입니다. 어떤 조합이든 최고 비트는 고른 것들 중 가장 높은 최고 비트가 되므로 하나만 고르는 쪽이 이깁니다.

기저로 차례로 지워 나가 0이 되면 만들 수 있습니다. 목표의 최고 비트를 가진 기저가 있으면 XOR로 지우고, 다음 비트로 넘어가는 것을 되풀이합니다. 끝까지 무언가 남으면 그 비트는 이 수들로 결코 만들 수 없는 부분입니다.

기저를 기약 사다리꼴로 정리한 뒤 k의 이진 표현을 「어느 기저를 쓸지」로 읽으면 됩니다. 각 기저 원소의 최고 비트가 다른 원소에는 나타나지 않게 정리해야 순서가 맞습니다. 이 정리를 건너뛰면 값은 다 나오지만 크기 순서가 어긋납니다.

2^(n − 기저크기)가지씩입니다. 어떤 수가 앞의 것들로 만들어져 기저에 들어가지 못했다면, 그것으로 0을 만드는 부분집합이 생기고 거기에 대칭차를 취해도 XOR 값이 그대로이기 때문입니다. n개에서 기저가 k개면 「XOR이 0이 되는 부분집합」이 정확히 2^(n−k)개 있습니다.

경진 프로그래밍에서 「부분집합 XOR의 최댓값」, 「어떤 값을 만들 수 있는가」, 「XOR이 0이 되는 부분집합 세기」 같은 문제에 표준으로 쓰입니다. 선형대수의 도구가 정수 비트에 그대로 옮겨진다는 것을 보여 주는 좋은 예이기도 하며, 오류정정부호(해밍 코드 등)의 생성행렬도 같은 언어로 설명됩니다.

전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.