비트 연산

비트를 잘 이용하면 연산을 빠르고, 메모리를 조금 사용하면서 수행할 수 있다.

 

1) N개의 비트를 1로 설정하고 싶다면, (1<<N)-1을 수행한다.

만약 N이 4라면 1을 N번 shift 한 결과는 10000이 된다.

여기서 1을 빼주면 1111이 되어, 결과적으로 4개의 비트를 1로 설정한 것이 된다.

 

2) 원소가 N개일 때의 모든 부분집합을 구하려면 1<<N을 이용한다.

1을 n번 shift하면 2의 n제곱의 값을 갖게 된다.

이를 집합으로 표현해보면, 원소가 n인 경우의 모든 부분집합의 수를 의미한다.

#include <iostream>
using namespace std;

void Subsets(char arr[], int n)
{
    for(int i=0; i<(1<<n); i++) //공집합 제외하려면 1부터
    {
        cout<<i<<" : ";
        cout<<"{";
        for(int j=0; j<n; j++)
        {
            if(i&(1<<j)) cout<<arr[j];
        }
        cout<<"}"<<endl;
    }
}

int main()
{
    char data[] = {'A', 'B', 'C', 'D'};
    int size = sizeof(data)/sizeof(char);
    Subsets(data,size);
    return 0;
}

위의 코드를 수행하면 공집합 포함 16개의 부분집합들을 출력할 수 있다.

 

3) i의 j번째 비트가 1인지 아닌지를 알고 싶다면 i&(1<<j)를 수행한다.

1을 j번 shift하면 알고자 하는 비트에 1이 위치하게 된다. 

그 후, i와 & 연산을 하게 되면 두 비트가 1인 경우에만 1의 값을 갖게 되므로, 

i의 j번째 비트가 1인 경우에는 1이 되고, 0인 경우에는 0이 된다.