Hamming ağırlığı - Hamming weight

Hamming ağırlığı bir dizi sıfır sembolünden farklı olan sembollerin sayısıdır alfabe Kullanılmış. Bu nedenle eşdeğerdir Hamming mesafesi aynı uzunluktaki tümü sıfır dizesinden. En tipik durum için, bir dizi bitler, bu dizedeki 1'lerin sayısıdır veya rakam toplamı of ikili gösterim belirli bir sayı ve ℓ₁ norm biraz vektör. Bu ikili durumda, aynı zamanda nüfus sayımı,[1] popcount, yan toplam,[2] veya bit toplamı.[3]

Örnekler
DizeHamming ağırlığı
111014
111010004
000000000
67801234056710
0-256 arası (ondalık) sayılar için nüfus sayımı için bir grafik (ikili sayılar için Hamming ağırlığı).[4][5][6]

Tarih ve kullanım

Hamming ağırlığının adı Richard Hamming bu fikri o yaratmamış olsa da.[7] İkili sayıların Hamming ağırlığı 1899'da James W. L. Glaisher için bir formül vermek tek terimli katsayıların sayısı tek sıra halinde Pascal üçgeni.[8] Irving S. Reed 1954'te ikili durumdaki Hamming ağırlığına eşdeğer bir konsept tanıttı.[9]

Hamming ağırlığı dahil olmak üzere birçok disiplinde kullanılmaktadır. bilgi teorisi, kodlama teorisi, ve kriptografi. Hamming ağırlığının uygulama örnekleri şunları içerir:

  • Modüler olarak kareye göre üs alma, bir üs için gereken modüler çarpımların sayısı e günlük2 e + ağırlık (e). Bu, genel anahtar değerinin e kullanılan RSA tipik olarak bir dizi düşük Hamming ağırlığı olarak seçilir.
  • Hamming ağırlığı, içindeki düğümler arasındaki yol uzunluklarını belirler. Akor dağıtılmış hash tabloları.[10]
  • IrisCode Biyometrik veri tabanlarındaki aramalar, tipik olarak hesaplanarak uygulanır. Hamming mesafesi saklanan her kayda.
  • İçinde bilgisayar satrancı kullanan programlar bitboard gösterimi, bir bitboardun Hamming ağırlığı, oyunda kalan belirli bir türdeki taşların sayısını veya bir oyuncunun taşları tarafından kontrol edilen tahta karelerinin sayısını verir ve bu nedenle, bir pozisyonun değerine katkıda bulunan önemli bir terimdir.
  • Hamming ağırlığı verimli bir şekilde hesaplamak için kullanılabilir ilk seti bul ffs (x) = pop (x ^ (x-1)) kimliğini kullanarak. Bu, aşağıdaki gibi platformlarda kullanışlıdır: SPARC Donanımsal Hamming ağırlık talimatları olan ancak hiçbir donanımı olmayanlar ilk set talimatını bulamaz.[11][1]
  • Hamming ağırlık operasyonu, bir dönüşüm olarak yorumlanabilir. tekli sayı sistemi -e ikili sayılar.[12]
  • Bazılarının uygulanmasında kısa ve öz veri yapıları sevmek bit vektörler ve dalgacık ağaçları.

Etkili uygulama

Bir nüfus sayımı bit dizisi genellikle kriptografide ve diğer uygulamalarda gereklidir. Hamming mesafesi iki kelimenin Bir ve B Hamming ağırlığı olarak hesaplanabilir Bir Xor B.[1]

Etkili bir şekilde nasıl uygulanacağı sorunu geniş çapta incelenmiştir. Hesaplama için tek bir işlem veya bit vektörlerindeki paralel işlemler bazı işlemcilerde mevcuttur. Bu özelliklere sahip olmayan işlemciler için bilinen en iyi çözümler bir ağaç modeline sayıları eklemeye dayanır. Örneğin, 16 bitlik ikili sayıdaki 1 bit sayısını saymak için a = 0110 1100 1011 1010, şu işlemler yapılabilir:

