Bit dizisi - Bit array

Bir bit dizisi (Ayrıca şöyle bilinir bit haritası, bit seti, bit dizisiveya bit vektör) bir dizi veri yapısı kompakt bir şekilde depolar bitler. Basit bir uygulama için kullanılabilir veri yapısını ayarla. Bir bit dizisi, işlemleri hızlı bir şekilde gerçekleştirmek için donanımdaki bit düzeyinde paralellikten yararlanmada etkilidir. Tipik bir bit dizisi depolar kw bit, nerede w depolama birimindeki bit sayısıdır, örneğin bayt veya kelime, ve k negatif olmayan bir tam sayıdır. Eğer w saklanacak bit sayısını bölmez, bazı alanların boşa gitmesi nedeniyle iç parçalanma.

Tanım

Bir bit dizisi, bir etki alanından (neredeyse her zaman bir tamsayı aralığı) {0, 1} kümesindeki değerlere eşlemedir. Değerler karanlık / açık, yok / mevcut, kilitli / kilidi açık, geçerli / geçersiz vb. Şeklinde yorumlanabilir. Mesele şu ki, yalnızca iki olası değer vardır, bu nedenle bunlar bir bitte saklanabilir. Diğer dizilerde olduğu gibi, tek bir bite erişim, diziye bir dizin uygulanarak yönetilebilir. Büyüklüğünü (veya uzunluğunu) varsayarsak n bitler, dizi, alanın bir alt kümesini belirtmek için kullanılabilir (ör. {0, 1, 2, ..., n−1}), burada 1 bit, kümedeki bir sayının varlığını ve 0 biti yokluğunu gösterir. Bu set veri yapısı aşağıdakileri kullanır: n/w boşluk kelimeleri, nerede w her birindeki bit sayısı makine kelimesi. En az anlamlı bitin (kelimenin) veya en anlamlı bitin, en küçük dizin numarasını gösterip göstermemesi büyük ölçüde önemsizdir, ancak ilk tercih edilme eğilimindedir ( küçük endian makineleri).

Temel işlemler

Çoğu makine, bellekteki bireysel bitleri adresleyemese veya tek bitleri işlemek için talimatlara sahip olmasa da, bir sözcükteki her bit seçilebilir ve kullanılarak değiştirilebilir. bitsel işlemler. Özellikle:

  • VEYA bir biti bire ayarlamak için kullanılabilir: 11101010 VEYA 00000100 = 11101110
  • VE bir biti sıfıra ayarlamak için kullanılabilir: 11101010 VE 11111101 = 11101000
  • VE sıfır test ile birlikte bir bitin ayarlanıp ayarlanmadığını belirlemek için kullanılabilir:
    11101010 VE 00000001 = 00000000 = 0
    11101010 VE 00000010 = 00000010 ≠ 0
  • XOR, biraz ters çevirmek veya değiştirmek için kullanılabilir:
    11101010 ÖZELVEYA 00000100 = 11101110
    11101110 ÖZELVEYA 00000100 = 11101010
  • Tüm bitleri ters çevirmek için KULLANILAMAZ.
    DEĞİL 10110010 = 01001101

Elde etmek için bit maskesi bu işlemler için gerekli olan bir bit kayması operatörün 1 rakamını uygun sayıda basamak sola kaydırmasının yanı sıra bitsel olumsuzluk Eğer gerekliyse.

Aynı büyüklükteki setleri temsil eden iki bitlik dizi verildiğinde, bunların Birlik, kavşak, ve küme teorik fark kullanma n/w her biri basit bit işlemleri (2n/w fark için) yanı sıra Tamamlayıcı birini:

i 0'dan n / w-1'e kadar tamamlayıcı_a [i]: = değil [i] birleşim [i]: = a [i] veya b [i] kesişim [i]: = a [i] ve b [i ] fark [i]: = a [i] ve (b [i] değil)

Bir bit dizisinin bitlerini yinelemek istersek, bunu her seferinde bir kelime olmak üzere her bir sözcükte döngü yapan çift iç içe geçmiş bir döngü kullanarak verimli bir şekilde yapabiliriz. Sadece n/w hafıza erişimi gereklidir:

i 0'dan n / w-1'e indeks: = 0 // gerekirse kelime: = a [i] b için 0'dan w-1'e değer: = kelime ve 1 ≠ 0 kelime: = kelime sağa kaydırma 1 // değer endeksi ile bir şeyler yapın: = dizin + 1 // gerekirse

Bu kod örneklerinin her ikisi de ideal referans yeri, daha sonra bir veri önbelleğinden büyük bir performans artışı alacak. Bir önbellek satırı ise k kelimeler, sadece hakkında n/hafta önbellekte eksiklikler meydana gelecektir.

Daha karmaşık işlemler

Olduğu gibi karakter dizileri tanımlamak basittir uzunluk, alt dize, sözlükbilimsel karşılaştırmak, birleştirme, tersine çevirmek operasyonlar. Bu işlemlerden bazılarının uygulanması, endianness.

Nüfus / Hamming ağırlığı

Bazen popülasyon sayısı veya Hamming ağırlığı olarak adlandırılan bir bit dizisindeki 1 bit sayısını bulmak istersek, bir dizi basit bit işlemi kullanarak bir sözcükteki bit sayısını hesaplayabilen etkili dalsız algoritmalar vardır. Her kelime için böyle bir algoritma çalıştırıyoruz ve bir toplam tutuyoruz. Sıfırları saymak da benzerdir. Bakın Hamming ağırlığı verimli bir uygulama örnekleri için makale.

Ters çevirme

Piksel başına bir bitlik bir görüntünün dikey olarak çevrilmesi veya bazı FFT algoritmaları, tek tek kelimelerin bitlerini çevirmeyi gerektirir (bu nedenle b31 b30 ... b0 olur b0 ... b30 b31İşlemci üzerinde bu işlem mevcut olmadığında, bu örnekte 32 bit üzerinde ardışık geçişlerle devam etmek hala mümkündür:

değiş tokuş iki 16bit yarım kelimelerdeğiş tokuş bayt tarafından çiftler (0xddccbbaa -> 0xccddaabb)...takas bitler tarafından çiftlertakas bitler (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1) son operasyon Yapabilmek olmak yazılı ((x&0x55555555)<<1) | (x&0xaaaaaaaa)>>1)).

İlkini bul

ilk seti bul veya ilkini bul İşlem, bir dizideki en küçük dizine sahip 1 bitin dizinini veya konumunu tanımlar ve yaygın donanım desteğine (bir sözcükten büyük olmayan diziler için) ve hesaplanması için verimli algoritmalara sahiptir. Zaman öncelik sırası bir bit dizisinde depolanırsa, ilkini bul, kuyruktaki en yüksek öncelikli öğeyi tanımlamak için kullanılabilir. Bir kelime boyutunu genişletmek için ilkini bul daha uzun diziler için, sıfır olmayan ilk kelime bulunabilir ve sonra ilkini bul bu kelime üzerine. İlgili işlemler ilk sıfırı bul, baştaki sıfırları say, önde gelenleri say, sondaki sıfırları say, takip edenleri say, ve günlük tabanı 2 (görmek ilk seti bul ) ayrıca basit bir şekilde bir bit dizisine genişletilebilir.

Sıkıştırma

Bir bit dizisi, "rasgele" bitler için en yoğun depolamadır, yani, her bit eşit ölçüde 0 veya 1 olabilir ve her biri bağımsızdır. Ancak çoğu veri rastgele değildir, bu nedenle daha kompakt bir şekilde saklamak mümkün olabilir. Örneğin, tipik bir faks görüntüsünün verileri rasgele değildir ve sıkıştırılabilir. Çalışma uzunluğu kodlaması genellikle bu uzun akışları sıkıştırmak için kullanılır. Ancak, sıkıştırılmış veri formatlarının çoğuna rasgele erişmek o kadar kolay değildir; ayrıca bit dizilerini çok agresif bir şekilde sıkıştırarak, bit düzeyinde paralellik nedeniyle faydaları kaybetme riskiyle karşı karşıya kalırız (vektörleştirme ). Bu nedenle, bit dizilerini bit akışları olarak sıkıştırmak yerine, bunları bayt veya sözcük akışları olarak sıkıştırabiliriz (bkz. Bitmap dizini (sıkıştırma) ).

