해밍 가중치

**해밍 가중치** 또는 **해밍 웨이트**(Hamming weight)는 사용되는 알파벳의 0 기호와 다른 기호의 개수이다. 따라서 동일한 길이의 모든 0 문자열에서 해밍 거리와 같다. 가장 일반적인 경우인 주어진 비트 집합의 경우, 이는 1로 설정된 비트의 수, 또는 주어진 숫자의 이진 표현의 디지털 합계 및 비트 벡터의 ℓ₁ 노름이다. 이 이진 사례에서는 **개체수 개수**, **팝카운트**, **측면 합계**, 또는 **비트 합산**이라고도 불린다. {|class="wikitable" align="right" |+예시 !문자열 !해밍 가중치 |- |**111**0**1** |4 |- |**111**0**1**000 |4 |- |00000000 |0 |- |**678**0**1234**0**567** |10 |} access-date=June 2, 2024
# 역사 및 사용법
해밍 가중치는 미국의 수학자 리처드 해밍의 이름을 따서 명명되었지만, 그가 이 개념을 고안한 것은 아니다. 이진 숫자의 해밍 가중치는 이미 1899년에 제임스 W. L. 글래셔가 파스칼의 삼각형의 한 행에 있는 홀수 이항 계수의 개수에 대한 공식을 제시하기 위해 사용했다. 어빙 S. 리드는 1954년에 이진 사례에서 해밍 가중치와 동일한 개념을 도입했다. 해밍 가중치는 정보 이론, 부호 이론, 암호학을 포함한 여러 분야에서 사용된다. 해밍 가중치 적용의 예는 다음과 같다. * 모듈러 제곱을 통한 지수 연산에서, 지수 e에 필요한 모듈러 곱셈의 수는 log2 e + weight(e)이다. 이것이 RSA에 사용되는 공개 키 값 e가 일반적으로 낮은 해밍 가중치를 가진 숫자로 선택되는 이유이다. * 해밍 가중치는 코드 분산 해시 테이블의 노드 간 경로 길이를 결정한다. * 생체 인식 데이터베이스의 아이리스 코드 조회는 일반적으로 저장된 각 기록에 대한 해밍 거리를 계산하여 구현된다.bibcode = 2010ITIP...19..522K * 비트보드 표현을 사용하는 컴퓨터 체스 프로그램에서, 비트보드의 해밍 가중치는 게임에 남아있는 특정 유형의 말 수 또는 한 플레이어의 말에 의해 제어되는 보드 칸 수를 나타내며, 따라서 위치 값에 중요한 기여를 한다.volume = 20 Updated and reprinted in Scalable Search in Computer Chess (Vieweg+Teubner Verlag, 2000), pp. 185–198, 10.1007/978-3-322-90178-1_13 * 해밍 가중치는 ffs(x) = pop(x ^ (x - 1))라는 항등식을 사용하여 최하위 비트 찾기를 효율적으로 계산하는 데 사용될 수 있다. 이는 하드웨어 해밍 가중치 명령은 있지만 하드웨어 최하위 비트 찾기 명령은 없는 SPARC와 같은 플랫폼에서 유용하다. * 해밍 가중치 연산은 일진법에서 이진법으로의 변환으로 해석될 수 있다.
# 효율적인 구현
비트 배열의 개체수 개수는 암호화 및 기타 응용 부문에서 종종 필요하다. 두 단어 A와 B의 해밍 거리는 A XOR B의 해밍 가중치로 계산할 수 있다. 이를 효율적으로 구현하는 방법에 대한 문제는 널리 연구되어 왔다. 계산을 위한 단일 연산 또는 비트 벡터에 대한 병렬 연산이 일부 프로세서에서 사용 가능하다. 이러한 기능이 없는 프로세서의 경우, 알려진 최상의 솔루션은 트리 패턴으로 개수를 추가하는 것을 기반으로 한다. 예를 들어, 16비트 이진수 a = 0110 1100 1011 1010에서 1비트의 개수를 세기 위해 다음 연산을 수행할 수 있다. {| class="wikitable" | 이진 ! 십진 ! 주석 |- | | `a` | 01 | 10 | 11 | 00 | 10 | 11 | 10 | 10 | | | 원본 숫자 |- | | `b0 = (a >> 0) & 01 01 01 01 01 01 01 01` | 01 | 00 | 01 | 00 | 00 | 01 | 00 | 00 | | 1, 0, 1, 0, 0, 1, 0, 0 | | a에서 격비트 |- | | `b1 = (a >> 1) & 01 01 01 01 01 01 01 01` | 00 | 01 | 01 | 00 | 01 | 01 | 01 | 01 | | 0, 1, 1, 0, 1, 1, 1, 1 | | a에서 나머지 비트 |- | | `c = b0 + b1` | 01 | 01 | 10 | 00 | 01 | 10 | 01 | 01 | | 1, 1, 2, 0, 1, 2, 1, 1 | | a의 각 2비트 슬라이스에서 1의 개수 |- | | `d0 = (c >> 0) & 0011 0011 0011 0011` | colspan=2 | 0001 | colspan=2 | 0000 | colspan=2 | 0010 | colspan=2 | 0001 | | 1, 0, 2, 1 | | c에서 격수 |- | | `d2 = (c >> 2) & 0011 0011 0011 0011` | colspan=2 | 0001 | colspan=2 | 0010 | colspan=2 | 0001 | colspan=2 | 0001 | | 1, 2, 1, 1 | | c에서 나머지 개수 |- | | `e = d0 + d2` | colspan=2 | 0010 | colspan=2 | 0010 | colspan=2 | 0011 | colspan=2 | 0010 | | 2, 2, 3, 2 | | a의 각 4비트 슬라이스에서 1의 개수 |- | | `f0 = (e >> 0) & 00001111 00001111` | colspan=4 | 00000010 | colspan=4 | 00000010 | | 2, 2 | | e에서 격수 |- | | `f4 = (e >> 4) & 00001111 00001111` | colspan=4 | 00000010 | colspan=4 | 00000011 | | 2, 3 | | e에서 나머지 개수 |- | | `g = f0 + f4` | colspan=4 | 00000100 | colspan=4 | 00000101 | | 4, 5 | | a의 각 8비트 슬라이스에서 1의 개수 |- | | `h0 = (g >> 0) & 0000000011111111` | colspan=8 | 0000000000000101 | | 5 | | g에서 격수 |- | | `h8 = (g >> 8) & 0000000011111111` | colspan=8 | 0000000000000100 | | 4 | | g에서 나머지 개수 |- | | `i = h0 + h8` | colspan=8 | 0000000000001001 | | 9 | | 전체 16비트 워드에서 1의 개수 |} 여기서 연산은 C 프로그래밍 언어와 같으므로, X >> Y는 X를 Y비트만큼 오른쪽으로 시프트하는 것을 의미하고, X & Y는 X와 Y의 비트 AND를 의미하며, +는 일반적인 덧셈이다. 이 문제에 대해 알려진 최상의 알고리즘은 위에 설명된 개념을 기반으로 하며 다음과 같다. //아래 함수에서 사용되는 타입과 상수 //uint64_t는 부호 없는 64비트 정수 변수 타입 (C 언어 C99 버전에서 정의됨) const uint64_t m1 = 0x5555555555555555; //이진: 0101... const uint64_t m2 = 0x3333333333333333; //이진: 00110011.. const uint64_t m4 = 0x0f0f0f0f0f0f0f0f; //이진: 4개의 0, 4개의 1 ... const uint64_t m8 = 0x00ff00ff00ff00ff; //이진: 8개의 0, 8개의 1 ... const uint64_t m16 = 0x0000ffff0000ffff; //이진: 16개의 0, 16개의 1 ... const uint64_t m32 = 0x00000000ffffffff; //이진: 32개의 0, 32개의 1 const uint64_t h01 = 0x0101010101010101; //0,1,2,3...의 256의 거듭제곱의 합 //이것은 비교를 위해 보여지는 순진한 구현이며, //더 나은 함수를 이해하는 데 도움이 된다. //이 알고리즘은 24개의 산술 연산(시프트, 더하기, AND)을 사용한다. int popcount64a(uint64_t x) { x = (x & m1 ) + ((x >> 1) & m1 ); //각 2비트의 개수를 해당 2비트에 넣는다. x = (x & m2 ) + ((x >> 2) & m2 ); //각 4비트의 개수를 해당 4비트에 넣는다. x = (x & m4 ) + ((x >> 4) & m4 ); //각 8비트의 개수를 해당 8비트에 넣는다. x = (x & m8 ) + ((x >> 8) & m8 ); //각 16비트의 개수를 해당 16비트에 넣는다. x = (x & m16) + ((x >> 16) & m16); //각 32비트의 개수를 해당 32비트에 넣는다. x = (x & m32) + ((x >> 32) & m32); //각 64비트의 개수를 해당 64비트에 넣는다. return x; } //느린 곱셈이 있는 기계에서 알려진 다른 구현보다 적은 산술 연산을 사용한다. //이 알고리즘은 17개의 산술 연산을 사용한다. int popcount64b(uint64_t x) { x -= (x >> 1) & m1; //각 2비트의 개수를 해당 2비트에 넣는다. x = (x & m2) + ((x >> 2) & m2); //각 4비트의 개수를 해당 4비트에 넣는다. x = (x + (x >> 4)) & m4; //각 8비트의 개수를 해당 8비트에 넣는다. x += x >> 8; //각 16비트의 개수를 최하위 8비트에 넣는다. x += x >> 16; //각 32비트의 개수를 최하위 8비트에 넣는다. x += x >> 32; //각 64비트의 개수를 최하위 8비트에 넣는다. return x & 0x7f; } //빠른 곱셈이 있는 기계에서 알려진 다른 구현보다 적은 산술 연산을 사용한다. //이 알고리즘은 12개의 산술 연산을 사용하며, 그 중 하나는 곱셈이다. int popcount64c(uint64_t x) { x -= (x >> 1) & m1; //각 2비트의 개수를 해당 2비트에 넣는다. x = (x & m2) + ((x >> 2) & m2); //각 4비트의 개수를 해당 4비트에 넣는다. x = (x + (x >> 4)) & m4; //각 8비트의 개수를 해당 8비트에 넣는다. return (x * h01) >> 56; //x + (x> 16]; } //선택적으로, wordbits[] 테이블은 다음 함수를 사용하여 채워질 수 있다. int popcount32e_init(void) { uint32_t i; uint16_t x; int count; for (i=0; i i; ++i) wordbits [i] = wordbits [i >> 1] + (1 & i); } 뮬라(Muła) 외는 popcount64b의 벡터화 버전이 전용 명령어(예: x64 프로세서의 popcnt)보다 빠르게 실행될 수 있음을 보여주었다. 할리-실(Harley–Seal) 알고리즘url=https://github.com/WojciechMula/sse-popcount/blob/master/popcnt-harley-seal.cpp은 정수 연산만 필요로 하면서도 가장 빠른 알고리즘 중 하나이다.arxiv=1611.07612
# 최소 가중치
오류 정정 부호에서 코드의 최소 해밍 가중치(일반적으로 코드의 **최소 가중치** wmin이라고 함)는 가장 낮은 가중치를 가진 비영 코드 워드의 가중치이다. 코드 워드의 가중치 w는 워드에 있는 1의 개수이다. 예를 들어, 워드 11001010의 가중치는 4이다. 선형 블록 코드에서 최소 가중치는 최소 해밍 거리 (dmin)이기도 하며 코드의 오류 수정 능력을 정의한다. 만약 wmin = n이면, dmin = n이고 코드는 최대 dmin/2개의 오류를 수정한다.Stern & Mahmoud, Communications System Design, Prentice Hall, 2004, p 477ff.
# 언어 지원
일부 C 컴파일러는 비트 개수 기능을 제공하는 내장 함수를 제공한다. 예를 들어, GCC (2004년 4월 버전 3.4부터)는 사용 가능한 경우 프로세서 명령어를 사용하거나 그렇지 않은 경우 효율적인 라이브러리 구현을 사용하는 내장 함수 `__builtin_popcount`를 포함한다. LLVM-GCC는 2005년 6월 버전 1.5부터 이 함수를 포함했다. C++ 표준 라이브러리에서 비트 배열 데이터 구조인 `bitset`은 설정된 비트 수를 세는 `count()` 메서드를 가지고 있다. C++20에서는 새로운 헤더 ``가 추가되었으며, 부호 없는 정수형 인수를 받는 함수 `std::popcount`와 `std::has_single_bit`를 포함한다. 자바에서는 확장 가능한 비트 배열 데이터 구조인 BitSet에 설정된 비트 수를 세는 cardinality() 메서드가 있다. 또한, 기본 32비트 및 64비트 정수의 비트 수를 세는 bitCount(int) 및 bitCount(long) 함수가 있다. 또한, BigInteger 임의 정밀도 정수 클래스에도 비트 수를 세는 bitCount() 메서드가 있다. 파이썬에서 `int` 타입은 설정된 비트 수를 세는 `bit_count()` 메서드를 가지고 있다. 이 기능은 2021년 10월에 출시된 파이썬 3.10에서 도입되었다.website=python.org 커먼 리스프에서 함수 `logcount`는 음수가 아닌 정수가 주어지면 1비트의 수를 반환한다. (음의 정수의 경우 2의 보수 표기법에서 0비트의 수를 반환한다.) 두 경우 모두 정수는 BIGNUM일 수 있다. GHC 7.4부터 하스켈 기본 패키지에는 `Bits` 클래스의 인스턴스인 모든 타입에 대해 사용 가능한 `popCount` 함수가 있다. (`Data.Bits` 모듈에서 사용 가능) SQL 언어의 MySQL 버전은 `BIT_COUNT()`를 표준 함수로 제공한다. 포트란 2008은 정수(또는 정수 배열) 내의 0이 아닌 비트 수를 반환하는 표준, 내장, 요소 함수 `popcnt`를 가지고 있다. 일부 프로그래밍 가능한 과학용 포켓 계산기에는 설정된 비트 수를 계산하는 특별한 명령이 있다. 예를 들어, HP-16C에는 `#B`가 있다. 프리 파스칼은 버전 3.0부터 popcnt를 구현한다.
# 프로세서 지원
* 1960년대의 IBM STRETCH 컴퓨터는 모든 논리 연산의 부산물로 설정된 비트 수와 선행 0의 개수를 계산했다. * 크레이 슈퍼컴퓨터는 일찍이 개체수 개수 기계어 명령어를 특징으로 했는데, 이는 암호 해독 애플리케이션을 위해 미국 정부 미국 국가안보국이 특별히 요청했다는 소문이 있다. * Control Data Corporation (CDC)의 6000 및 Cyber 70/170 시리즈 머신에는 개체수 개수 명령이 포함되어 있었다. COMPASS에서 이 명령은 `CXi`로 코딩되었다. * 64비트 SPARC 버전 9 아키텍처는 `POPC` 명령을 정의하지만, 대부분의 구현은 이를 구현하지 않아 운영 체제에 의한 에뮬레이션이 필요하다. * 도널드 커누스의 모델 컴퓨터 MMIX는 1999년부터 `SADD` 명령을 가지고 있다. `SADD a,b,c`는 b에서 1이고 c에서 0인 모든 비트를 세고 그 결과를 a에 쓴다. * 컴팩의 Alpha 21264A는 1999년에 출시되었으며, 카운트 확장(`CIX`)을 가진 최초의 Alpha 시리즈 CPU 설계였다. * 아날로그 디바이스의 블랙핀 프로세서는 32비트 개체수 개수를 수행하는 `ONES` 명령을 특징으로 한다. * AMD의 바르셀로나 아키텍처는 2007년에 SSE4a 확장 기능의 일부로 `POPCNT` 명령어를 도입하는 고급 비트 조작(ABM) ISA를 도입했다. * 인텔 코어 프로세서는 SSE4.2 명령어 집합 확장을 통해 `POPCNT` 명령어를 도입했으며, 2008년 11월에 출시된 네할렘 기반 코어 i7 프로세서에서 처음 사용 가능했다. * ARM 아키텍처는 Advanced SIMD (NEON) 확장의 일부로 `VCNT` 명령어를 도입했다. * RISC-V 아키텍처는 비트 조작(B) 확장의 일부로 `CPOP` 명령어를 도입했다.
# 더 읽어보기
* type=report (Item 169: PDP/6-10용 개체수 개수 어셈블리 코드.)