Abseil Code Review · 49/79

absl::bits — popcount·countl_zero

2026년 6월 12일 · Hawk · 2분 읽기

#C++20 `<bit>`의 polyfill

C++20에서 <bit> 헤더가 들어왔다. std::popcount, std::countl_zero, std::countr_zero, std::bit_width 등. C++14/17 코드베이스에서는 쓸 수 없지만 Abseil이 동일 인터페이스를 미리 제공한다.

1
#include "absl/numeric/bits.h"
2

3
uint32_t x = 0b1011'0100;
4

5
int pop  = absl::popcount(x);       // 4 — 1 비트 개수
6
int lz   = absl::countl_zero(x);    // 24
7
int tz   = absl::countr_zero(x);    // 2
8
int lo1  = absl::countl_one(x);     // 0
9
int tz1  = absl::countr_one(x);     // 0
10
int bw   = absl::bit_width(x);      // 8 — 표현에 필요한 비트 수
11
bool p2  = absl::has_single_bit(x); // false (2의 거듭제곱이 아님)

#표 — 함수 카탈로그

함수	의미	입력 0일 때
`popcount(x)`	1 비트 개수	0
`countl_zero(x)`	왼쪽(MSB) 0 개수	N (모두 0)
`countr_zero(x)`	오른쪽(LSB) 0 개수	N
`countl_one(x)`	왼쪽 1 개수	0
`countr_one(x)`	오른쪽 1 개수	0
`bit_width(x)`	비트 폭 (최상위 1의 위치 + 1)	0
`bit_ceil(x)`	x 이상 최소 2의 거듭제곱	1
`bit_floor(x)`	x 이하 최대 2의 거듭제곱	0
`has_single_bit(x)`	x가 2의 거듭제곱?	false
`rotl(x, s)`	왼쪽 비트 회전	0
`rotr(x, s)`	오른쪽 비트 회전	0

타입은 unsigned integer 한정(uint8_t/uint16_t/uint32_t/uint64_t). signed 입력은 컴파일 에러.

#실제 어디 쓰이나

#SwissTable의 SIMD 메타데이터

absl::flat_hash_map의 group 검색은 16바이트 메타에서 매칭 비트마스크를 만들고 countr_zero로 슬롯 인덱스를 뽑는다.

1
// 의사 코드 — 실제는 SIMD intrinsic
2
uint16_t mask = MatchFingerprint(group, fingerprint);
3
while (mask) {
4
    int idx = absl::countr_zero(mask);
5
    if (slots[idx].key == key) return slots[idx].value;
6
    mask &= mask - 1;   // 가장 낮은 1 비트 끄기
7
}

#가변 길이 정수 인코딩

1
int BytesNeeded(uint64_t x) {
2
    if (x == 0) return 1;
3
    int bits = absl::bit_width(x);
4
    return (bits + 6) / 7;   // 7비트씩 묶기 (varint)
5
}

#해시맵 capacity 계산

1
size_t NextPowerOfTwo(size_t n) {
2
    return absl::bit_ceil(n);
3
}
4

5
size_t IndexMask(size_t capacity) {
6
    // capacity는 2의 거듭제곱
7
    return capacity - 1;
8
}

#컴파일러 매핑

함수	x86 BMI/POPCNT	ARM
`popcount`	`popcnt`	`cnt`
`countl_zero`	`lzcnt`	`clz`
`countr_zero`	`tzcnt` / `bsf`	`rbit + clz`

Abseil은 하드웨어 instruction이 있으면 그것을, 없으면 portable bit-twiddle로 fallback. 인라인 호출이 단일 instruction으로 컴파일되는 게 보통이다.

#회피 패턴

1
// 회피 — manual loop
2
int Popcount(uint32_t x) {
3
    int c = 0;
4
    while (x) { c += x & 1; x >>= 1; }
5
    return c;
6
}
7

8
// Good — hardware popcnt
9
int c = absl::popcount(x);

1
// 회피 — branch로 가장 높은 비트 찾기
2
int Log2(uint32_t x) {
3
    int r = 0;
4
    while (x >>= 1) ++r;
5
    return r;
6
}
7

8
// Good
9
int r = absl::bit_width(x) - 1;   // x == 0이면 -1, 호출 전 검사

1
// 회피 — 2의 거듭제곱 검사
2
bool IsPow2(uint32_t x) { return x && !(x & (x - 1)); }
3

4
// Good
5
bool p = absl::has_single_bit(x);

#C++20 마이그레이션

Abseil 함수들은 std:: 짝과 1

시그니처 호환이다. 컴파일러를 C++20으로 올렸다면 다음과 같이 치환 가능.

1
// before
2
#include "absl/numeric/bits.h"
3
int c = absl::popcount(x);
4

5
// after
6
#include <bit>
7
int c = std::popcount(x);

namespace absl = std; 같은 alias는 안 되지만 using std::popcount; 정도면 단일 함수 단위 마이그레이션이 가능하다.

#작은 예시 — Bit Set 순회

1
// uint64 비트마스크의 set 비트 인덱스를 모두 순회
2
void ForEachSet(uint64_t mask, std::function<void(int)> f) {
3
    while (mask) {
4
        int idx = absl::countr_zero(mask);
5
        f(idx);
6
        mask &= mask - 1;   // lowest set bit clear
7
    }
8
}
9

10
ForEachSet(0b10101100, [](int i) { std::cout << i << "\n"; });
11
// 2, 3, 5, 7