İfadeİkiliOndalıkYorum Yap
a011011001011101027834Orijinal numara
b0 = (a >> 0) & 01 01 01 01 01 01 01 0101000100000100001, 0, 1, 0, 0, 1, 0, 0Her biri bir
b1 = (a >> 1) & 01 01 01 01 01 01 01 0100010100010101010, 1, 1, 0, 1, 1, 1, 1A'dan kalan bitler
c = b0 + b101011000011001011, 1, 2, 0, 1, 2, 1, 1A'nın her 2 bitlik diliminde 1'lerin sayısı
d0 = (c >> 0) & 0011 0011 0011 001100010000001000011, 0, 2, 1Her biri c'den sayılır
d2 = (c >> 2) & 0011 0011 0011 001100010010000100011, 2, 1, 1C'den kalan sayımlar
e = d0 + d200100010001100102, 2, 3, 2A'nın her 4 bitlik diliminde 1'lerin sayısı
f0 = (e >> 0) & 00001111 0000111100000010000000102, 2Her biri e'den sayılır
f4 = (e >> 4) & 00001111 0000111100000010000000112, 3E'den kalan sayımlar
g = f0 + f400000100000001014, 5A'nın her 8 bitlik diliminde 1'lerin sayısı
h0 = (g >> 0) & 000000001111111100000000000001015Her biri g'den sayılır
h8 = (g >> 8) & 000000001111111100000000000001004Kalan g
i = h0 + h80000000000001001916 bitlik kelimenin tamamında 1'lerin sayısı

Burada işlemler olduğu gibi C programlama dili, yani X >> Y X'i sağa Y bitleriyle kaydırmak anlamına gelir, X ve Y, X ve Y'nin bitsel AND anlamına gelir ve + sıradan toplamadır. Bu problem için bilinen en iyi algoritmalar, yukarıda gösterilen kavrama dayanmaktadır ve burada verilmiştir:[1]

// aşağıdaki işlevlerde kullanılan türler ve sabitler// uint64_t, işaretsiz 64 bitlik tam sayı değişken türüdür (C dilinin C99 sürümünde tanımlanmıştır)sabit uint64_t m1  = 0x5555555555555555; // ikili: 0101 ...sabit uint64_t m2  = 0x3333333333333333; // ikili: 00110011 ..sabit uint64_t m4  = 0x0f0f0f0f0f0f0f0f; // ikili: 4 sıfır, 4 bir ...sabit uint64_t m8  = 0x00ff00ff00ff00ff; // ikili: 8 sıfır, 8 bir ...sabit uint64_t m16 = 0x0000ffff0000ffff; // ikili: 16 sıfır, 16 bir ...sabit uint64_t m32 = 0x00000000ffffffff; // ikili: 32 sıfır, 32 birsabit uint64_t h01 = 0x0101010101010101; // 256'nın toplamı 0,1,2,3 üssü ...// Bu, karşılaştırma için gösterilen saf bir uygulamadır,// ve daha iyi işlevleri anlamaya yardımcı olmak için.// Bu algoritma 24 aritmetik işlem kullanır (kaydırma, ekleme ve).int popcount64a(uint64_t x){    x = (x & m1 ) + ((x >>  1) & m1 ); // her 2 bitin sayısını bu 2 bitin içine koyun     x = (x & m2 ) + ((x >>  2) & m2 ); // her 4 bitin sayısını bu 4 bitin içine koyun     x = (x & m4 ) + ((x >>  4) & m4 ); // her 8 bitin sayısını bu 8 bitin içine koyun     x = (x & m8 ) + ((x >>  8) & m8 ); // her 16 bitin sayısını bu 16 bitin içine koyun     x = (x & m16) + ((x >> 16) & m16); // her 32 bitin sayısını bu 32 bitin içine koyun     x = (x & m32) + ((x >> 32) & m32); // her 64 bitin sayısını bu 64 bitin içine koyun     dönüş x;}// Bu, bilinen diğer tüm aritmetik işlemlerden daha az aritmetik işlem kullanır. // yavaş çarpma olan makinelerde uygulama.// Bu algoritma 17 aritmetik işlem kullanır.int popcount64b(uint64_t x){    x -= (x >> 1) & m1;             // her 2 bitin sayısını bu 2 bitin içine koyun    x = (x & m2) + ((x >> 2) & m2); // her 4 bitin sayısını bu 4 bitin içine koyun     x = (x + (x >> 4)) & m4;        // her 8 bitin sayısını bu 8 bitin içine koyun     x += x >>  8;  // her 16 bitin sayısını en düşük 8 bitine koyun    x += x >> 16;  // her 32 bitin sayısını en düşük 8 bitine koyun    x += x >> 32;  // her 64 bitin sayısını en düşük 8 bitine koyun    dönüş x & 0x7f;}// Bu, bilinen diğer tüm aritmetik işlemlerden daha az aritmetik işlem kullanır. // hızlı çarpma özellikli makinelerde uygulama.// Bu algoritma, biri çarpma olan 12 aritmetik işlem kullanır.int popcount64c(uint64_t x){    x -= (x >> 1) & m1;             // her 2 bitin sayısını bu 2 bitin içine koyun    x = (x & m2) + ((x >> 2) & m2); // her 4 bitin sayısını bu 4 bitin içine koyun     x = (x + (x >> 4)) & m4;        // her 8 bitin sayısını bu 8 bitin içine koyun     dönüş (x * h01) >> 56;  // sol 8 bit x + (x << 8) + (x << 16) + (x << 24) + ... }

