[Algorithm/C++] 유용한 비트연산 / builtin 함수

이번 글은 특정 알고리즘에 대한 설명이라기보다는, 수학/정수론 문제를 풀 때 꽤나 자주, 유용하게 쓰이는 여러 가지 비트연산들에 대해 설명하고자 합니다.

들어가기에 앞서, 비트 연산자 &(and), |(or), ^(xor), ~(not), <<(left shift), >>(right shift)에 대해 알고 계시면 좋습니다.

간단한 예로, n개 버튼 중 어떤 m개의 버튼을 눌러보는 모든 경우의 수를 시도해보아야 하는 상황에 대해 생각해 봅시다.

백준 N과 M 시리즈 풀이처럼, 아래와 같이 재귀함수로 구현할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

bool button[20];//0~n-1, n<=20이라고 가정.
void f(int n,int m,int cur,int pick){
    if(pick==m){//m개의 버튼을 누른 경우.
        for(int i=n-1;i>=0;i--)printf("%d",button[i]);//n번째 버튼부터 순서대로 출력.
        printf("\n");
        return;
    }
    if(cur==n)return;//더 이상 고를 버튼이 없음.

    button[cur]=0;
    f(n,m,cur+1,pick);//이번 버튼을 누르지 않고 다음 버튼으로 넘어감.

    button[cur]=1;
    f(n,m,cur+1,pick+1);//이번 버튼을 누르고 다음 버튼으로 넘어감.

    button[cur]=0;//켰던 버튼을 다시 꺼줌.
}

int main(){
    int n,m;scanf("%d%d",&n,&m);
    f(n,m,0,0);
    return 0;
}

 

이 구현을 단순화하기 위해, << 연산과 $__builtin_popcount()$ 함수가 사용됩니다.

먼저 버튼의 모든 상태를 검사하려면, 구간은 $[0,2^n)$으로 나타낼 수 있습니다.

이때 $1<<n$ 연산으로 $2^n$을 간단히 표현할 수 있습니다. (math 헤더의 pow(2,n) 연산에 비해 속도도 훨씬 빠릅니다.)

이제 for문을 돌면서 현재 버튼의 상태가 $state$일 때, $__builtin_popcount(state)$는 $state$의 켜진 비트 수를 리턴하는 내장 함수입니다.

따라서 아래와 같이 for문으로 구현을 단순화할 수 있습니다.

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int state=0;state<1<<n;state++)
        if(__builtin_popcount(state)==m){
            printf("%d\n",state);
        }
    return 0;
}

위의 재귀함수 결과와 똑같이 이진수 형태로 출력하고 싶다면, 아래와 같이 bitset 컨테이너를 사용하면 됩니다.

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,m;scanf("%d%d",&n,&m);
    for(int state=0;state<1<<n;state++)
        if(__builtin_popcount(state)==m){
            cout<<bitset<20>(state)<<"\n";//길이20의 이진수로 표현.
        }
    return 0;
}

 

재귀함수 구현에서는 i번째 버튼의 상태를 $button[i]$ 값으로 확인할 수 있었지만, 모든 버튼의 상태가 int형 숫자 $state$에 들어있는 경우에는 어떻게 관리할 수 있을까요?

1) i번째 버튼을 눌렀는가?

-> $state&(1<<i)$값이 0이라면 버튼을 누르지 않은 것이고, 0이 아니라면(=값이 $1<<n$이라면) 버튼을 누른 것입니다.

이때 버튼을 누른 상태의 값을 $1<<n$이 아니라 1로 표현하고 싶다면, $state>>i&1$과 같이 표현하면 됩니다.

$state>>i$를 하면서 i번째 버튼의 비트값을 $2^0$자릿수로 끌어내리고, 1과의 and연산을 통해 그 비트값이 1인지 확인해 준 겁니다.

2) i번째 비트를 켜거나 끄고 싶다.

