해밍 가중치

해밍 가중치 또는 해밍 웨이트(Hamming weight)는 사용되는 알파벳의 0 기호와 다른 기호의 개수이다. 따라서 동일한 길이의 모든 0 문자열에서 해밍 거리와 같다. 가장 일반적인 경우인 주어진 비트 집합의 경우, 이는 1로 설정된 비트의 수, 또는 주어진 숫자의 이진 표현의 디지털 합계 및 비트 벡터의 ℓ₁ 노름이다. 이 이진 사례에서는 개체수 개수, 팝카운트, 측면 합계, 또는 비트 합산이라고도 불린다.

+예시문자열해밍 가중치11101411101000400000000067801234056710

섬네일|right|숫자 0부터 256까지의 해밍 가중치 그래프.

 역사 및 사용법 
해밍 가중치는 미국의 수학자 리처드 해밍의 이름을 따서 명명되었지만, 그가 이 개념을 고안한 것은 아니다. 이진 숫자의 해밍 가중치는 이미 1899년에 제임스 W. L. 글래셔가 파스칼의 삼각형의 한 행에 있는 홀수 이항 계수의 개수에 대한 공식을 제시하기 위해 사용했다. 어빙 S. 리드는 1954년에 이진 사례에서 해밍 가중치와 동일한 개념을 도입했다.

해밍 가중치는 정보 이론, 부호 이론, 암호학을 포함한 여러 분야에서 사용된다. 해밍 가중치 적용의 예는 다음과 같다.
 모듈러 제곱을 통한 지수 연산에서, 지수 e에 필요한 모듈러 곱셈의 수는 log2 e + weight(e)이다. 이것이 RSA에 사용되는 공개 키 값 e가 일반적으로 낮은 해밍 가중치를 가진 숫자로 선택되는 이유이다.
 해밍 가중치는 코드 분산 해시 테이블의 노드 간 경로 길이를 결정한다.
 생체 인식 데이터베이스의 아이리스 코드 조회는 일반적으로 저장된 각 기록에 대한 해밍 거리를 계산하여 구현된다.
 비트보드 표현을 사용하는 컴퓨터 체스 프로그램에서, 비트보드의 해밍 가중치는 게임에 남아있는 특정 유형의 말 수 또는 한 플레이어의 말에 의해 제어되는 보드 칸 수를 나타내며, 따라서 위치 값에 중요한 기여를 한다. Updated and reprinted in Scalable Search in Computer Chess (Vieweg+Teubner Verlag, 2000), pp. 185–198, 
 해밍 가중치는 ffs(x) = pop(x ^ (x - 1))라는 항등식을 사용하여 최하위 비트 찾기를 효율적으로 계산하는 데 사용될 수 있다. 이는 하드웨어 해밍 가중치 명령은 있지만 하드웨어 최하위 비트 찾기 명령은 없는 SPARC와 같은 플랫폼에서 유용하다.
 해밍 가중치 연산은 일진법에서 이진법으로의 변환으로 해석될 수 있다.

 효율적인 구현 
비트 배열의 개체수 개수는 암호화 및 기타 응용 부문에서 종종 필요하다. 두 단어 A와 B의 해밍 거리는 A XOR B의 해밍 가중치로 계산할 수 있다.

이를 효율적으로 구현하는 방법에 대한 문제는 널리 연구되어 왔다. 계산을 위한 단일 연산 또는 비트 벡터에 대한 병렬 연산이 일부 프로세서에서 사용 가능하다. 이러한 기능이 없는 프로세서의 경우, 알려진 최상의 솔루션은 트리 패턴으로 개수를 추가하는 것을 기반으로 한다. 예를 들어, 16비트 이진수 a = 0110 1100 1011 1010에서 1비트의 개수를 세기 위해 다음 연산을 수행할 수 있다.

 표현식 이진 십진 주석 a 01 10 11 00 10 11 10 10 style="text-align:left;"    원본 숫자 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 0001 0000 0010 0001 1, 0, 2, 1 c에서 격수 d2 = (c >> 2) & 0011 0011 0011 0011 0001 0010 0001 0001 1, 2, 1, 1 c에서 나머지 개수 e = d0 + d2 0010 0010 0011 0010 2, 2, 3, 2 a의 각 4비트 슬라이스에서 1의 개수 f0 = (e >> 0) & 00001111  00001111 00000010 00000010 2, 2 e에서 격수 f4 = (e >> 4) & 00001111 00001111 00000010 00000011 2, 3 e에서 나머지 개수 g = f0 + f4 00000100 00000101 4, 5 a의 각 8비트 슬라이스에서 1의 개수 h0 = (g >> 0) & 0000000011111111 0000000000000101 5 g에서 격수 h8 = (g >> 8) & 0000000011111111 0000000000000100 4 g에서 나머지 개수 i = h0 + h8 0000000000001001 9 전체 16비트 워드에서 1의 개수

여기서 연산은 C 프로그래밍 언어와 같으므로, 는 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<<8) + (x<<16) + (x<<24) + ...의 왼쪽 8비트를 반환한다.
}