Yukarıdaki uygulamalar, bilinen herhangi bir algoritmanın en kötü durum davranışına sahiptir. Bununla birlikte, bir değerin birkaç sıfır olmayan bite sahip olması beklendiğinde, bunun yerine, bu bitleri birer birer sayan algoritmaları kullanmak daha verimli olabilir. Wegner'ın 1960'ta tanımladığı gibi,[13] bitsel AND nın-nin x ile x - 1 farklıdır x sadece en önemsiz sıfır olmayan bitin sıfırlanmasında: 1 çıkarmak en sağdaki 0'ların dizgesini 1'lere ve en sağdaki 1'i 0'a değiştirir. x başlangıçta vardı n 1 olan bitler, sonra yalnızca n bu işlemin yinelemeleri, x sıfıra indirilecektir. Aşağıdaki uygulama bu prensibe dayanmaktadır.

// x'teki çoğu bit 0 olduğunda bu daha iyidir// Bu algoritma tüm veri boyutları için aynı şekilde çalışır.// Bu algoritma, 3 aritmetik işlem ve x'teki "1" bit başına 1 karşılaştırma / dal kullanır.int popcount64d(uint64_t x){    int Miktar;    için (Miktar=0; x; Miktar++)        x &= x - 1;    dönüş Miktar;}

Daha büyük bir bellek kullanımına izin verilirse, Hamming ağırlığını yukarıdaki yöntemlerden daha hızlı hesaplayabiliriz. Sınırsız bellekle, her 64 bitlik tamsayının Hamming ağırlığının büyük bir arama tablosu oluşturabildik. Her 16 bitlik tamsayının hamming fonksiyonunun bir arama tablosunu saklayabilirsek, her 32 bitlik tamsayının Hamming ağırlığını hesaplamak için aşağıdakileri yapabiliriz.

