해밍 중량

Hamming weight

문자열의 해밍 가중치는 사용된 알파벳의 0 기호와 다른 기호 수입니다.따라서 길이가 같은 모두 0인 문자열로부터의 해밍 거리와 동일합니다.가장 일반적인 경우, 비트 문자열의 경우, 이것은 문자열 내의 1의 수 또는 특정 숫자의 이진 표현과 비트 벡터의 "" 노름의 자리수입니다.이 바이너리에서는 모집단 카운트,[1] 팝 카운트, 측면 [2]합계 또는 비트 [3]합계라고도 합니다.

예
스트링 해밍 중량
11101 4
11101000 4
00000000 0
678012340567 10
(소수) 숫자 0 ~ 256에 [4][5][6]대한 모집단 카운트(이진수의 경우 가중치 해밍)에 대한 그림입니다.

이력 및 사용방법

해밍 무게의 이름은 리처드 해밍의 이름을 따서 지어졌습니다. 비록 그가 [7]그 개념을 고안한 것은 아니지만요.이진수의 해밍 가중치는 1899년 제임스 글라이셔에 의해 파스칼 [8]삼각형의 한 줄에 있는 홀수 이항 계수의 수에 대한 공식을 제공하기 위해 이미 사용되었습니다.어빙 S. 리드는 1954년 [9]바이너리 케이스의 해밍 무게와 동등한 개념을 도입했다.