Avantajlar ve dezavantajlar

Bit dizilerinin, basit olmalarına rağmen, aynı problemler için diğer veri yapılarına göre bir takım belirgin avantajları vardır:

  • Son derece kompakttırlar; başka hiçbir veri yapısı saklayamaz n bağımsız veri parçaları n/w kelimeler.
  • Küçük bit dizilerinin, bellek erişimi olmadan uzun süre kayıt kümesinde depolanmasına ve değiştirilmesine izin verirler.
  • Bit düzeyinde paralellikten yararlanma, bellek erişimini sınırlama ve maksimum veri önbelleği, pratik veri kümelerinde çoğu zaman diğer birçok veri yapısından daha iyi performans gösterirler, hatta asimptotik olarak daha verimli olanlar bile.

Bununla birlikte, bit dizileri her şeyin çözümü değildir. Özellikle:

  • Sıkıştırma olmadan, hem zamanda hem de uzayda seyrek kümeler (aralıklarına kıyasla daha az öğeye sahip olanlar) için boşa harcanan veri yapılarıdır. Bu tür uygulamalar için sıkıştırılmış bit dizileri, Judy dizileri, dener, ya da Bloom filtreleri bunun yerine düşünülmelidir.
  • Tek tek öğelere erişim pahalı ve bazı dillerde ifade edilmesi zor olabilir. Rasgele erişim sıralı erişimden daha yaygınsa ve dizi nispeten küçükse, bayt adresli bir makinede bir bayt dizisi tercih edilebilir. Bununla birlikte, bir kelime dizisi, makinede yalnızca kelime adresleme yapmadıkça, büyük alan yükü ve ek önbellek eksikliğinden dolayı muhtemelen haklı değildir.

Başvurular

Kompaktlıkları nedeniyle, bit dizileri, alan veya verimliliğin önemli olduğu alanlarda çok sayıda uygulamaya sahiptir. En yaygın olarak, basit bir mantıksal bayrak grubunu veya sıralı bir mantıksal değer dizisini temsil etmek için kullanılırlar.

Bit dizileri için kullanılır öncelik sıraları, dizindeki bit nerede k eğer ve sadece k kuyrukta; bu veri yapısı, örneğin, Linux çekirdeği ve donanımda ilk sıfırı bulma işleminden büyük ölçüde yararlanır.

Tahsisi için bit dizileri kullanılabilir hafıza sayfaları, düğümler, disk sektörleri vb. Bu gibi durumlarda terim bit eşlem Kullanılabilir. Bununla birlikte, bu terim sıklıkla atıfta bulunmak için kullanılır raster görüntüler, birden çok kullanabilir piksel başına bit.

Bit dizilerinin başka bir uygulaması, Bloom filtresi olasılıklı veri yapısını ayarla küçük bir hata olasılığı karşılığında büyük kümeleri küçük bir alanda depolayabilen. Olasılıklı inşa etmek de mümkündür karma tablolar yanlış pozitifleri veya yanlış negatifleri kabul eden bit dizilerine dayanır.

Bit dizileri ve üzerlerindeki işlemler de oluşturmak için önemlidir. kısa ve öz veri yapıları, mümkün olan minimum alana yakın kullanım. Bu bağlamda, n1 biti veya 1 bit sayısını belirli bir konuma kadar saymak önemli hale gelir.

Bit dizileri ayrıca aşağıdaki akışları incelemek için yararlı bir soyutlamadır. sıkıştırılmış genellikle bayt bölümlerini kaplayan veya bayt hizalı olmayan öğeler içeren veriler. Örneğin, sıkıştırılmış Huffman kodlama tek bir 8 bitlik karakterin gösterimi, 1 ila 255 bit uzunluğunda herhangi bir yerde olabilir.

