변수에서 Bit에서 0이나 1의 위치 또는 갯수를 구하는 경우 컴파일러는 내장 함수들을 지원한다.
GCC나 Clang에서 간단한 코드를 살펴보자.
#include <stdio.h>
// for i in range(22): print('"{}", '.format(re.sub(r'(\d{4})', r'\1 ', bin(i)[2:].rjust(32, '0')).rstrip()), end='')
char *bits[] = { "0000 0000 0000 0000 0000 0000 0000 0000", "0000 0000 0000 0000 0000 0000 0000 0001", "0000 0000 0000 0000 0000 0000 0000 0010", "0000 0000 0000 0000 0000 0000 0000 0011", "0000 0000 0000 0000 0000 0000 0000 0100", "0000 0000 0000 0000 0000 0000 0000 0101", "0000 0000 0000 0000 0000 0000 0000 0110", "0000 0000 0000 0000 0000 0000 0000 0111", "0000 0000 0000 0000 0000 0000 0000 1000", "0000 0000 0000 0000 0000 0000 0000 1001", "0000 0000 0000 0000 0000 0000 0000 1010", "0000 0000 0000 0000 0000 0000 0000 1011", "0000 0000 0000 0000 0000 0000 0000 1100", "0000 0000 0000 0000 0000 0000 0000 1101", "0000 0000 0000 0000 0000 0000 0000 1110", "0000 0000 0000 0000 0000 0000 0000 1111", "0000 0000 0000 0000 0000 0000 0001 0000", "0000 0000 0000 0000 0000 0000 0001 0001", "0000 0000 0000 0000 0000 0000 0001 0010", "0000 0000 0000 0000 0000 0000 0001 0011", "0000 0000 0000 0000 0000 0000 0001 0100", "0000 0000 0000 0000 0000 0000 0001 0101" };
int main() {
for (int i=0;i<21;i++) {
printf("%s clz: %d ffs: %d popcount: %d\n", \
bits[i], \
__builtin_clz(i), \
__builtin_ffs(i), \
__builtin_popcount(i));
}
return 0;
}
Output
0000 0000 0000 0000 0000 0000 0000 0000 clz: 31 ffs: 0 popcount: 0
0000 0000 0000 0000 0000 0000 0000 0001 clz: 31 ffs: 1 popcount: 1
0000 0000 0000 0000 0000 0000 0000 0010 clz: 30 ffs: 2 popcount: 1
0000 0000 0000 0000 0000 0000 0000 0011 clz: 30 ffs: 1 popcount: 2
0000 0000 0000 0000 0000 0000 0000 0100 clz: 29 ffs: 3 popcount: 1
0000 0000 0000 0000 0000 0000 0000 0101 clz: 29 ffs: 1 popcount: 2
0000 0000 0000 0000 0000 0000 0000 0110 clz: 29 ffs: 2 popcount: 2
0000 0000 0000 0000 0000 0000 0000 0111 clz: 29 ffs: 1 popcount: 3
0000 0000 0000 0000 0000 0000 0000 1000 clz: 28 ffs: 4 popcount: 1
0000 0000 0000 0000 0000 0000 0000 1001 clz: 28 ffs: 1 popcount: 2
0000 0000 0000 0000 0000 0000 0000 1010 clz: 28 ffs: 2 popcount: 2
0000 0000 0000 0000 0000 0000 0000 1011 clz: 28 ffs: 1 popcount: 3
0000 0000 0000 0000 0000 0000 0000 1100 clz: 28 ffs: 3 popcount: 2
0000 0000 0000 0000 0000 0000 0000 1101 clz: 28 ffs: 1 popcount: 3
0000 0000 0000 0000 0000 0000 0000 1110 clz: 28 ffs: 2 popcount: 3
0000 0000 0000 0000 0000 0000 0000 1111 clz: 28 ffs: 1 popcount: 4
0000 0000 0000 0000 0000 0000 0001 0000 clz: 27 ffs: 5 popcount: 1
0000 0000 0000 0000 0000 0000 0001 0001 clz: 27 ffs: 1 popcount: 2
0000 0000 0000 0000 0000 0000 0001 0010 clz: 27 ffs: 2 popcount: 2
0000 0000 0000 0000 0000 0000 0001 0011 clz: 27 ffs: 1 popcount: 3
0000 0000 0000 0000 0000 0000 0001 0100 clz: 27 ffs: 3 popcount: 2
사용한 내장 함수들이다.
- __builtin_clz : 상위 비트(MSB)부터 0의 갯수, 입력 0에 대해 보장하지 않음 (undefined)
- __builtin_ffs : 하위 비트(LSB)부터 첫번째 1의 위치, 못찾으면 0
- __builtin_popcount : 비트 1의 갯수
clz는 0의 경우도 1인 경우도 31인 것을 볼 수 있다. 0인 경우 처리를 해야한다.
이 외에 ctz 등의 함수도 있다.
- __builtin_ctz : 하위 비트(LSB)부터 0의 갯수, 입력 0에 대해 보장하지 않음 (undefined)
Assembly
내장 함수들이 어셈블리에서 어떻게 처리되는지 살펴보자.
x86 64비트
# gcc -O2 -S -march=native test.c
...
tzcntl %ebx, %r8d
popcntl %ebx, %r9d
lzcntl %ebx, %ecx
x86 32비트
# gcc -O2 -m32 -S test.c
...
pushl %esi
call __popcountsi2@PLT
xorl %edx, %edx
addl $16, %esp
rep bsfl %esi, %edx
addl $1, %edx
bsrl %esi, %ecx
xorl $31, %ecx
arm 64비트
# aarch64-linux-gnu-gcc -O2 -S test.c
...
cnt v0.8b, v0.8b
rbit w4, w19
clz w4, w4
clz w3, w19
add w4, w4, 1
add x19, x19, 1
addv b0, v0.8b
아키텍처에 따라 다음 어셈블리 명령어를 사용하는 것을 확인할 수 있다.
- x86 : bsf, bsr
- x86_64 : tzcnt, popcnt, lzcnt
- arm64 : clz, cnt
이처럼 아키텍처마다 instruction 레벨에서 bit 연산을 지원 한다.
기타
위의 내장 함수들은 32비트 기준이며 long 타입과 long long 타입은 __builtin_ffsll과 같이 l, ll 접미사를 붙여줘야 한다.
*nix 계열에서는 LP64 모델을 사용하며 L, LL, ULL 등의 접미사를 사용하면 64비트가 된다.
1 대신 0을 찾는등 반대의 경우는 Bitwise NOT(~) 연산으로 비트를 뒤집으면 된다.
그 외에도 아래의 popcount 구현처럼 많은 bit hack들이 존재한다.
int swar(uint32_t i) {
i = i - ((i >> 1) & 0x55555555);
i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
return (((i + (i >> 4)) & 0x0F0F0F0F) * 0x01010101) >> 24;
}
더 관심이 있다면 Bit Twiddling Hacks이나 Linux 소스코드 등 에서 더 많은 것을 찾아볼 수 있다.