해밍 웨이트는 정보 이론, 부호화 이론 및 암호학을 포함한 여러 분야에서 사용됩니다.해밍 중량의 적용 예는 다음과 같습니다.

  • 제곱에 의한 모듈러형 지수화에서는 지수 e에 필요한 모듈러 곱셈의 수는2 log e + weight(e)이다.이것이 RSA에서 사용되는 공개키 값 e가 일반적으로 낮은 Hamming 무게의 수로 선택되는 이유입니다.
  • Hamming 가중치는 Chord 분산 해시 [10]테이블의 노드 간 경로 길이를 결정합니다.
  • 바이오메트릭 데이터베이스의 IrisCode 조회는 일반적으로 저장된 각 레코드까지의 해밍 거리를 계산하여 구현됩니다.
  • 비트보드 표현을 이용한 컴퓨터 체스 프로그램에서 비트보드의 해밍 웨이트는 게임 내에 남아 있는 소정의 종류의 피스 수 또는 한 플레이어의 피스에 의해 제어되는 보드의 정사각형 수를 주기 때문에 포지션의 가치에 중요한 기여 용어이다.
  • 해밍 가중치는 동일 ffs(x) = pop(x ^ (x - 1)을 사용하여 첫 번째 집합을 효율적으로 계산하는 데 사용할 수 있습니다.이 기능은 하드웨어 해밍 중량 지시가 있지만 하드웨어가 최초 설정 지령을 [11][1]찾지 않은 SPARC 등의 플랫폼에서 유용합니다.
  • Hamming 가중치 연산은 단수법에서 이진수로 [12]변환된 것으로 해석할 수 있습니다.
  • 비트 벡터 및 웨이브릿 트리와 같은 간결한 데이터 구조의 구현.

효율적인 구현

비트 문자열의 인구 수는 암호학 및 기타 응용 프로그램에서 종종 필요합니다.두 단어 A와 B의 해밍 거리는 A x 또는 [1]B의 해밍 무게로 계산할 수 있습니다.

그것을 어떻게 효율적으로 실행할 것인가에 대한 문제는 널리 연구되어 왔다.계산을 위한 단일 연산 또는 비트 벡터에 대한 병렬 연산을 일부 프로세서에서 사용할 수 있습니다.이러한 기능이 없는 프로세서의 경우 트리 패턴의 카운트를 추가하는 것이 최선의 해결책입니다.예를 들어, 16비트 이진수 a = 0110 1100 1011 1010에서 1비트 수를 카운트하려면 다음 작업을 수행할 수 있습니다.

표현 바이너리 십진수 댓글
a 01 10 11 00 10 11 10 10 27834 원래 번호
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 에서 격주로
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 의 나머지 비트
c = b0 + b1 01 01 10 00 01 10 01 01 1, 1, 2, 0, 1, 2, 1, 1 의 각 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 의 각 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 의 각 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는 X와 Y의 비트 단위 AND를 의미하며, +는 일반 덧셈을 의미합니다.이 문제에 대해 가장 잘 알려진 알고리즘은 위에서 설명한 개념에 기초하고 있으며,[1] 다음과 같이 제시되어 있습니다. 

//아래 함수에 사용되는 유형 및 상수 //uint64_t는 부호 없는 64비트 정수 변수 유형입니다(C99 버전의 C 언어로 정의됨). 컨스턴트 uint64_t m1  = 0x5555555555555555; //메시지: 0101... 컨스턴트 uint64_t m2  = 0x3333333333333333; //파일: 00110011.. 컨스턴트 uint64_t m4  = 0x0f0f0f0f0f0f0f0f; //소수: 4개의 0, 4개의 1... 컨스턴트 uint64_t m8  = 0x00ff00ff00ff00ff; //소수: 8개의 0, 8개의 1... 컨스턴트 uint64_t m16 = 0x0000ffff0000ffff; //소수: 16개의 0, 16개의 1... 컨스턴트 uint64_t m32 = 0x00000000ffffffff; //스태프: 32개의 0, 32개의 1 컨스턴트 uint64_t h01 = 0x0101010101010101; //256의 0,1,2,3의 제곱합...  //이것은 비교를 위해 제시된 단순한 구현입니다. //더 나은 기능을 이해하는 데 도움이 됩니다. //이 알고리즘은 24개의 산술 연산(shift, add, and)을 사용합니다. 인트 팝카운트 64a(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비트에 입력     돌아가다 x; }  //다른 알려진 것보다 적은 산술 연산을 사용합니다. //증배 속도가 느린 기계에서의 정보. //이 알고리즘은 17개의 산술 연산을 사용합니다. 인트 팝카운트 64b(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비트로 입력     돌아가다 x & 0x7f; }  //다른 알려진 것보다 적은 산술 연산을 사용합니다. //증배 속도가 빠른 머신에 대한 설명. //이 알고리즘은 12개의 산술 연산을 사용하며, 그 중 하나가 곱셈입니다. 인트 팝카운트 64c(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 * h01) >> 56;  //x+(x<8)+(x<16)+(x<24)+...의 왼쪽 8비트를 표시  }

위의 구현은 알려진 알고리즘 중 가장 최악의 경우 동작을 합니다.단, 값이 0이 아닌 비트를 적게 가질 것으로 예상되는 경우에는 이러한 비트를 한 번에 하나씩 카운트하는 알고리즘을 사용하는 것이 더 효율적일 수 있습니다.Wegner가 1960년에 [13]기술한 바와 같이 x - 1을 가진 x의 비트 단위 AND는 0이 아닌 최하위 비트를 0으로 지우는 데 있어서만 x와 다릅니다.1을 빼면 오른쪽 끝 문자열이 0으로 바뀌고 오른쪽 끝 문자열이 0으로 변경됩니다.x가 원래 1인 n비트를 가진 경우, 이 작업을 n회만 반복하면 x가 0으로 감소합니다.다음의 실장은, 이 원칙에 근거하고 있습니다. 

//x의 대부분의 비트가 0일 때 더 좋습니다. //이 알고리즘은 모든 데이터 크기에 대해 동일하게 작동합니다. //이 알고리즘은 x의 "1" 비트당 3개의 산술 연산과 1개의 비교/분기를 사용합니다. 인트 팝카운트 64d(uint64_t x) {     인트 세어보세요;     위해서 (세어보세요=0; x; 세어보세요++)         x &= x - 1;     돌아가다 세어보세요; }

메모리 사용량이 증가하면 위의 방법보다 더 빨리 Hamming 웨이트를 계산할 수 있습니다.무제한 메모리를 사용하면 64비트 정수마다 Hamming 웨이트의 큰 룩업 테이블을 만들 수 있습니다.16비트 정수마다 해밍 함수의 룩업 테이블을 저장할 수 있다면, 32비트 정수마다 다음과 같이 해밍 가중치를 계산할 수 있습니다. 

정적인 uint8_t 워드비트[65536] = { /* 정수 0 ~65535 비트카운트 (*/ 포함) }; //이 알고리즘은 3개의 산술 연산과 2개의 메모리 읽기를 사용합니다. 인트 팝카운트32e(uint32_t x) {     돌아가다 워드비트[x & 0xFFFF] + 워드비트[x >> 16]; } 
//옵션으로 이 함수를 사용하여 워드비트[] 테이블을 채울 수 있습니다. 인트 popcount32e_init(무효) {     uint32_t i;     uint16_t x;     인트 세어보세요;     위해서 (i=0; i <=> 0xFFFF; i++)     {         x = i;         위해서 (세어보세요=0; x; 세어보세요++) // 위의 popcount64d()에서 빌렸습니다.             x &= x - 1;         워드비트[i] = 세어보세요;     } }