statik uint8_t kelime bitleri[65536] = { / * 0 ile 65535 arası tam sayıların bit sayıları * / };// Bu algoritma 3 aritmetik işlem ve 2 bellek okuma kullanır.int popcount32e(uint32_t x){    dönüş kelime bitleri[x & 0xFFFF] + kelime bitleri[x >> 16];}
// İsteğe bağlı olarak, wordbits [] tablosu bu işlev kullanılarak doldurulabilirint popcount32e_init(geçersiz){    uint32_t ben;    uint16_t x;    int Miktar;    için (ben=0; ben <= 0xFFFF; ben++)    {        x = ben;        için (Miktar=0; x; Miktar++) // yukarıdaki popcount64d () 'den ödünç alındı            x &= x - 1;        kelime bitleri[ben] = Miktar;    }}

Muła vd.[14] popcount64b'nin vektörleştirilmiş bir sürümünün adanmış talimatlardan (ör. x64 işlemcilerde popcnt) daha hızlı çalışabileceğini gösterdiler.

Dil desteği

Bazı C derleyicileri, bit sayma olanakları sağlayan iç işlevler sağlar. Örneğin, GCC (Nisan 2004'teki 3.4 sürümünden beri) yerleşik bir işlev içerir __builtin_popcount varsa bir işlemci talimatı veya aksi takdirde verimli bir kitaplık uygulaması kullanacaktır.[15] LLVM-GCC bu işlevi Haziran 2005'teki 1.5 sürümünden itibaren dahil etmiştir.[16]

İçinde C ++ STL bit dizisi veri yapısı bit kümesi var Miktar() ayarlanan bit sayısını sayan yöntem. İçinde C ++ 20, yeni bir başlık <bit> fonksiyonları içeren eklendi std :: popcount ve std :: has_single_bit, işaretsiz tamsayı türlerinin argümanlarını alarak.

Java'da, büyütülebilir bit dizisi veri yapısı BitSet var BitSet.cardinality () ayarlanan bit sayısını sayan yöntem. Ek olarak, var Tamsayı.bitCount (int) ve Long.bitCount (uzun) sırayla ilkel 32 bit ve 64 bit tam sayılardaki bitleri saymak için işlevler. Ayrıca BigInteger keyfi hassasiyetli tamsayı sınıfında ayrıca bir BigInteger.bitCount () bitleri sayan yöntem.

İçinde Python, int tür bir bit_count () set bit sayısını sayma yöntemi. Bu işlevsellik, 2021'de piyasaya sürülmesi planlanan Python 3.10'da yenidir.[17]

İçinde Ortak Lisp, negatif olmayan bir tam sayı verildiğinde logcount işlevi 1 bit sayısını döndürür. (Negatif tamsayılar için, 2'nin tümleyen gösteriminde 0 bit sayısını döndürür.) Her iki durumda da tamsayı bir BIGNUM olabilir.

İçinde başlayan GHC 7.4, Haskell temel pakette bir popCount işlevinin örnekleri olan tüm türlerde kullanılabilir Bit sayısı sınıf (şu adresten temin edilebilir: Veri bitleri modülü).[18]

MySQL versiyonu SQL dil sağlar BIT_COUNT () standart bir işlev olarak.[19]

Fortran 2008 standart, içsel, temel işleve sahiptir popcnt bir tamsayı (veya tamsayı dizisi) içindeki sıfır olmayan bitlerin sayısını döndürmek.[20]

Bazı programlanabilir bilimsel cep hesaplayıcıları, ayarlanan bitlerin sayısını hesaplamak için özel komutlar içerir, örn. #B üzerinde HP-16C[3][21] ve WP 43S,[22][23] #BITS[24][25] veya BİTSUM[26][27] HP-16C emülatörlerinde ve nBITS üzerinde WP 34S.[28][29]

FreePascal popcnt 3.0 sürümünden beri uygulanmaktadır.[30]

İşlemci desteği

Ayrıca bakınız

Referanslar

  1. ^ a b c d e f g Warren Jr., Henry S. (2013) [2002]. Hacker Zevk (2 ed.). Addison Wesley - Pearson Education, Inc. sayfa 81–96. ISBN  978-0-321-84268-8. 0-321-84268-5.
  2. ^ Knuth, Donald Ervin (2009). "Bitsel hileler ve teknikler; İkili Karar Diyagramları". Bilgisayar Programlama Sanatı. Cilt 4, Fasikül 1. Addison – Wesley Profesyonel. ISBN  0-321-58050-8. (NB. Taslak Fascicle 1b Indirilebilir.)
  3. ^ a b Hewlett-Packard HP-16C Bilgisayar Bilimcisi Sahibi El Kitabı (PDF). Hewlett-Packard Şirketi. Nisan 1982. 00016-90001. Arşivlendi (PDF) 2017-03-28 tarihinde orjinalinden. Alındı 2017-03-28.
  4. ^ [1], Fōrmulæ ile yazılmış. Fōrmulæ wiki. Erişim tarihi: 2019-09-30.
  5. ^ Göreve bir çözüm Nüfus sayımı. Erişim tarihi: 2019-09-30.
  6. ^ Rosetta Kodu. Erişim tarihi: 2019-09-30.
  7. ^ Thompson, Thomas M. (1983). Hata Düzeltme Kodlarından Küre Paketlerine ve Basit Gruplara. Carus Matematiksel Monograflar # 21. Amerika Matematik Derneği. s. 33.
  8. ^ Glaisher, James Whitbread Lee (1899). "Bir asal modüle göre bir iki terimli teorem katsayısının kalıntısı üzerine". Üç Aylık Saf ve Uygulamalı Matematik Dergisi. 30: 150–156. (Not. Özellikle bkz. S. 156'nın son paragrafı.)
  9. ^ Reed, Irving Stoy (1954). "Çoklu Hata Düzeltme Kodları Sınıfı ve Kod Çözme Şeması". Bilgi Teorisi IRE Profesyonel Grubu. Radyo Mühendisleri Enstitüsü (IRE). PGIT-4: 38-49.
  10. ^ Stoica, I .; Morris, R .; Liben-Nowell, D .; Karger, D. R .; Kaashoek, M. F .; Dabek, F .; Balakrishnan, H. (Şubat 2003). "Akor: İnternet uygulamaları için ölçeklenebilir bir eşler arası arama protokolü". Ağ Oluşturmada IEEE / ACM İşlemleri. 11 (1): 17–32. Bölüm 6.3: "Genel olarak, takip etmemiz gereken parmak sayısı, düğümden sorguya olan mesafenin ikili gösterimindeki parmakların sayısı olacaktır."
  11. ^ a b SPARC International, Inc. (1992). "A.41: Nüfus Sayımı. Programlama Notu". SPARC mimari kılavuzu: sürüm 8 (Sürüm 8 ed.). Englewood Kayalıkları, New Jersey, ABD: Prentice Hall. pp.231. ISBN  0-13-825001-4.
  12. ^ Blaxell, David (1978). Hogben, David; Fife, Dennis W. (editörler). "Bağlantıyı bit modeli eşleştirmeye göre kaydet". Bilgisayar Bilimi ve İstatistik - Arayüzle İlgili Onuncu Yıllık Sempozyum. NBS Özel Yayını. ABD Ticaret Bakanlığı / Ulusal Standartlar Bürosu. 503: 146–156.
  13. ^ Wegner, Peter (Mayıs 1960). "İkili bir bilgisayarda olanları saymak için bir teknik". ACM'nin iletişimi. 3 (5): 322. doi:10.1145/367236.367286.
  14. ^ Muła, Wojciech; Kurz, Nathan; Lemire, Daniel (Ocak 2018). "AVX2 Talimatlarını Kullanarak Daha Hızlı Nüfus Sayımları". Bilgisayar Dergisi. 61 (1). arXiv:1611.07612. doi:10.1093 / comjnl / bxx046.
  15. ^ "GCC 3.4 Sürüm Notları". GNU Projesi.
  16. ^ "LLVM 1.5 Sürüm Notları". LLVM Projesi.
  17. ^ "Python 3.10'daki Yenilikler". python.org.
  18. ^ "GHC 7.4.1 sürüm notları". GHC belgeleri.
  19. ^ "Bölüm 12.11. Bit Fonksiyonları - MySQL 5.0 Referans Kılavuzu".
  20. ^ Metcalf, Michael; Reid, John; Cohen, Malcolm (2011). Modern Fortran Açıklaması. Oxford University Press. s. 380. ISBN  0-19-960142-9.
  21. ^ Schwartz, Jake; Grevelle, Rick (2003-10-20) [1993]. HP48S / SX için HP16C Emülatör Kitaplığı. 1.20 (1 ed.). Alındı 2015-08-15. (Not. Bu kütüphane aynı zamanda HP 48G /GX /G +. Özellik kümesinin ötesinde HP-16C bu paket ayrıca ikili, sekizli ve onaltılık hesaplamaları da destekler Kayan nokta sayıları içinde bilimsel gösterim olağan ondalık kayan nokta sayılarına ek olarak.)
  22. ^ Bonin, Walter (2019) [2015]. WP 43S Kullanıcı Kılavuzu (PDF). 0.12 (taslak ed.). s. 135. ISBN  978-1-72950098-9. ISBN  1-72950098-6. Alındı 2019-08-05. [2] [3] (314 sayfa)
  23. ^ Bonin, Walter (2019) [2015]. WP 43S Referans Kılavuzu (PDF). 0.12 (taslak ed.). sayfa xiii, 104, 115, 120, 188. ISBN  978-1-72950106-1. ISBN  1-72950106-0. Alındı 2019-08-05. [4] [5] (271 sayfa)
  24. ^ Martin, Ángel M .; McClure, Greg J. (2015-09-05). "HP-41CX için HP16C Emülatör Modülü - Kullanım Kılavuzu ve QRG" (PDF). Arşivlendi (PDF) 2017-04-27 tarihinde orjinalinden. Alındı 2017-04-27. (NB. Ötesinde HP-16C özellik için bu özel kitaplığı ayarlayın HP-41CX hesap makinesinin işlevselliğini yaklaşık 50 ek işlevle genişletir.)
  25. ^ Martin, Ángel M. (2015-09-07). "HP-41: Yeni HP-16C Emülatörü mevcut". Arşivlendi 2017-04-27 tarihinde orjinalinden. Alındı 2017-04-27.
  26. ^ Thörngren, Håkan (2017/01/10). "Uğur Böceği Belgeleri" (0A sürümü). Alındı 2017-01-29. [6]
  27. ^ "Yeni HP-41 modülü mevcut: Uğur Böceği". 2017-01-10. Arşivlendi 2017-01-29 tarihinde orjinalinden. Alındı 2017-01-29.
  28. ^ Dale, Paul; Bonin, Walter (2012) [2008]. "WP 34S Kullanım Kılavuzu" (PDF) (3.1 ed.). Alındı 2017-04-27.
  29. ^ Bonin, Walter (2015) [2008]. WP 34S Kullanıcı Kılavuzu (3.3 ed.). ISBN  978-1-5078-9107-0.
  30. ^ "Ücretsiz Pascal belgeleri popcnt". Alındı 2019-12-07.
  31. ^ "JDK-6378821: bitCount (), SPARC işlemcilerde ve AMD + 10h'de POPC kullanmalıdır". Java hata veritabanı. 2006-01-30.
  32. ^ Blackfin Komut Seti Referansı (Başlangıç ​​ed.). Analog cihazlar. 2001. sayfa 8-24. Parça Numarası 82-000410-14.
  33. ^ Wolf, Clifford (2019-03-22). "RISC-V" B "RISC-V için Bit Manipülasyon Uzantısı, Taslak v0.37" (PDF). GitHub.

daha fazla okuma

Dış bağlantılar