위의 구현은 알려진 모든 알고리즘 중에서 최악의 경우에 가장 좋은 성능을 보인다. 그러나 값이 0이 아닌 비트가 거의 없을 것으로 예상되는 경우, 한 번에 하나씩 비트를 세는 알고리즘을 사용하는 것이 더 효율적일 수 있다. 웨그너(Wegner)가 1960년에 설명했듯이, x와 x-1의 비트 AND는 최하위 0이 아닌 비트를 0으로 만드는 것에서만 x와 다르다. 1을 빼면 가장 오른쪽의 0 문자열은 1로 바뀌고, 가장 오른쪽의 1은 0으로 바뀐다. 만약 x가 원래 n개의 1비트를 가졌다면, 이 연산을 n번만 반복하면 x는 0이 될 것이다. 다음 구현은 이 원리에 기반한다.

//x에 0이 많은 경우 더 좋다.
//이 알고리즘은 모든 데이터 크기에 대해 동일하게 작동한다.
//이 알고리즘은 x의 "1" 비트당 3개의 산술 연산과 1개의 비교/분기를 사용한다.
int popcount64d(uint64_t x)
{
    int count;
    for (count=0; x; count++)
        x &= x - 1;
    return count;
}

여기서 흥미로운 점은 팝카운트, FFS 및 CLZ 간의 밀접한 관계이다.

더 많은 메모리 사용이 허용된다면, 위 방법보다 해밍 가중치를 더 빠르게 계산할 수 있다. 무제한 메모리로는 모든 64비트 정수의 해밍 가중치를 저장하는 큰 조회 테이블을 만들 수 있다. 모든 16비트 정수의 해밍 함수 조회 테이블을 저장할 수 있다면, 모든 32비트 정수의 해밍 가중치를 계산하기 위해 다음을 수행할 수 있다.
static uint8_t wordbits[65536] = { /* 0부터 65535까지의 정수에 대한 비트 개수 (포함) */ };
//이 알고리즘은 3개의 산술 연산과 2개의 메모리 읽기를 사용한다.
int popcount32e(uint32_t x)
{
    return wordbits[x & 0xFFFF] + wordbits[x >> 16];
}

//선택적으로, wordbits[] 테이블은 다음 함수를 사용하여 채워질 수 있다.
int popcount32e_init(void)
{
    uint32_t i;
    uint16_t x;
    int count;
    for (i=0; i <= 0xFFFF; i++)
    {
        x = i;
        for (count=0; x; count++) // 위의 popcount64d()에서 가져옴
            x &= x - 1;
        wordbits[i] = count;
    }
}

재귀적 알고리즘은 도노번(Donovan)과 커니핸(Kernighan)에 의해 제시되었다.
/* i의 무게는 i / 2의 무게와
i의 최하위 비트에서만 다를 수 있다. */
int popcount32e_init (void)
{
    int i;
    for (i = 1; sizeof wordbits / sizeof *wordbits > i; ++i)
        wordbits [i] = wordbits [i >> 1] + (1 & i);
}

뮬라(Muła) 외는 popcount64b의 벡터화 버전이 전용 명령어(예: x64 프로세서의 popcnt)보다 빠르게 실행될 수 있음을 보여주었다.

할리-실(Harley–Seal) 알고리즘은 정수 연산만 필요로 하면서도 가장 빠른 알고리즘 중 하나이다.

 최소 가중치 
오류 정정 부호에서 코드의 최소 해밍 가중치(일반적으로 코드의 최소 가중치 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에서는 새로운 헤더 <bit>가 추가되었으며, 부호 없는 정수형 인수를 받는 함수 std::popcount와 std::has_single_bit를 포함한다.

자바에서는 확장 가능한 비트 배열 데이터 구조인 에 설정된 비트 수를 세는  메서드가 있다. 또한, 기본 32비트 및 64비트 정수의 비트 수를 세는  및  함수가 있다. 또한,  임의 정밀도 정수 클래스에도 비트 수를 세는  메서드가 있다.

파이썬에서 int 타입은 설정된 비트 수를 세는 bit_count() 메서드를 가지고 있다. 이 기능은 2021년 10월에 출시된 파이썬 3.10에서 도입되었다.

커먼 리스프에서 함수 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 명령어를 도입했다.

 같이 보기 
 2의 보수
 팬아웃

 각주 

 더 읽어보기 
  (Item 169: PDP/6-10용 개체수 개수 어셈블리 코드.)

 외부 링크 
 종합 마법 알고리즘. 최적화된 개체수 개수 및 기타 알고리즘이 샘플 코드와 함께 설명되어 있다.
 비트 트위들링 핵 설정된 비트를 세는 코드와 함께 여러 알고리즘이 제공된다.
 Necessary and Sufficient  - Damien Wintour - 다양한 해밍 가중치 구현을 위한 C# 코드가 있다.
 32비트 정수에서 설정된 비트 수를 세는 가장 좋은 알고리즘은 무엇인가? - Stackoverflow

분류:부호 이론