무와 [14]등는 popcount64b의 벡터화 버전이 전용 명령어(예를 들어 x64 프로세서의 popcnt)보다 빠르게 실행된다는 것을 보여 줍니다.

최소 중량

오류 정정 부호화에서 최소 해밍 가중치(일반적으로 코드의 최소 가중치min w라고 함)는 최소 가중치가 0이 아닌 코드 워드의 가중치입니다.코드 워드의 무게 w는 워드의 1s 수입니다.예를 들어, 단어 110010의 무게는 4입니다.

선형 블록 코드에서 최소 가중치는 최소 해밍 거리(dmin)이며 코드의 오류 수정 능력을 정의합니다.wmin = n이면 dmin = n이고 코드는 최대min d/2 [15]오류를 수정합니다.

언어 지원

일부 C 컴파일러는 비트 카운트 기능을 제공하는 고유 함수를 제공합니다.예를 들어 GCC(2004년4월 버전 3.4 이후)에는 내장 기능이 포함되어 있습니다.__builtin_popcount 프로세서 명령어를 사용할 수 있는 경우 또는 효율적인 라이브러리 구현을 사용할 수 없는 경우.[16]LLVM-GCC에는 2005년 [17]6월 버전 1.5부터 이 기능이 포함되어 있습니다.

C++ STL에서는 비트 배열 데이터 구조bitset가 있다count()설정된 비트 수를 카운트하는 메서드입니다.C++20에서는 새로운 헤더<bit>기능이 추가되어 있습니다.std::popcount그리고.std::has_single_bit부호 없는 정수 유형의 인수를 사용합니다.

자바에서는 확장 가능한 비트 어레이 데이터 구조BitSet가 있다BitSet.cardinality()설정된 비트 수를 카운트하는 메서드입니다.또,Integer.bitCount(int)그리고.Long.bitCount(long)기본 32비트 및 64비트 정수로 각각 비트를 카운트하는 함수입니다.또,BigIntegerarbitrary-module 정수 클래스에는BigInteger.bitCount()비트를 카운트하는 메서드.

Python에서는inttype에는 a가 있습니다.bit_count()method를 사용하여 비트 세트 수를 카운트합니다.이 기능은 2021년 [18]10월에 출시된 파이썬 3.10에서 도입되었습니다.

Common Lisp에서 함수는logcount는 음수가 아닌 정수를 지정하면 1비트 수를 반환합니다(음수 정수의 경우 2의 보표기로 0비트 수를 반환합니다).어느 경우든 정수는 BIGNUM이 될 수 있습니다.

GHC 7.4 이후 Haskell 베이스 패키지에는popCount의 인스턴스인 모든 유형에서 사용 가능한 함수Bitsclass(에서 사용 가능)Data.Bits모듈)[19]을 클릭합니다.

MySQL 버전의 SQL 언어는BIT_COUNT()표준 [20]기능으로 사용합니다.

Fortran 2008에는 표준 내장 요소 기능이 탑재되어 있습니다.popcnt정수(또는 정수 배열)[21] 내에서 0이 아닌 비트 수를 반환합니다.

일부 프로그램 가능한 과학 포켓 계산기는 설정 비트 수를 계산하는 특수 명령을 제공합니다.#BHP-16C[3][22] 및 WP [23][24]43S에서는 #BITS[25][26] 또는BITSUM[27][28] HP-16C 에뮬레이터 및nBITSWP 34S에 [29][30]있습니다.

FreePascal은 버전 3.0 [31]이후 popcnt를 구현합니다.

