본문 바로가기

공부/알고리즘

[완전탐색/조합] 비트 연산을 이용하여 조합 만들기 - 비트 조합

반응형

예전에 대학생활을 하면서 '로봇 연구회' 동아리 활동을 하면서 아트메가 128을 사용했기 때문에 비트연산을 이용한 경험이 있습니다.


덕분에 프로그래밍을 하면서 비트를 이용해서 문제를 해결한 적이 있는데, 


이번에는 그 중에서도 특히 인상 깊었던 '조합 만드는 법'에 대해서 설명하려고 합니다!


우선, 그 전에 비트 연산에 대해서 간단히 알아봅시다.


1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다. 

ex) 0b 1111 & 0b 0011 = 0b 0011


2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.

ex) 0b 1100 | 0b 1010 = 0b 1110


3. ~ : 모든 비트를 1이면 0으로 0이면 1로 반전합니다.

ex ) ~0b 1100 = 0b 0011


4. >> : 1 비트 오른쪽으로 이동합니다.

ex) 0b 110 >> 1 = 0b 011


5. << : 1 비트 왼쪽으로 이동합니다.

ex) 0b 110 << 1 = 0b 1100


참고로 -는 2의 보수를 만드는 연산입니다. 이는, 모든 비트를 반전한 후에 1을 더한 값과 같습니다!

예를 들면, 0001 1010의 값을 가지는 a가 있다고 하면, -a는 1110 0101 + 1 = 1110 0110 이 되는 것입니다!

이 2의 보수의 특징으로 아주 재미있는 일을 할 수 있습니다. 바로, '최하위 비트'를 구하는 것이죠!


1을 더하기 전에 1과 0을 반전 시킨다는 것은, 결국 0이었던 부분이 다 1이 된다는 것입니다.

예를들면, 10100000 이라는 수가 있다면, 1과 0을 반전시키면 01011111 이 됩니다.


여기서 원래 수에서 맨 하위에 1이 있던 부분의 비트를 X라고 합시다. (진하고 밑줄 그어진 비트)


위에서 보듯이, X비트는 0이 되고, 해당 비트의 뒷 부분은 모두 1이 됩니다!


이제 거기에 1을 더하면? 계속해서 올림이 일어나서 결국 X는 다시 1이 됩니다!

반대로, X비트의 뒷 부분은 모두 0이 되겠죠!

위에 있던 01011111 에서 1을 더하면 01100000이 되는 것입니다!


여기에 더해서 처음의 수와 2의 보수를 취한 수를 비교했을 때, X비트의 왼쪽 비트의 0과 1이 서로 반대인 것을 확인할 수 있습니다.

또한, X비트의 오른쪽은 모두 0이기 떄문에 

결국, 처음에 있던 수와 & 연산을 수행하면, X비트만 1이 됩니다. 


따라서, b & -b 를 하면 맨 하위의 1 부분을 구할 수 있습니다.


위의 경우는 10100000 & 01100000 = 00100000를 얻을 수 있습니다.


이를 조금 응용하면 ~b & -~b를 사용해서 최 하위에 있는 0의 위치를 1로 만들 수 있습니다!  

위에서 사용했던 10100000에 이 방법을 이용하면 00000001 이 됩니다!


이제 이를 이용해서 어떻게 비트로  조합을 만들어 낼 수 있는지 보겠습니다!

우선 조합을 만들어가는 과정을 보겠습니다.


 1. 맨 하위에서 연속되어 있는 1 비트들 중에서 상위 비트를 1칸 왼쪽으로 움직입니다.

 2. 움직인 비트보다 오른쪽에 있는 비트들은 오른쪽 끝으로 붙입니다.

 3. 모두 탐색했으면 빠져나옵니다.


아래 그림은 실제로 이 어떻게 나타나는지 보는 출력값 입니다.




어떻게 만들 수 있는지 우선 코드를 보여드리겠습니다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#pragma once
#include<cstdio>
 
int num[15];
 