1. i번째 비트를 켠다 -> $state+(1<<i)$ 과 같이 표현할 수 있습니다. 이때 문제가 발생하는데, 만약 i번째 비트가 이미 켜져 있었다면 carry(받아올림)가 발생합니다. 따라서 기존 i번째 비트의 여부와 상관없이 1로 만들고 싶다면, $state|(1<<i)$로 표현하면 됩니다.
2. i번째 비트를 끈다 -> $state-(1<<i)$ 과 같이 표현할 수 있습니다. 마찬가지로 만약 i번째 비트가 이미 꺼져있었다면 borrow(받아내림)가 발생합니다. 따라서 기존 i번째 비트의 여부와 상관없이 0으로 만들고 싶다면, $state&~(1<<i)$로 표현하면 됩니다.

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int state=21;//10101

    int button=2;
    printf("%d\n",state+(1<<button));//11001 -> 잘못된 결과!
    printf("%d\n",state|(1<<button));//10101 -> 켜진 비트를 켰으므로 변화 없음
    button=1;
    printf("%d\n",state|(1<<button));//10111

    printf("%d\n",state-(1<<button));//10011 -> 잘못된 결과!
    printf("%d\n",state&~(1<<button));//10101 -> 꺼진 비트를 껐으므로 변화 없음
    button=2;
    printf("%d\n",state&~(1<<button));//10001
    return 0;
}

 

다음으로, $__builtin_clz()$, $__builtin_ctz()$ 함수에 대해 알아봅시다.

1) $__builtin_clz()$

count leading zeros라는 의미로, MSB(Most Significant Bit)부터 1을 만나기 전까지의 0의 개수를 리턴하는 함수입니다.

예를 들어 $__builtin_clz(19)$ = 27인데, int의 크기가 32비트이므로 19 = 00000000 00000000 00000000 00010011 (27개)라서 그렇습니다.

long long 자료형의 경우, 함수명 뒤에 ll을 붙여 사용하며, $__builtin_clzll(19)$ = 32+27 = 59입니다.

그래서 이걸 어디다 써먹냐 하면,

어떤 int형 정수 x보다 큰 정수 중, 가장 작은 2의 거듭제곱수를 찾을 때 $1<<(32-__builtin_clz(x))$로 한 번에 찾을 수 있습니다!

 

2) $__builtin_ctz()$

count trailing zeros라는 의미로, LSB(Least Significant Bit)부터 1을 만나기 전까지의 0의 개수를 리턴하는 함수입니다.

예를 들어 $__builtin_ctz(40)$ = 3인데, 40 = 00000000 00000000 00000000 00101000 (3개)라서 그렇습니다.

마찬가지로 long long 자료형의 경우, 함수명 뒤에 ll을 붙여 사용하시면 됩니다.

이 함수 역시, 어떤 정수 x를 나누는 가장 큰 2의 거듭제곱수를 찾을 때 $1<<__builtin_ctz(x)$로 한 번에 찾을 수 있습니다!

이 값의 더 간단한 표현으로는 $x&-x$ 가 있는데(?!), 펜윅 트리(Fenwick Tree, Binary Indexed Tree)에서 구간을 업데이트할 때 사용되기도 합니다.

 

#include <bits/stdc++.h>
using namespace std;

int main(){
    int x=40;
    printf("%d\n",1<<(32-__builtin_clz(x)));//40보다 큰 가장 작은 2의 거듭제곱수=64
    printf("%d\n",1<<__builtin_ctz(x));//40을 나누는 가장 큰 2의 거듭제곱수=8
    printf("%d\n",x&-x);//마찬가지로 8.
    return 0;
}

 

 

 

여담으로,$memset()$ 함수에 대해 소개하며 글을 마치겠습니다.

문제를 푸실 때, 길이 $n$의 int형 배열 $a$의 모든 값을 매우 큰 값으로 초기화해줘야 하는 상황을 많이 접해보셨을 겁니다.

이때 주로 $fill(a,a+n,1e9)$ 와 같이 사용하곤 하는데,

$memset(a,0x3f,sizeof(a))$ 으로 $fill()$ 함수보다 더 빠르게 초기화할 수 있습니다.

memset은 1바이트 단위로 값을 초기화하는데, 16진수 0x3f = 00111111 이므로

4바이트인 int형 배열은 모두 00111111 00111111 00111111 00111111 = 1061109567 (약 10억)으로 초기화됩니다.

하지만 만약 너무 큰 값으로 초기화하고 싶은 욕심이 생겨서 $memset(a,0xff,sizeof(a))$ 과 같이 사용한다면,

MSB인 부호비트까지 건드려버려서 -1로 초기화됩니다.

 

 

 

여러 가지 함수를 간략히 설명하려니 두서없는 글이 된 것 같은데, 이해하기 어렵거나 더 필요한 정보가 있다면 수시로 업데이트하겠습니다.

긴 글 읽어주셔서 감사합니다.