프로세서 지원

  • 1960년대 IBM STRETH 컴퓨터는 모든 논리 [1]연산의 부산물로서 세트 비트 수와 선행 0의 수를 계산했습니다.
  • Cray 슈퍼컴퓨터는 초기에 미국 정부 국가안보국(NSA)이 암호 애플리케이션을 [1]위해 특별히 요청한 것으로 알려진 인구 계수 기계 명령을 특징으로 했습니다.
  • Control Data Corporation (CDC) 6000 및 Cyber 70/170 시리즈 머신에는 인구 카운트 명령이 포함되어 있습니다.COMPASS에서는 이 명령은 다음과 같이 코드화되어 있습니다.CXi.
  • 64비트 SPARC 버전9 아키텍처에서는POPC그러나 대부분의 구현에서는 [11][1]구현되지 않으므로 [32]운영체제에 의해 에뮬레이트되어야 합니다.
  • Donald Knuth의 모델 컴퓨터 MMIX는 그의 책 The Art of Computer Programming에서 MIX를 대체할 것입니다.SADD1999년 이래의 교육. SADD a,b,c는 b에서 1비트, c에서 0비트인 모든 비트를 카운트하고 결과를 a에 씁니다.
  • 1999년에 출시된 Compaq의 Alpha 21264A는 카운트를 확장한 최초의 Alpha 시리즈 CPU 설계입니다.CIX).
  • 아날로그 디바이스의 Blackfin 프로세서는ONES32비트 입력 [33]카운트를 실행하도록 지시합니다.
  • AMD의 바르셀로나 아키텍처는 ABM(Advanced Bit Manipulation) ISA를 도입하여POPCNT2007년 SSE4a 확장의 일부로서 설명.
  • 인텔 Core 프로세서는POPCNT SSE4.2 명령어 세트 확장을 사용한 명령어.Nehalem 기반의 Core i7 프로세서로 2008년 11월에 발매되었습니다.
  • ARM 아키텍처는VCNT어드밴스드 SIMD(NEON) 확장의 일부로서의 명령입니다.
  • RISC-V 아키텍처는PCNTBit Manipulation(B; 비트 조작) [34]확장의 일부로서의 명령입니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b c d e f g Warren Jr., Henry S. (2013) [2002]. Hacker's Delight (2 ed.). Addison Wesley - Pearson Education, Inc. pp. 81–96. ISBN 978-0-321-84268-8. 0-321-84268-5.
  2. ^ Knuth, Donald Ervin (2009). "Bitwise tricks & techniques; Binary Decision Diagrams". The Art of Computer Programming. Vol. 4, Fascicle 1. Addison–Wesley Professional. ISBN 978-0-321-58050-4. (NB. 패시클 1b 초안 다운로드 가능)
  3. ^ a b Hewlett-Packard HP-16C Computer Scientist Owner's Handbook (PDF). Hewlett-Packard Company. April 1982. 00016-90001. Archived (PDF) from the original on 2017-03-28. Retrieved 2017-03-28.
  4. ^ [1], Formulé로 작성.Formulae 위키.2019-09-30 취득.
  5. ^ 모집단 수 작업에 대한 해결책입니다.2019-09-30 취득.
  6. ^ 로제타 코드2019-09-30 취득.
  7. ^ Thompson, Thomas M. (1983). From Error-Correcting Codes through Sphere Packings to Simple Groups. The Carus Mathematical Monographs #21. The Mathematical Association of America. p. 33.
  8. ^ Glaisher, James Whitbread Lee (1899). "On the residue of a binomial-theorem coefficient with respect to a prime modulus". The Quarterly Journal of Pure and Applied Mathematics. 30: 150–156. (NB. 특히 페이지 156의 마지막 단락을 참조한다.)
  9. ^ Reed, Irving Stoy (1954). "A Class of Multiple-Error-Correcting Codes and the Decoding Scheme". IRE Professional Group on Information Theory. Institute of Radio Engineers (IRE). PGIT-4: 38–49.
  10. ^ Stoica, I.; Morris, R.; Liben-Nowell, D.; Karger, D. R.; Kaashoek, M. F.; Dabek, F.; Balakrishnan, H. (February 2003). "Chord: a scalable peer-to-peer lookup protocol for internet applications". IEEE/ACM Transactions on Networking. 11 (1): 17–32. doi:10.1109/TNET.2002.808407. S2CID 221276912. Section 6.3: "In general, the number of fingers we need to follow will be the number of ones in the binary representation of the distance from node to query."
  11. ^ a b SPARC International, Inc. (1992). "A.41: Population Count. Programming Note". The SPARC architecture manual: version 8 (Version 8 ed.). Englewood Cliffs, New Jersey, USA: Prentice Hall. pp. 231. ISBN 0-13-825001-4.
  12. ^ Blaxell, David (1978). Hogben, David; Fife, Dennis W. (eds.). "Record linkage by bit pattern matching". Computer Science and Statistics--Tenth Annual Symposium on the Interface. NBS Special Publication. U.S. Department of Commerce / National Bureau of Standards. 503: 146–156.
  13. ^ Wegner, Peter (May 1960). "A technique for counting ones in a binary computer". Communications of the ACM. 3 (5): 322. doi:10.1145/367236.367286. S2CID 31683715.
  14. ^ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (January 2018). "Faster Population Counts Using AVX2 Instructions". Computer Journal. 61 (1): 111–120. arXiv:1611.07612. doi:10.1093/comjnl/bxx046. S2CID 540973.
  15. ^ Stern & Mahmoud, 커뮤니케이션 시스템 설계, 프렌티스 홀, 2004, 페이지 477ff.
  16. ^ "GCC 3.4 Release Notes". GNU Project.
  17. ^ "LLVM 1.5 Release Notes". LLVM Project.
  18. ^ "What's New In Python 3.10". python.org.
  19. ^ "GHC 7.4.1 release notes". GHC 매뉴얼
  20. ^ "Chapter 12.11. Bit Functions — MySQL 5.0 Reference Manual".
  21. ^ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Explained. Oxford University Press. p. 380. ISBN 978-0-19-960142-4.
  22. ^ Schwartz, Jake; Grevelle, Rick (2003-10-20) [1993]. HP16C Emulator Library for the HP48S/SX. 1.20 (1 ed.). Retrieved 2015-08-15. (NB. 이 라이브러리는 HP 48G/GX/G+에서도 동작합니다.HP-16C의 피처 세트 외에 이 패키지는 일반적인 10진 부동소수점 숫자에 더해 과학적 표기의 바이너리, 8진수 및 16진수 부동소수점 숫자의 계산도 지원합니다).
  23. ^ Bonin, Walter (2019) [2015]. WP 43S Owner's Manual (PDF). 0.12 (draft ed.). p. 135. ISBN 978-1-72950098-9. Retrieved 2019-08-05. [2] [3] (314페이지)
  24. ^ Bonin, Walter (2019) [2015]. WP 43S Reference Manual (PDF). 0.12 (draft ed.). pp. xiii, 104, 115, 120, 188. ISBN 978-1-72950106-1. Retrieved 2019-08-05. [4] [5] (271페이지)
  25. ^ Martin, Ángel M.; McClure, Greg J. (2015-09-05). "HP16C Emulator Module for the HP-41CX - User's Manual and QRG" (PDF). Archived (PDF) from the original on 2017-04-27. Retrieved 2017-04-27. (NB. HP-16C 기능 세트 이외에 이 HP-41CX용 커스텀 라이브러리는 계산기의 기능을 약 50개의 추가 기능으로 확장합니다.)
  26. ^ Martin, Ángel M. (2015-09-07). "HP-41: New HP-16C Emulator available". Archived from the original on 2017-04-27. Retrieved 2017-04-27.
  27. ^ Thörngren, Håkan (2017-01-10). "Ladybug Documentation" (release 0A ed.). Retrieved 2017-01-29. [6]
  28. ^ "New HP-41 module available: Ladybug". 2017-01-10. Archived from the original on 2017-01-29. Retrieved 2017-01-29.
  29. ^ Dale, Paul; Bonin, Walter (2012) [2008]. "WP 34S Owner's Manual" (PDF) (3.1 ed.). Retrieved 2017-04-27.
  30. ^ Bonin, Walter (2015) [2008]. WP 34S Owner's Manual (3.3 ed.). ISBN 978-1-5078-9107-0.
  31. ^ "Free Pascal documentation popcnt". Retrieved 2019-12-07.
  32. ^ "JDK-6378821: bitCount() should use POPC on SPARC processors and AMD+10h". Java bug database. 2006-01-30.
  33. ^ Blackfin Instruction Set Reference (Preliminary ed.). Analog Devices. 2001. pp. 8–24. Part Number 82-000410-14.
  34. ^ Wolf, Claire (2019-03-22). "RISC-V "B" Bit Manipulation Extension for RISC-V, Draft v0.37" (PDF). Github.

추가 정보

외부 링크