유용한 비트연산들 모음

문자 | 문자열

대문자와 소문자는 정확히 32만큼 차이 난다. 32는 (1<<n)의 형태이므로, '간단한' 비트 연산을 적용하기 가장 쉽다.

1. 항상 대문자로 만들기

char f(char x) { return x & ~32; }

32를 나타내는 비트만 0으로 놓고, 문자와 AND를 취하면 32의 비트만 끌 수 있다.

 

2. 항상 소문자로 만들기

char f(char x) { return x | 32; }

 

3. toggle (소문자는 대문자로, 대문자는 소문자로)

char f(char x) { return x ^ 32; }

---

정수

 

1. 2의 지수 형태 판별 :

bool f(int n) { return !(n & (n - 1)); }

 

2. 모든 n개의 비트가 켜져 있는지 확인

bool f(int bt) { return (bt + 1) == (1 << n); }

비트마스킹 문제를 풀 때 자주 사용된다. n개의 비트를 일일이 켜서 확인하는 건 매우 번거롭지만,

모든 비트가 1이라면 1을 더했을때 단 한 개의 비트만 1인, 곧 1000...(2)의 형태가 됨을 이용해 간단히 구현할 수 있다.

여담으로, 순열 완전탐색을 구현할 때 재귀로 해도 간단하지만, [0, (1<<n) )을 탐색해도 된다.

만약, 공집합이 의미가 없다면 [1, (1<<n) -1 )을 탐색하면 된다.

 

3. 비트내 켜져 있는 비트 개수 구하기

int f(int bt) { return __builtin_popcount(bt); }

직접 하나씩 쉬프트 하며 확인하면 O(logN)이 될 수밖에 없다.

내부에 조금 복잡한 비트연산 몇 가지로 조합되어 O(1)에 작동하는 __builtin_popcount()를 사용하면

간단하고도 훌륭한 성능의 구현이 가능하다.

 

4. 비트내 가장 왼쪽에 켜진 비트 위치 구하기

int f(int bt) { return 31 - __builtin_clz(bt); }

 

__builtin_clz()는 가장 왼쪽에 있는 켜진 비트를 기준으로, 왼쪽에 존재하는 비트의 개수를 리턴한다.

 

 

 

5. 비트내 가장 오른쪽에 켜진 비트 위치 구하기

int f(int bt) { return __builtin_ctz(bt); }

clz()에서 왼쪽과 오른쪽만 달라졌다.

 

6. 비트내 가장 오른쪽에 켜진 비트 값 구하기

int f(int bt) { return bt & (-bt); }

당연히, 4에서 1<<f(bt)를 해도 같은 결과가 나온다.  

 

7. [s, e]에서 mid 찾기

int f(int s, int e) { return s + e >> 1; }

비트연산 쉬프트는 +보다 우선순위가 낮기에, 괄호를 안 붙여도 된다.

(s+e)/2보다 미세하게 빠르기도 하거니와, 귀찮게 괄호를 열고 닫을 필요가 없음이 유용하다.

이분탐색, 세그먼트 트리등 mid값은 원체 자주 쓰인다.

 

8. 정수 n 홀수 판별

bool f(int n) { return n & 1; }

 

---

참고 : http://www.secmem.org/blog/2019/10/19/handy-function-about-bit/