int getZeros(int n)
{
    int num = 0;
    while ((n & 1== 0)
    {
        num++;
        n >>= 1;
    }
 
    return num;
}
 
void func(int bit, int n)
{
    int msb = 1 << (n - 1);
    while (msb)
    {
        printf("%d ", (bool)(msb & bit));
        msb >>= 1;
    }
    printf("\n");
}
 
int main()
{
    int bit;
    int n, m;
 
    scanf("%d %d\n"&n, &m);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d \n", num + i);
    }
 
    bit = (1 << m) - 1;
 
    while (bit < (1 << n))
    {
        func(bit, n);
        int temp = bit | ((bit & -bit) - 1);
 
        bit = (temp + 1| (((~temp & -~temp) - 1>> (getZeros(bit) + 1));
    }
 
    return 0;
}
cs


핵심 부분은 main에 있는 while입니다.


    while (bit < (1 << n))
    {
        func(bit, n);
        int temp = bit | ((bit & -bit) - 1);
 
        bit = (temp + 1| (((~temp & -~temp) - 1>> (getZeros(bit) + 1));
    }



우선 temp의 역할을 알아봅시다. bit & -bit는 최하위 1비트의 위치를 구하는 것이었습니다.


거기에 1을 빼준다는 것은, 최하위 뒷부분을 모두 1로 만든다는 의미입니다. 

거기에, 원래 bit와 OR연산을 수행하면 최하위 1비트 뒤는 모두 1이 됩니다.


예를 들면, bit가 1100 1100 이면, temp는 1100 1111 이 됩니다!


temp에 1을 더한다는 것은, 위에서 비트 조합의 3 단계 중에서 1번에 해당합니다. 위의 예에서 temp에 1을 더하면 1101 0000이 됩니다.


getZeros() 함수는 비트에서 맨 오른쪽부터 1이 나오기 전까지 0의 개수가 몇 개인지 반환해주는 함수입니다. 

(~temp & -~temp) - 1의 값은 맨 하위 비트 0 을 1로 바꾼 뒤 1을 뺀 값입니다. 

결국, 맨 하위에 있는 0 오른쪽의 비트를 모두 1로 켜준 값이 됩니다. 


위의 예에서는 0000 1111이 됩니다.


이제 마지막 비트들을 어떻게 오른쪽으로 붙일 수 있는지 확인해 봅시다.


만들어야 하는 비트는, 1101 0001 입니다.

그리고, temp + 1을 통해서 1101 0000 을 만들 수 있었습니다!

그리고, (~temp & -~temp) - 1을 통해서 0000 1111을 얻었습니다.


그렇다면! 0000 1111을 딱 오른쪽으로 3 칸을 밀면 원하는 비트를 만들 수 있는 것입니다!


왜 하필 3 칸 일까요!? 

우선, 처음 비트가 1100 1100입니다! 오른쪽으로 2칸만 움직이면 비트를 오른쪽 끝으로 붙여버릴 수 있는 것이죠!


하지만, 1100 1100에서 진하게 칠한 부분이 1101 0000으로 이동했음에도 불구하고, 0000 1111로 표현된 것을 볼 수 있습니다. 따라서, 저 부분까지 처리해줘야 하기 때문에, 처음에 있던 0의 개수보다 1칸 더 움직여야 하는 것입니다! 이렇게 getZeros(bit) + 1 만큼 1을 오른쪽으로 밀어넣어서 사라지게하면 비트 조합을 만들기 위한 3단계에서 2단계를 수행할 수 있습니다.


위의 예에서는 1100 1100이기 때문에 오른쪽으로 3 칸을 움직여야하고, 0000 1111은 0000 0001이 됩니다.

그리고 temp+1과 or 연산을 해주면! 1101 0000 | 0000 0001 = 1101 0001 입니다! 이렇게 해서 원하는 결과를 얻을 수 있습니다!


그리고 비트가 1 << n 보다 커지면, 그 이전이 모든 경우의 수를 돌아봤다는 것이므로 루프를 빠져나오면 됩니다! 



반응형