İçinde bilgi alma bit dizileri için iyi bir temsildir. gönderme listeleri çok sık terimler. Kesin olarak artan tam sayılardan oluşan bir listede bitişik değerler arasındaki boşlukları hesaplar ve bunları kullanarak kodlarsak tekli kodlama sonuç, içinde 1 bit bulunan bir bit dizisidir. nsadece ve ancak n listede. Bir boşluğun ima edilen olasılığı n 1/2n. Bu aynı zamanda özel bir durumdur Golomb kodlaması M parametresinin 1 olduğu; bu parametre sadece normal olarak -log (2-p) / günlük (1-p) ≤ 1 veya kabaca terim belgelerin en az% 38'inde geçmektedir.

Dil desteği

APL programlama dili tamsayılardan farklı bir Boolean veri türü olarak rastgele şekil ve boyuttaki bit dizilerini tam olarak destekler. Tüm büyük uygulamalar (Dyalog APL, APL2, APL Next, NARS2000, Gnu APL, vb.) bitleri, makine kelimesinin boyutu ne olursa olsun yoğun bir şekilde paketleyin. Bitlere, olağan indeksleme notasyonu (A [3]) aracılığıyla ve ayrıca genellikle bitlerin bir tablo araması yoluyla bitlerin toplanması gibi özel bir durum algoritması kullanılarak çalıştırıldıkları tüm olağan ilkel fonksiyonlar ve operatörler aracılığıyla ayrı ayrı erişilebilir. .

C programlama dili 's bit alanları bazı bit sayısına eşit büyüklükte yapılarda bulunan sözde nesneler aslında küçük bit dizileridir; sözcükleri yayamayacakları için sınırlıdırlar. Uygun bir sözdizimi vermelerine rağmen, bitlere çoğu makinede bitsel operatörler kullanılarak erişilebilir ve bunlar yalnızca statik olarak tanımlanabilir (C'nin statik dizileri gibi, boyutları derleme zamanında sabittir). C programcılarının kelimeleri küçük bit dizileri olarak kullanmaları ve bit operatörlerini kullanarak bitlerine erişmeleri de yaygın bir deyimdir. Yaygın olarak bulunan bir başlık dosyası X11 system, xtrapbits.h, "sistemlerin bit dizilerinin bit alanı manipülasyonunu tanımlamaları için taşınabilir bir yoldur." Yukarıda belirtilen yaklaşımın daha açıklayıcı bir açıklaması şu adreste bulunabilir: comp.lang.c sss.

İçinde C ++ bireysel olmasına rağmen bools genellikle bir bayt veya tamsayı ile aynı alanı kaplar, STL tip vektör bir kısmi şablon uzmanlığı bir alan verimliliği optimizasyonu olarak bitlerin paketlendiği. Baytlar (bit değil) C ++ 'da adreslenebilir en küçük birim olduğundan, [] operatörü değil bir öğeye bir başvuru döndürür, ancak bunun yerine bir vekil referansı. Bu küçük bir nokta gibi görünebilir, ancak şu anlama gelir: vektör dır-dir değil standart bir STL konteyneri, bu nedenle vektör genellikle tavsiye edilmez. Başka bir benzersiz STL sınıfı, bit kümesi,[1] derleme zamanında belirli bir boyutta sabitlenmiş bir bit vektörü oluşturur ve arayüzünde ve sözdiziminde C programcıları tarafından bit kümeleri olarak kelimelerin deyimsel kullanımına daha çok benzer. Ayrıca, ayarlanan bitlerin sayısını verimli bir şekilde sayma yeteneği gibi bazı ek güce sahiptir. C ++ Kitaplıklarını Artırın sağlamak dynamic_bitset sınıf[2] çalışma zamanında belirtilen boyutu.

D programlama dili standart kitaplığı Phobos'ta bit dizileri sağlar. std.bitmanip. C ++ 'da olduğu gibi, [] operatörü bir referans döndürmez, çünkü tek tek bitler çoğu donanımda doğrudan adreslenebilir değildir, bunun yerine bir bool.

