비트연산 - Bit Operation

비트연산

• 비트연산 매우매우 유용하다. 특히 전체 부분집합의 갯수를 헤아리거나, 모든 원소들의 부분합? 이렇게 구할때는 매우 유용하게 사용할 수 있다..

• 일반적으로 문제를 풀거나 할때 쓰는 >> or << 연산자는 arithmetic right shift이다 shift를 해도 부호비트는 건들지 않겠다는 의미이다.

활용 1

• 첫번째 이분탐색을 할 때 mid는 mid = (le + ri) / 2를 mid = le + ri >> 1 이런식으로 해줄 수 있다 이렇게 하면 shift 연산자는 우선순위가 낮아서 괄호가 필요없다는 것이 장점!

활용 2

• 카카오 블라인드 후보키에서도 bit연산이 많이 필요하다 만약 해당 숫자에서 켜진 bit의 수를 알고자할 때도 비트연산이 필요하다.

int countBits(int x) {
    int ret = 0;
    while(ret) {
        if(x & 1) ++ret; // 해당 x의 bit의 첫번째에 켜져있다. 

        // 그후에 작업했던 bit는 지운다
        x = x >> 1; // x를 오른쪽으로 1칸 shift이동!
    }
}

활용 3 (해당 bit가 켜져있는지 확인하자) & 사용

• 해당 자리의 bit만 1로 해놓고 나머지는 0인 새로운 값을 만들고, 새로운 값과 기존의 값과 (ex :num) 비교해서 해당 위치가 켜져있으면 true로 반환 할 수 있다

bool getBit(int num, int i) {
    return (num & (1 << i) != 0;
}

활용 4 (해당 bit를 키는 작업) | 사용

• 해당 자리의 bit만 1로 해놓고 나머지는 0인 새로운 값을 만들고, 새로운 값과 기존의 값과 (ex :num) 비교해서 해당 위치가 켜져있으면 true로 반환 할 수 있다

bool setBit(int num, int i) {
    return (num | (1 << i);
}

활용 5 (해당 bit를 clear 작업) ~ 사용

• 1을 i번 해당 bit까지 << 한뒤 ~을 하면 값이 뒤집힌다 해당 bit만 0이 되고 나머지는 1로 되서 그것을 또 &하면 원하는 bit만 꺼지게된다.

bool setBit(int num, int i) {
    return (num & ~(1 << i);
}

출처 : 엔지니어 대한민국님 자료구조 알고리즘