비트벡터 랭크·셀렉트 계산기
비트열을 넣으면 O(1) rank/select를 만드는 Jacobson의 블록·서브블록 분해 구조를 단계별로 보여주고, 특정 위치까지의 1 개수(rank)와 k번째 1의 위치(select)를 계산합니다.
0과 1로만 구성합니다
블록 크기의 배수
비트열 (전체 20비트)
10110010110100101101
전체 1의 개수
11개
rank(pos) — pos 이전까지 1의 개수
select(k) — k번째 1의 위치
사용 방법
- 1비트열(0과 1로만 구성)을 입력합니다.
- 2블록 크기·슈퍼블록 크기(슈퍼블록은 블록 크기의 배수)를 정합니다.
- 3rank(특정 위치까지의 1 개수)와 select(k번째 1의 위치)를 조회합니다.
자주 묻는 질문
rank(i)는 비트열의 앞에서부터 위치 i 직전까지 1이 몇 개 있는지를 세는 질의이고, select(k)는 k번째(1부터 세어) 1이 어느 위치에 있는지를 찾는 질의입니다. 처음부터 순진하게 세면 각각 O(n)이 걸립니다.
Guy Jacobson(1989)의 방법은 비트열을 큰 덩어리(슈퍼블록)로 나눠 그 앞까지의 절대 1 개수를 저장하고, 슈퍼블록 안을 다시 작은 덩어리(블록)로 나눠 슈퍼블록 시작부터의 상대 개수를 저장합니다. rank(i)는 슈퍼블록 표 조회 + 블록 표 조회 + 마지막 블록 안에서 직접 세기(기계어 한 단어 안이라 상수시간)로 계산됩니다.
rank(i)가 i에 대해 단조증가한다는 성질을 이용해 이분탐색으로 계산합니다. "rank(pos+1)이 k 이상이 되는 가장 작은 pos"가 바로 k번째 1의 위치입니다.
웨이블릿 트리·FM-인덱스(문자열 검색)·succinct 트리 등 다양한 압축 자료구조의 기반 연산입니다. 웨이블릿 트리 계산기는 이해를 돕기 위해 rank를 단순 선형탐색으로 계산하는데, 이 계산기는 그 rank 자체를 O(1)로 만드는 방법을 다룹니다.
전송되지 않습니다. 계산은 모두 브라우저 안에서 이루어지고 넣은 값은 이 기기에만 남습니다.
알아두면 좋은 점
- Guy Jacobson, "Space-efficient Static Trees and Graphs"(1989)가 succinct 자료구조 표준 문헌에서 인용되는 원 기법입니다(2026-09-05 확인). 이 계산기는 블록 안 popcount를 자바스크립트 반복문으로 직접 세지만, 표 조회 두 번 + 작은 블록 안 세기라는 구조 자체는 원 기법을 그대로 따릅니다.
- 무작위로 생성한 비트열과 여러 블록·슈퍼블록 크기 조합에서, rank·select 결과가 처음부터 순진하게 세는 O(n) 구현과 항상 일치하는지 테스트로 고정했습니다(차등 테스트).
- 실제 하드웨어의 popcount 명령어를 이 계산기가 흉내 내지는 않으므로, 여기 나오는 성능은 개념 설명용이며 실측 성능이 아닙니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 5일 · 결과는 참고용 추정치입니다.