İçinde Java, sınıf BitSet daha sonra C programcılarına aşina olan bitsel operatörlerin adını taşıyan işlevlerle işlenen bir bit dizisi oluşturur. Aksine bit kümesi C ++ 'da Java BitSet "boyut" durumuna sahip değildir (0 bit ile başlatılan, efektif olarak sonsuz bir boyuta sahiptir); herhangi bir dizinde biraz ayarlanabilir veya test edilebilir. Ek olarak, bir sınıf var EnumSet, bir değer kümesini temsil eden numaralandırılmış tür bit alanlarına daha güvenli bir alternatif olarak dahili olarak bir bit vektörü olarak.

.NET Framework sağlar BitArray koleksiyon sınıfı. Boole değerlerini depolar, rastgele erişimi ve bitsel operatörleri destekler, üzerinde yinelenebilir ve Uzunluk özellik, büyütmek veya kesmek için değiştirilebilir.

olmasına rağmen Standart ML bit dizilerini desteklemez, New Jersey Standart ML'sinin bir uzantısı vardır, BitArray yapısı, SML / NJ Kitaplığında. Boyut olarak sabit değildir ve alışılmadık şekilde kaydırma işlemleri dahil olmak üzere ayar işlemlerini ve bit işlemlerini destekler.

Haskell benzer şekilde şu anda bitsel işlemler için standart destekten yoksundur, ancak hem GHC hem de Hugs bir Veri bitleri kaydırma ve döndürme işlemleri dahil olmak üzere çeşitli bitsel işlevler ve işleçlere sahip modül ve boole değerlerinin üzerinde bir "kutulu olmayan" dizi, bir Bit dizisini modellemek için kullanılabilir, ancak bu, önceki modülden destek almasa da.

İçinde Perl dizeler genişletilebilir bit dizileri olarak kullanılabilir. Normal bitsel operatörler kullanılarak işlenebilirler (~ | & ^),[3] ve ayrı bitler, kullanılarak test edilebilir ve ayarlanabilir vec işlevi.[4]

İçinde Yakut, bir tam sayıya erişebilirsiniz (ancak ayarlayamazsınız) (Fixnum veya Bignum) köşeli ayraç operatörünü kullanarak ([]), sanki bir bit dizisiymiş gibi.

Elmalar Çekirdek Vakfı kütüphane içerir CFBitVector ve CFMutableBitVector yapılar.

PL / I dizilerini destekler bit dizeleri sabit uzunlukta veya değişken olabilen keyfi uzunlukta. Dizi elemanları olabilir hizalı- her öğe bir bayt veya kelime sınırında başlar— veya hizalanmamış- öğeler hiçbir dolgu olmadan hemen birbirini takip eder.

PL / pgSQL ve PostgreSQL'in SQL desteği bit dizeleri yerel tip olarak. İki SQL bit türü vardır: bit(n) ve biraz değişken (n), nerede n pozitif bir tamsayıdır.[5]

Gibi donanım tanımlama dilleri VHDL, Verilog, ve SystemVerilog yerel olarak bit vektörlerini destekler, çünkü bunlar gibi depolama öğelerini modellemek için kullanılır. parmak arası terlik genel olarak donanım otobüsleri ve donanım sinyalleri. Gibi donanım doğrulama dillerinde OpenVera, e ve SystemVerilog bit vektörleri, donanım modellerinden değerleri örneklemek ve simülasyonlar sırasında donanıma aktarılan verileri temsil etmek için kullanılır.

Ayrıca bakınız

Referanslar

  1. ^ "SGI.com Tech Archive Resources artık kullanımdan kaldırıldı". SGI. 2 Ocak 2018.
  2. ^ "dynamic_bitset - 1.66.0". www.boost.org.
  3. ^ "perlop - perldoc.perl.org". perldoc.perl.org.
  4. ^ "vec - perldoc.perl.org". perldoc.perl.org.
  5. ^ https://www.postgresql.org/docs/current/datatype-bit.html

Dış bağlantılar