비트 연산 AND(\(\wedge\)), OR(\(\vee\)), XOR(\(\bigoplus\))과 관련하여 여러 성질을 알아보고, 누적 연산을 효율적으로 하는 방법을 알아봅시다.
비트 연산에 대한 자세한 내용은 다루지 않으므로, 비트 연산의 내용은 아래 위키백과를 참고해주세요.
https://ko.wikipedia.org/wiki/비트_연산
비트 연산 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 비트 연산(bitwise operation)은 한 개 혹은 두 개의 이진수에 대해 비트 단위로 적용되는 연산이다. NOT 연산은 각 자릿수의 값을 반대로 바꾸는 연산이다. NOT 0111 = 10
ko.wikipedia.org
1. 비트 연산의 당연하지만 재미있는 성질
비트 연산은 이진수 체계에서 각 비트 단위에 적용되는 연산입니다.
따라서 당연하게도 아래의 두 가지 규칙이 적용됩니다.
가. 비트 연산 결과의 자리수는 피연산자의 최대 자리수를 넘지 않는다.
\( 10110111_{(2)} \: \wedge \: 1101_{(2)} \: = \: 101_{(2)} \)
\( 10110111_{(2)}\: \vee \:1101_{(2)} \: = \: 10111111_{(2)} \)
\( 10110111_{(2)}\: \bigoplus \:1101_{(2)}\: = \:10111010_{(2)} \)
8자리 이진수와 4자리 이진수를 비트연산한 결과는 더 큰 자릿수인 8자리를 넘지 않습니다.
나. 비트 연산 결과는 피연산자의 각 자리를 각각 비트연산한 결과와 같다.
\( {\color{red}1}0110{\color{orange}1}11_{(2)}\: \wedge \:{\color{red}0}0001{\color{orange}1}01_{(2)}\: = \:{\color{red}0}0000{\color{orange}1}01_{(2)} \)
\( 101{\color{red}1}0111_{(2)} \: \vee \: 000{\color{red}0}1101_{(2)} \: = \: 101{\color{red}1}1111_{(2)} \)
\( 10{\color{red}1}1011{\color{orange}1}_{(2)}\: \bigoplus \:00{\color{red}0}0110{\color{orange}1}_{(2)}\: = \:10{\color{red}1}1101{\color{orange}0}_{(2)} \)
비트 연산 결과의 각 자릿수는 이진수의 각 자리 숫자를 각각 비트 연산한 결과와 같습니다.
2. 본격적인 문제
n개의 수, \(\{A_{1}, \: A_{2}, \: ..., \: A_{n}\}\)가 있습니다.
AND, OR, XOR 연산을 다음과 같이 수행한 결과를 구하는 방법을 알아봅시다.
\(A_{1} \: + \: ( A_{1} \: \wedge \: A_{2} ) \: + \: ( A_{1} \: \wedge \: A_{2} \: \wedge \: A_{3} ) \: + \: ... \: + \: (A_{1} \: \wedge \: A_{2} \: \wedge \: ... \: \wedge \: A_{n})\)
\(+ \: A_{2} \: + \: (A_{2} \: \wedge \: A_{3}) \: + ( A_{2} \: \wedge \: A_{3} \: \wedge \: A_{4} ) \: + \: ... \: +
\: (A_{2} \: \wedge \: A_{3} \: \wedge \: ... \: \wedge \: A_{n}) \)
\(...\)
\( + \: A_{n-1} \: + \: ( A_{n-1} \: \wedge \: A_{n} ) \)
\( + \: A_{n} \)
\(A_{1} \: + \: ( A_{1} \: \vee \: A_{2} ) \: + \: ( A_{1} \: \vee \: A_{2} \: \vee \: A_{3} ) \: + \: ... \: + \: (A_{1} \: \vee \: A_{2} \: \vee \: ... \: \vee \: A_{n})\)
\(+ \: A_{2} \: + \: (A_{2} \: \vee \: A_{3}) \: +
( A_{2} \: \vee \: A_{3} \: \vee \: A_{4} ) \: + \: ... \: +
\: (A_{2} \: \vee \: A_{3} \: \vee \: ... \: \vee \: A_{n}) \)
\(...\)
\( + \: A_{n-1} \: + \: ( A_{n-1} \: \vee \: A_{n} ) \)
\( + \: A_{n} \)
\(A_{1} \: + \: ( A_{1} \: \bigoplus \: A_{2} ) \: + \: ( A_{1} \: \bigoplus \: A_{2} \: \bigoplus \: A_{3} ) \: + \: ... \: + \: (A_{1} \: \bigoplus \: A_{2} \: \bigoplus \: ... \: \bigoplus \: A_{n})\)
\(+ \: A_{2} \: + \: (A_{2} \: \bigoplus \: A_{3}) \: +
( A_{2} \: \bigoplus \: A_{3} \: \bigoplus \: A_{4} ) \: + \: ... \: +
\: (A_{2} \: \bigoplus \: A_{3} \: \bigoplus \: ... \: \bigoplus \: A_{n}) \)
\(...\)
\( + \: A_{n-1} \: + \: ( A_{n-1} \: \bigoplus \: A_{n} ) \)
\( + \: A_{n} \)
이전 비트 연산 결과를 활용하여 누적 계산하면 될 것 같습니다.
마치 누적합을 구하듯이 말입니다.
예를 들어 수열이 9, 12, 14, 15이라고 하면, 이진수로 1001, 1100, 1110, 1111이 됩니다.
위의 방법으로 AND 연산을 해보면,
\( 1001_{(2)} \: = \: {\color{red}1001_{(2)}} \)
\( {\color{red}1001_{(2)}} \: \wedge \: 1100_{(2)} \: = \: {\color{red}1000_{(2)}} \)
\( 1001_{(2)} \: \wedge \: 1100_{(2)} \: \wedge \: 1110_{(2)} \: = \: {\color{red}1000_{(2)}} \: \wedge \: 1110_{(2)} \: = \: {\color{red}1000_{(2)}} \)
\( 1001_{(2)} \: \wedge \: 1100_{(2)} \: \wedge \: 1110_{(2)} \: \wedge \: 1111_{(2)} \: = \: {\color{red}1000_{(2)}} \: \wedge \: 1111_{(2)} \: = \: {\color{red}1000_{(2)}} \)
\( 1100_{(2)} \: = \: {\color{red}1100_{(2)}} \)
\( {\color{red}1100_{(2)}} \: \wedge \: 1110_{(2)} \: = \: {\color{red}1100_{(2)}} \)
\( 1100_{(2)} \: \wedge \: 1110_{(2)} \: \wedge \: 1111_{(2)} \: = \: {\color{red}1100_{(2)}} \: \wedge \: 1111_{(2)} \: = \: {\color{red}1100_{(2)}} \)
\( 1110_{(2)} \: = \: {\color{red}1110_{(2)}} \)
\( {\color{red}1110_{(2)}} \: \wedge \: 1111_{(2)} \: = \: {\color{red}1110_{(2)}} \)
\( 1111_{(2)} \: = \: {\color{red}1111_{(2)}} \)
\( 1001_{(2)} \: + \: 1000_{(2)} \: + \: 1000_{(2)} \: + \: 1000_{(2)} \)
\( + \: 1100_{(2)} \: + \: 1100_{(2)} \: + \: 1100_{(2)} \)
\( + \: 1110_{(2)} \: + \: 1110_{(2)} \)
\( + \: 1111_{(2)} \)
\( = \: (9 \: + \: 8 \: + \: 8 \: + \: 8) \: + \: (12 \: + \: 12 \: + \: 12) \: + \: (14 \: + \: 14) \: + \: (15) \)
\( = \: 112 \)
OR 연산과 XOR 연산도 같은 방식으로 계산하면 각각 137, 86이 나옵니다.
하지만 그렇게 될 경우 연산의 시간 복잡도가 \(O(n^{2})\)으로 비효율적입니다.
더 효과적인 방법은 없을까요?
앞서 살펴본 비트 연산의 성질을 생각해보면 수열의 모든 수를 각 자릿수로 나눠 각각 같은 연산을 해준 뒤, 다시 합쳐도 결과는 같습니다.
예시의 수열을 각 자릿수로 나누어 표로 나타내면 다음과 같습니다.
| \(2^{3}\)의 자리 | \(2^{2}\)의 자리 | \(2^{1}\)의 자리 | \(2^{0}\)의 자리 | |
| 9(\(1001_{(2)}\)) | 1 | 0 | 0 | 1 |
| 12(\(1100_{(2)}\)) | 1 | 1 | 0 | 0 |
| 14(\(1110_{(2)}\)) | 1 | 1 | 1 | 0 |
| 15(\(1111_{(2)}\)) | 1 | 1 | 1 | 1 |
각각의 열(각 자릿수)에 원래의 연산을 수행하여 다시 더하면 됩니다.
| \(2^{3}\)의 자리 | \(2^{2}\)의 자리 | \(2^{1}\)의 자리 | \(2^{0}\)의 자리 | |
| 9(\(1001_{(2)}\)) | 1 | 0 | 0 | 1 |
| 12(\(1100_{(2)}\)) | 1 | 1 | 0 | 0 |
| 14(\(1110_{(2)}\)) | 1 | 1 | 1 | 0 |
| 15(\(1111_{(2)}\)) | 1 | 1 | 1 | 1 |
| AND 연산 결과 | 10 | 6 | 3 | 2 |
| 최종 결과 | \( (10 \: \times \: 2^{3}) \: + \: ( 6 \: \times \: 2^{2} ) \: + \: ( 3 \: \times \: 2^{1} ) \: + \: ( 2 \: \times \: 2^{0} ) \: = \: 112 \) | |||
각 자릿수를 따로 연산하여, 자릿수에 해당하는 값을 곱해서 더해줘도 같은 값이 나옵니다.
하지만 이 방법은 자릿수만큼 연산이 배가 되기 때문에 아직도 비효율적입니다.
대신 이 방법의 장점은 피연산자를 모두 0 또는 1로 만든다는 점입니다.
이 점을 활용하면 효율적으로 만들 수 있습니다.
가. AND
앞의 AND 연산을 누적할 때 특별한 점이 있습니다.
바로 0이 하나라도 있으면 그 다음 누적 연산 때는 값이 무조건 0이 된다는 것입니다.
이 점을 이용해 각 자리의 누적 비트 연산 결과를 \(O(n^{2})\)에서 선형 시간으로 개선할 수 있습니다.
피연산자는 1 또는 0 뿐이고, 1일 경우 이후 연산에 누적되어 활용되는 점을 생각하면,
1이 얼마나 연속적으로 나오는지 길이를 구하고, 1부터 그 길이까지의 합(1~n 까지의 합)을 구하면 누적 연산의 결과를 바로 알 수 있습니다.
| \(2^{3}\)의 자리 | \(2^{2}\)의 자리 | \(2^{1}\)의 자리 | \(2^{0}\)의 자리 | |
| 9(\(1001_{(2)}\)) | 1 | 0 | 0 | 1 |
| 12(\(1100_{(2)}\)) | 1 | 1 | 0 | 0 |
| 14(\(1110_{(2)}\)) | 1 | 1 | 1 | 0 |
| 15(\(1111_{(2)}\)) | 1 | 1 | 1 | 1 |
| 1의 연속 길이 | 4 | 3 | 2 | 1, 1 |
| AND 연산 결과 | 1 ~ 4까지의 합 = 10 | 1 ~ 3까지의 합 = 6 | 1 ~ 2까지의 합 = 3 | 1까지의 합 * 2 = 2 |
| 최종 결과 | \( (10 \: \times \: 2^{3}) \: + \: ( 6 \: \times \: 2^{2} ) \: + \: ( 3 \: \times \: 2^{1} ) \: + \: ( 2 \: \times \: 2^{0} ) \: = \: 112 \) | |||
나. OR
OR 연산은 AND 연산과 반대로 1이 나오면 이후 누적 연산은 무조건 1이 됩니다.
따라서 모든 값이 1일 때의 값을 먼저 구한 후, 0이 연속으로 나오는 길이를 구하여 빼주면 됩니다.
| \(2^{3}\)의 자리 | \(2^{2}\)의 자리 | \(2^{1}\)의 자리 | \(2^{0}\)의 자리 | |
| 9(\(1001_{(2)}\)) | 1 | 0 | 0 | 1 |
| 12(\(1100_{(2)}\)) | 1 | 1 | 0 | 0 |
| 14(\(1110_{(2)}\)) | 1 | 1 | 1 | 0 |
| 15(\(1111_{(2)}\)) | 1 | 1 | 1 | 1 |
| 0의 연속 길이 | 0 | 1 | 2 | 2 |
| OR 연산 결과 | 10 - 0 = 10 | 10 - 1 = 9 | 10 - 3 = 7 | 10 - 3 = 7 |
| 최종 결과 | \( (10 \: \times \: 2^{3}) \: + \: ( 9 \: \times \: 2^{2} ) \: + \: ( 7 \: \times \: 2^{1} ) \: + \: ( 7 \: \times \: 2^{0} ) \: = \: 137 \) | |||
다. XOR
XOR의 진리표는 다음과 같습니다.
| XOR | 0 | 1 |
| 0 | 0 | 1 |
| 1 | 1 | 0 |
쉽게 피연산자가 같으면 0, 다르면 1 이 됨을 알 수 있습니다.
이제 XOR 연산의 특징을 알아봅시다.
\(A \: \bigoplus \: 0 \: = \: A\) → XOR의 항등원은 0
\(A \: \bigoplus \: A \: = \: 0\) → XOR의 역원은 자기 자신
\(A \: \bigoplus \: B \: = \: B \: \bigoplus \: A \) → XOR 교환법칙 성립
\((A \: \bigoplus \: B) \: \bigoplus \: C \: = \: A \: \bigoplus \: (B \: \bigoplus \: C) \: = \: A \: \bigoplus \: B \: \bigoplus \: C \) → XOR 결합법칙 성립
위의 특징들을 이용해 다음과 같이 구간 연산의 결과를 계산할 수 있습니다.
\( V[^{n}_{m}] \: = \: A_{n} \: \bigoplus \: A_{n+1} \: \bigoplus \: ... \: \bigoplus \: A_{m-1} \: \bigoplus \: A_{m} \) 라고 할 때,
\( V[^{n}_{m}] \: = \: 0 \: \bigoplus \: V[^{n}_{m}] \: = \: (V[^{1}_{n-1}] \: \bigoplus \: V[^{1}_{n-1}]) \: \bigoplus \: V[^{n}_{m}] \)
\( = V[^{1}_{n-1}] \: \bigoplus \: (V[^{1}_{n-1}] \: \bigoplus \: V[^{n}_{m}]) \: = \: V[^{1}_{n-1}] \: \bigoplus
\: V[^{1}_{m}]\)
따라서,
\( V[^{n}_{m}] \: = \: V[^{1}_{n-1}] \: \bigoplus \: V[^{1}_{m}]\)
또 0과 1만으로 XOR 연산을 하면 결과를 1의 개수가 홀수이면 1, 짝수이면 0으로 예상할 수 있습니다.
예를 들어, (\(1 \: \bigoplus \: 1 \: \bigoplus \: 0 \: \bigoplus \: 1 \: \bigoplus \: 0 \: \bigoplus \: 1 \: \bigoplus \: 1\))에서
0은 XOR의 항등원이므로,
(\(1 \: \bigoplus \: 1 \: \bigoplus \: 1 \: \bigoplus \: 1 \: \bigoplus \: 1\)) 과 같습니다.
그리고 XOR에서 1의 역원은 1이므로,
\((1 \: \bigoplus \: 1) \: \bigoplus \: (1 \: \bigoplus \: 1) \: \bigoplus \: 1 \: = \: (0) \: \bigoplus \: (0) \: \bigoplus \: 1 \: = 1\)
이제까지 살펴본 XOR 연산의 특징을 활용해봅시다.
원래 문제는 아래와 같으나,
\(A_{1} \: + \: ( A_{1} \: \bigoplus \: A_{2} ) \: + \: ( A_{1} \: \bigoplus \: A_{2} \: \bigoplus \: A_{3} ) \: + \: ... \: + \: (A_{1} \: \bigoplus \: A_{2} \: \bigoplus \: ... \: \bigoplus \: A_{n})\)
\(+ \: A_{2} \: + \: (A_{2} \: \bigoplus \: A_{3}) \: +
( A_{2} \: \bigoplus \: A_{3} \: \bigoplus \: A_{4} ) \: + \: ... \: +
\: (A_{2} \: \bigoplus \: A_{3} \: \bigoplus \: ... \: \bigoplus \: A_{n}) \)
\(...\)
\( + \: A_{n-1} \: + \: ( A_{n-1} \: \bigoplus \: A_{n} ) \)
\( + \: A_{n} \)
덧셈의 교환법칙으로 다음과 같이 바꿀 수 있습니다.
\(A_{1} \)
\( + \: ( A_{1} \: \bigoplus \: A_{2} ) \: + \: A_{2} \)
\( + \: ( A_{1} \: \bigoplus \: A_{2} \: \bigoplus \: A_{3} ) \: + \: (A_{2} \: \bigoplus \: A_{3}) \: + \: A_{3} \)
\(...\)
\(+ \: (A_{1} \: \bigoplus \: ... \: \bigoplus \: A_{n-1}) \: + \: (A_{2} \: \bigoplus \: ... \: \bigoplus \: A_{n-1}) \: + \: ... \: + A_{n-1} \)
\(+ \: (A_{1} \: \bigoplus \: ... \: \bigoplus \: A_{n}) \: + \: (A_{2} \: \bigoplus \: ... \: \bigoplus \: A_{n}) \: + \: ... \: + A_{n} \)
n번째 수까지 XOR 연산을 누적한 값을 \(V_{n}\)(\(V_{0} \: = \: 0\))이라고 하면, 문제를 다시 다음과 같이 바꿀 수 있습니다.
\(V_{0} \: \bigoplus \: V_{1} \)
\( + \: ( V_{0} \: \bigoplus \: V_{2} ) \: + \: ( V_{1} \: \bigoplus \: V_{2} ) \)
\( + \: ( V_{0} \: \bigoplus \: V_{3} ) \: + \: ( V_{1} \: \bigoplus \: V_{3} ) \: + \: ( V_{2} \: \bigoplus \: V_{3} ) \)
\(...\)
\(+ \: ( V_{0} \: \bigoplus \: V_{n-1} ) \: + \: ... \: + \: ( V_{n-2} \: \bigoplus \: V_{n-1} ) \)
\(+ \: ( V_{0} \: \bigoplus \: V_{n} ) \: + \: ... \: + ( V_{n-1} \: \bigoplus \: V_{n} ) \)
하지만 아직까지도 시간복잡도가 \(O(n^{2})\)입니다.
어떻게 선형 시간으로 단축시킬 수 있을까요?
예를 들어 \(A \: = \: [1, 1, 0, 1, 0, 1, 1]\)이라고 해봅시다.
누적 XOR 연산 결과를 표로 나타내면 다음과 같습니다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| \(A_{i}\) | 1 | 1 | 0 | 1 | 0 | 1 | 1 | |
| \(V_{i}\) | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
여기서 알 수 있는 점은 \(V_{i}\)가 1이면 i 까지의 피연산자 중 1이 홀수 개이고, \(V_{i}\)가 0이면 i 까지의 피연산자 중 1이 짝수 개라는 것입니다.
그리고 \((V_{i} \: \bigoplus \: V_{j})\)의 결과는 서로 다른 값이면 1, 같은 값이면 0입니다.
따라서 어떤 \(j\)에 대해서 \(i\)가 0 부터 \((j-1)\)까지의 누적 연산 결과가 서로 다른 것의 갯수를 세면 우리가 풀고자 하는 문제를 빠르게 해결할 수 있습니다.
따라서 \(V_{i}\)의 값이 0인 것의 갯수과, 1인 것의 갯수를 누적하여 미리 세어두면, 이를 활용하여 선형 시간 내에 문제를 해결할 수 있습니다.
\(i\) 까지의 0의 갯수를 \(Z_{i}\), 1의 갯수를 \(O_{i}\)라고 하면 다음과 같이 표로 나타낼 수 있습니다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| \(A_{i}\) | 1 | 1 | 0 | 1 | 0 | 1 | 1 | |
| \(V_{i}\) | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| \(Z_{i}\) | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 |
| \(O_{i}\) | 0 | 1 | 1 | 1 | 2 | 3 | 3 | 4 |
이제 이를 활용하여 \(V_{i}\)가 0이면 \(O_{i}\)를 선택하고, \(V_{i}\)가 1이면 \(Z_{i}\)를 선택하면, 위에서 변환시킨 문제의 한 줄 한 줄이 바로 바로 계산됩니다.
| i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| \(A_{i}\) | 1 | 1 | 0 | 1 | 0 | 1 | 1 | |
| \(V_{i}\) | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
| \(Z_{i}\) | 1 | 1 | 2 | 3 | 3 | 3 | 4 | 4 |
| \(O_{i}\) | 0 | 1 | 1 | 1 | 2 | 3 | 3 | 4 |
| i까지의 누적 연산 결과 | 0 | 1 | 1 | 1 | 3 | 3 | 3 | 4 |
이제는 원래 문제로 돌아가서 해결해봅시다.
| \(2^{3}\)의 자리 |
\(2^{2}\)의 자리 |
\(2^{1}\)의 자리 |
\(2^{0}\)의 자리 |
|||||||||||||
| A | V | Z | O | A | V | Z | O | A | V | Z | O | A | V | Z | O | |
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | |||||
| 9(\(1001_{(2)}\)) | 1 | 1 | 1 | 1 | 0 | 0 | 2 | 0 | 0 | 0 | 2 | 0 | 1 | 1 | 1 | 1 |
| 12(\(1100_{(2)}\)) | 1 | 0 | 2 | 1 | 1 | 1 | 2 | 1 | 0 | 0 | 3 | 0 | 0 | 1 | 1 | 2 |
| 14(\(1110_{(2)}\)) | 1 | 1 | 2 | 2 | 1 | 0 | 3 | 1 | 1 | 1 | 3 | 1 | 0 | 1 | 1 | 3 |
| 15(\(1111_{(2)}\)) | 1 | 0 | 3 | 2 | 1 | 1 | 3 | 2 | 1 | 0 | 4 | 1 | 1 | 0 | 2 | 3 |
| XOR 연산 결과 | 1 + 1 + 2 + 2 = 6 | 0 + 2 + 1 + 3 = 6 | 0 + 0 + 3 + 1 = 4 | 1 + 1 + 1 + 3 = 6 | ||||||||||||
| 최종 결과 | \( (6 \: \times \: 2^{3}) \: + \: ( 6 \: \times \: 2^{2} ) \: + \: ( 4 \: \times \: 2^{1} ) \: + \: ( 5 \: \times \: 2^{0} ) \: = \: 86 \) | |||||||||||||||
