LIST
- 홀수 판별
- -1 판별
- 부호 판별
- 두 수의 부호 일치
- 2의 승수 판별
- 2의 승수로 곱하기, 나누기
- 2의 승수로 나눈 나머지
- 2의 승수로 올림
- 완전이진트리
- swap
- 가장 작은 비트가 나타내는 값
- bit로 나타낸 이진 순열의 다음 순열
- bool 배열 메모리 최적화
1. 홀수 판별
모든 홀수는 이진수로 나타내면 0번 비트가 켜져있으므로, 0번 비트를 검사해주면 된다.
|
1
2
|
if (a & 1) // a가 홀수
else if (!(a & 1)) // a가 짝수
|
cs |
2. -1 판별
-1의 이진수표현은 모든 비트가 켜진 것이므로, ~(-1)은 모든 비트가 꺼진 0이다.
따라서 ~a가 0이라면 a는 -1, ~a가 0이 아닌 수라면 a는 -1이 아닌 수이다.
|
1
2
3
4
5
|
for(int i = n - 1; ~i; --i) // n-1에서 0까지 반복한다. i = -1이면 ~i = 0 이므로 반복을 종료한다.
int d[N];
memset(d, -1, sizeof d);
if (~d[x]) return d[x]; // -1로 초기화된 dp 테이블이 계산된 것인지(-1이 아닌지) 확인한다.
|
cs |
3. 부호 판별
32bit 정수로 음수를 표현할 때는 2의 보수법을 사용한다. 2의 보수법 상 음수는 31번째 비트가 1이 되므로 31번째 비트를 검사해 부호를 판별 가능하다.
|
1
2
|
if (a >> 31 & 1) // a는 음수
else if (!(a >> 31 & 1)) // a는 양수
|
cs |
4. 두 수의 부호 일치
32bit 정수 a와 b의 부호가 서로 다르다면 a의 31번째 비트와 b의 31번째 비트가 달라야하며 (a ^ b)의 31번째 비트는 1이 된다. 즉, (a ^ b)가 음이 아닌 정수인지 검사하면 두 수의 부호 일치를 판별할 수 있다.
|
1
2
|
if ((a ^ b) < 0) // a와 b의 부호가 다름
else if ((a ^ b) >= 0) // a와 b의 부호가 일치
|
cs |
5. 2의 승수 판별
a가 2의 승수라면, a는 단 한 개의 비트만이 켜진 수이며, a - 1은 해당 비트가 0이고 하위 비트가 모두 켜진 수이다.
따라서 a & a - 1의 결과가 0이라면 a는 2의 승수이며 이외에는 2의 승수가 아니다.
|
1
2
|
if (a & a - 1) // a는 2의 승수가 아님
else if (!(a & a - 1)) // a는 2의 승수
|
cs |
6. 2의 승수로 곱하기, 나누기
a << x 는 a$\times 2^x$ 와 같다.
|
1
|
a << x
|
cs |
a >> x 는 a$\div 2^x$ (정수 나눗셈) 와 같다.
|
1
|
a >> x
|
cs |
7. 2의 승수로 나눈 나머지
a >> x 에서 지워지는 하위 비트들이 곧 나머지이다.
(1 << x) - 1은 x개의 하위 비트들만 켜진 수이며, 이를 a와 and 연산하여 나머지를 구할 수 있다.
|
1
|
a & (1 << x) - 1
|
cs |
8. 2의 승수로 올림
1, 2, 4, 8, 16 차례로 shift한 결과를 or 연산하면 최상위비트의 하위비트가 모두 켜진 상태가 된다.
여기에 1을 더해주면 2의 승수로 올림한 결과를 얻을 수 있다.
어떤 입력에 대해서도 동일한 연산 수를 보장하므로 $O(1)$.
|
1
2
3
|
x--;
for(int i =1; i<=16; i<<=1) x |= x >> i;
x++;
|
cs |
9. 완전이진트리
완전이진트리(Complete Binary Tree)는 1차원 배열로 나타낼 수 있다. 이 때 부모 자식 형제 노드를 인덱스의 bit연산으로 찾을 수 있다. heap, segment tree 등의 자료구조가 일반적으로 완전이진트리로 구현된다.
- 부모노드
a의 부모노드는 a $\div 2$ (정수 나눗셈) 위치에 있다.
|
1
|
a >> 1
|
cs |
- 형제노드
a의 형제노드는 0번 비트만 다른 위치에 있다.
|
1
|
a ^ 1
|
cs |
- 왼쪽 자식노드
a의 왼쪽 자식노드는 a $\times 2$ 위치에 있다.
|
1
|
a << 1
|
cs |
- 오른쪽 자식노드
a의 오른쪽 자식 노드는 a $\times 2 + 1$ 위치에 있다.
a << 1 의 결과가 항상 짝수(0번 비트가 0)이므로 or 1 연산을 해도 오류가 없다.
|
1
|
a << 1 | 1
|
cs |
10. swap
xor 연산의 역원은 자기 자신임을 이용한다.
https://ko.wikipedia.org/wiki/XOR_%EA%B5%90%EC%B2%B4_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
XOR 교체 알고리즘 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. XOR 교체 알고리즘은 임시 변수를 두지 않고, 두 개의 변수를 배타적 논리합(XOR) 비트 연산을 이용하여 교체하는 알고리즘이다. 이 알고리즘은 컴퓨터 프로그래밍 분야에서 프로세서의 최적화 능력이 부족했을 때 대안으로 자주 사용되었다. XOR 교체 알고리즘은 세 개의 XOR 연산을 사용하여 임시 변수 없이 두 변수를 교환한다. 의사코드로는 다음과 같이 표현할 수 있다. X ← X XOR Y Y ← X XOR Y X ←
ko.wikipedia.org
|
1
|
void swap(int &a, int &b) { a ^= b ^= a ^= b; }
|
cs |
11. 가장 작은 비트가 나타내는 값
2의 보수 체제에서 -a의 이진수 표현은 ~a + 1과 같다.
이 값은 a의 최하위비트의 하위비트는 모두 0, 상위비트는 모두 a의 반전인 형태가 된다.
따라서 a & -a 는 a의 최하위비트 만이 켜진 수이다.
이는 동적 부분합 자료구조인 fenwick tree에서 유용하게 응용된다.
|
1
2
|
int cnt = 0;
while (a) a -= a & -a, cnt++; // 매우 빠른시간에 켜진 bit만 탐색한다.
|
cs |
12. bit로 나타낸 이진 순열의 다음 순열
0, 1로 이루어진 이진 순열을 bit로 나타낸 것을 입력으로 받아, 사전적으로 다음의 순열을 반환한다.
|
1
2
3
4
|
int next_p(int v){
int t = v | (v-1);
return (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(v) + 1));
}
|
cs |
13. bool 배열 메모리 최적화
x가 $32 \times Q + R$로 유일하게 정해지므로 b[x]를 b[Q](R)로 압축해 나타낼 수 있다.
1byte bool 변수가 8bit이고 1bit에 수 하나를 저장할 수 있어 기존 대비 $\frac {1}{8}$배의 메모리 절감이 가능하다.
|
1
2
3
4
|
bool b[N / 32];
bool& getb(int x) {
return b[x >> 5] & (1 << x - (x >> 5) * x);
}
|
cs |
+ 더 많은 bithack
http://graphics.stanford.edu/~seander/bithacks.html
Bit Twiddling Hacks
Bit Twiddling Hacks By Sean Eron Anderson seander@cs.stanford.edu Individually, the code snippets here are in the public domain (unless otherwise noted) — feel free to use them however you please. The aggregate collection and descriptions are © 1997-2005 S
graphics.stanford.edu
