Bit dizisi - Bit array

Bir bit dizisi ( bit haritası , bit seti , bit dizisi veya bit vektörü olarak da bilinir ), bitleri kompakt bir şekilde depolayan bir dizi veri yapısıdır . Basit bir küme veri yapısını uygulamak için kullanılabilir . 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, kw bitlerini depolar ; burada w , bir bayt veya kelime gibi depolama birimindeki bitlerin sayısıdır ve k , negatif olmayan bir tam sayıdır. eğer wdepolanacak bit sayısını bölmez, dahili parçalanma nedeniyle bir miktar alan boşa harcanır .

Tanım

Bir bit dizisi, bazı etki alanlarından (neredeyse her zaman bir tamsayı aralığı) {0, 1} kümesindeki değerlere eşlemedir. Değerler koyu/açık, yok/mevcut, kilitli/kilidi açık, geçerli/geçersiz vb. olarak yorumlanabilir. Mesele şu ki, sadece iki olası değer var, bu yüzden bir bitte saklanabiliyorlar. Diğer dizilerde olduğu gibi, diziye bir indeks uygulanarak tek bir bite erişim yönetilebilir. Büyüklüğü (veya uzunluk) varsayarak olması , n bit dizisi alan (örneğin, {0, 1, 2, ..., bir alt kümesini belirlemek için kullanılabilir , n , 1 bitlik bir belirten -1}), varlığı ve 0-bit kümede bir sayının olmaması. Bu set veri yapısı kullanımları ile ilgili N / ağırlık alanı, bir deyişle ağırlık her bir bit sayısı olan makine kelime . En az anlamlı bitin (kelimenin) veya en anlamlı bitin en küçük indeks numarasını gösterip göstermediği büyük ölçüde önemsizdir, ancak ilki tercih edilme eğilimindedir ( küçük endian makinelerde).

Temel işlemler

Çoğu makine bellekteki tek tek bitleri adresleyemese ve tek bitleri işlemek için talimatlara sahip olmasa da, bir kelimedeki her bit, bitsel işlemler kullanılarak seçilebilir ve manipüle edilebilir . Özellikle:

  • VEYA bir biti bire ayarlamak için kullanılabilir: 11101010 VEYA 00000100 = 11101110
  • AND, bir biti sıfıra ayarlamak için kullanılabilir: 11101010 AND 11111101 = 11101000
  • AND, sıfır testiyle 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 geçiş yapmak için kullanılabilir:
    11101010 XOR 00000100 = 11101110
    11101110 XOR 00000100 = 11101010
  • NOT tüm bitleri ters çevirmek için kullanılamaz.
    10110010 = 01001101 DEĞİL

Bu işlemler için gereken bit maskesini elde etmek için , 1 sayısını uygun sayıda sola kaydırmak için bir bit kaydırma operatörü ve gerekirse bitsel olumsuzlama kullanabiliriz .

Kümeleri temsil eden aynı boyutta iki bit dizisi verildiğinde, bunların birleşimini , kesişimini ve küme teorik farklarını , her biri n / w basit bit işlemlerini ( fark için 2 n / w ) ve ayrıca aşağıdakilerden birinin tamamlayıcısını kullanarak hesaplayabiliriz : 

for i from 0 to n/w-1
    complement_a[i] := not a[i]
    union[i]        := a[i] or b[i]
    intersection[i] := a[i] and b[i]
    difference[i]   := a[i] and (not b[i])

Bir bit dizisinin bitleri arasında yineleme yapmak istersek, bunu, her bir sözcük arasında birer birer döngü yapan, çift yuvalanmış bir döngü kullanarak verimli bir şekilde yapabiliriz. Yalnızca n / w bellek erişimleri gereklidir: 

for i from 0 to n/w-1
    index := 0    // if needed
    word := a[i]
    for b from 0 to w-1
        value := word and 1 ≠ 0
        word := word shift right 1
        // do something with value
        index := index + 1    // if needed

Bu kod örneklerinin her ikisi de, daha sonra bir veri önbelleğinden büyük bir performans artışı alacak olan ideal referans konumu sergiler . Bir önbellek satırı k kelimeyse, yalnızca yaklaşık n / hafta önbellek ıskaları meydana gelir.

Daha karmaşık işlemler

Karakter dizgilerinde olduğu gibi uzunluk , alt dizgi , sözlükbilimsel karşılaştırma , birleştirme , ters işlemleri tanımlamak kolaydır . Bu işlemlerden bazılarının uygulanması endianness'e duyarlıdır .

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

Bir bit dizisindeki 1 bit sayısını bulmak istiyorsak, bazen popülasyon sayısı veya Hamming ağırlığı olarak adlandırılır, bir dizi basit bit işlemi kullanarak bir kelimedeki bit sayısını hesaplayabilen verimli dalsız algoritmalar vardır. Her kelimede böyle bir algoritma çalıştırırız ve bir toplam tutarı tutarız. Sıfırları saymak benzerdir. Etkili bir uygulama örnekleri için Hamming ağırlık makalesine bakın .

ters çevirme

Dikey bir adet bir-bit başına piksel görüntüsünün çevirme, veya bir FFT algoritmaları, bireysel kelime bit (böylece çevirme gerektirir b31 b30 ... b0olur b0 ... b30 b31). Bu işlem işlemcide mevcut olmadığında, bu örnekte 32 bit üzerinde ardışık geçişlerle devam etmek hala mümkündür: 

exchange two 16-bit halfwords
exchange bytes by pairs (0xddccbbaa -> 0xccddaabb)
...
swap bits by pairs
swap bits (b31 b30 ... b1 b0 -> b30 b31 ... b0 b1)

The last operation can be written ((x&0x55555555) << 1) | (x&0xaaaaaaaa) >> 1)).

İlkini bul

Bul birinci seti ya da ilk bulmak işlemi tanımlar dizin veya bir dizideki en küçük endekse sahip 1-bit pozisyonu ve (bir kelime daha büyük olmayan diziler için) yaygın donanım desteği ve hesaplama için etkin algoritmalar bulunmaktadır. Bir bit dizisinde bir öncelik sırası depolandığında, kuyruktaki en yüksek öncelikli öğeyi tanımlamak için ilkini bul kullanılabilir. Kelime boyutunda bir ilk bul daha uzun dizilere genişletmek için , ilk sıfır olmayan kelimeyi bulabilir ve ardından o kelimede ilkini bul çalıştırabilirsiniz . İlgili işlemler , ilk sıfır bulmak , önde gelen sıfır sayısı , gelen olanlar sayısı , sıfır arka sayısı , olanları arka sayısı ve log tabanı 2 (bkz ilk kümesini bulmak da basit bir şekilde biraz dizisine uzatılabilir).

Sıkıştırma

Bir bit dizisi, "rastgele" bitler için en yoğun depolamadır, yani her bitin eşit derecede 0 veya 1 olması muhtemeldir 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 rastgele değildir ve sıkıştırılabilir. Çalışma uzunluğu kodlaması , bu uzun akışları sıkıştırmak için yaygın olarak kullanılır. Ancak, çoğu sıkıştırılmış veri formatına rastgele erişim o kadar kolay değildir; ayrıca bit dizilerini çok agresif bir şekilde sıkıştırarak, bit düzeyinde paralellik ( vektörleştirme ) nedeniyle faydaları kaybetme riskiyle karşı karşıyayız . Bu nedenle, bit dizilerini bit akışları olarak sıkıştırmak yerine, bunları bayt veya kelime akışları olarak sıkıştırabiliriz (bkz. Bitmap indeksi (sıkıştırma) ).

Avantajlar ve dezavantajlar

Bit dizileri, basitliklerine rağmen, aynı problemler için diğer veri yapılarına göre bir takım belirgin avantajlara sahiptir:

  • Son derece kompakttırlar; başka hiçbir veri yapısı, n / w sözcüklerle n bağımsız veri parçasını depolayamaz .
  • Küçük bit dizilerinin, bellek erişimi olmadan uzun süreler boyunca kayıt kümesinde saklanmasına ve işlenmesine izin verirler.
  • Bit düzeyinde paralellikten yararlanma, bellek erişimini sınırlama ve veri önbelleğini maksimum düzeyde kullanma yetenekleri nedeniyle, pratik veri kümelerinde, asimptotik olarak daha verimli olanlarda bile, çoğu zaman diğer birçok veri yapısından daha iyi performans gösterirler.

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

  • Sıkıştırma olmadan, hem zaman hem de uzayda seyrek kümeler (aralıklarına kıyasla az elemana sahip olanlar) için savurgan küme veri yapılarıdır. Bu tür uygulamalar için bunun yerine sıkıştırılmış bit dizileri, Judy dizileri , denemeler ve hatta Bloom filtreleri düşünülmelidir.
  • Tek tek öğelere erişmek bazı dillerde pahalı ve ifade edilmesi zor olabilir. Rastgele erişim sıralı erişimden daha yaygınsa ve dizi nispeten küçükse, bayt adreslemeli bir makinede bir bayt dizisi tercih edilebilir. Bununla birlikte, bir kelime dizisi, makinede yalnızca kelime adresleme olmadığı sürece, büyük alan yükü ve neden olduğu ek önbellek kayıpları nedeniyle muhtemelen haklı değildir.

Uygulamalar

Kompakt olmaları nedeniyle, bit dizilerinin alan veya verimliliğin önemli olduğu alanlarda bir dizi uygulaması vardır. En yaygın olarak, basit bir boole bayrağı grubunu veya sıralı bir boole değerleri dizisini temsil etmek için kullanılırlar.

Bit dizileri öncelik sıraları için kullanılır , burada k dizinindeki bit, yalnızca ve yalnızca k kuyruktaysa ayarlanır ; bu veri yapısı, örneğin, Linux çekirdeği tarafından kullanılır ve donanımdaki ilk sıfır bul işleminden güçlü bir şekilde yararlanır.

Bit dizileri, bellek sayfalarının , düğümlerin , disk sektörlerinin vb. tahsisi için kullanılabilir . Bu gibi durumlarda, bitmap terimi kullanılabilir. Ancak, bu terim sıklıkla piksel başına birden çok bit kullanabilen raster görüntülere atıfta bulunmak için kullanılır .

Bit dizilerinin başka bir uygulaması, küçük bir hata olasılığı karşılığında büyük kümeleri küçük bir alanda depolayabilen olasılıksal bir küme veri yapısı olan Bloom filtresidir . Yanlış pozitifleri veya yanlış negatifleri kabul eden bit dizilerine dayalı olasılıklı karma tablolar oluşturmak da mümkündür .

Bit dizileri ve üzerlerindeki işlemler, mümkün olan en az alana yakın alan kullanan kısa ve öz veri yapıları oluşturmak için de önemlidir . Bu bağlamda, bulma gibi işlemleri n 1 bit inci ya da önemli hale belirli bir pozisyona kadar 1 bit sayısını sayan.

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

Gelen bilgi alma , bit diziler için iyi bir temsilidir gönderme listeleri çok sık terimlerin. Onları kullanan kesin artan tamsayı ve kodlama listesinde bitişik değerleri arasındaki boşluklar hesaplaması kodlama tekli , sonuç olarak, bir 1 bit ile bir bit dizisi olan n, ancak ve ancak inci pozisyonda n de düşünülmelidir. Bir boşluk zımni olasılık n 1/2 olan n . Bu aynı zamanda, M parametresinin 1 olduğu Golomb kodlamasının özel durumudur ; bu parametre normalde sadece -log(2- p )/log(1- p ) ≤ 1 olduğunda seçilir veya kabaca terim belgelerin en az %38'inde geçer.

Dil desteği

APL programlama dili tamamen Boolean tamsayılar gelen veri türü farklı olarak keyfi şekli ve boyutu bit dizileri destekler. Tüm büyük uygulamalar ( Dyalog APL, APL2, APL Next, NARS2000, Gnu APL , vb.) bitleri makine kelimesi boyutu ne olursa olsun yoğun bir şekilde paketler. Bitlere, olağan indeksleme notasyonu (A[3]) aracılığıyla ve ayrıca genellikle bir bayt tablosu araması yoluyla bitleri toplamak gibi özel bir durum algoritması kullanılarak çalıştırıldıkları tüm olağan ilkel işlevler ve operatörler aracılığıyla tek tek erişilebilir. .

C programlama dilinin 'nin bit alanları sözde nesneleri boyutuna sahip yapılar bulunan, bit bir sayıya eşit olması küçük bir bit dizileri bulunmaktadır; sözcükleri yayamayacakları için sınırlıdırlar. Uygun bir sözdizimi sağlasalar da, bitlere hala çoğu makinede bytewise operatörleri kullanılarak erişilir ve bunlar yalnızca statik olarak tanımlanabilir (C'nin statik dizileri gibi, boyutları derleme zamanında sabitlenir). C programcılarının kelimeleri küçük bit dizileri olarak kullanması ve bit operatörlerini kullanarak bitlerine erişmesi de yaygın bir deyimdir. X11 sisteminde bulunan, yaygın olarak bulunan bir başlık dosyası olan xtrapbits.h, "sistemlerin bit dizilerinin bit alanı manipülasyonunu tanımlaması için taşınabilir bir yoldur". Yukarıda bahsedilen yaklaşımın daha açıklayıcı bir açıklaması comp.lang.c sss'de bulunabilir .

Gelen C ++ bağımsız olsa da, bools tipik olarak bir bayt veya bir tamsayı hacimsel olarak, STL türü vector<bool>a, kısmi şablon uzmanlık bitleri alan verimliliği optimize olarak paketlenmiş edildiği. Bayt (olup bit) C küçük adreslenebilir birimi olduğu ++ [] operatör etmez olmayan bir eleman için bir başvuru göndermez ancak, bunun yerine bir geri vekil referans . Bu küçük bir nokta gibi görünebilir, ancak bu demektir vector<bool>olduğu değil kullanımı neden olan standart STL konteyner, vector<bool>genel olarak önerilmez. Başka bir benzersiz STL sınıfı, bitsetderleme 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, ayarlanmış bit sayısını verimli bir şekilde sayma yeteneği gibi bazı ek güce de sahiptir. Kuvvetlendirme C ++ kitaplıkları bir sağlar dynamic_bitset, boyutu çalışma zamanında belirtilen sınıfı.

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

In Java , sınıf BitSetve ardından C'ye programcılarına tanıdık bit operatörleri adını fonksiyonları ile manipüle edilir biraz dizi oluşturur. bitsetC++' dakinden farklı olarak , Java BitSetbir "boyut" durumuna sahip değildir (0 bit ile başlatılmış etkin bir sonsuz boyuta sahiptir); bit herhangi bir dizinde ayarlanabilir veya test edilebilir. Ek olarak, bit alanlarına daha güvenli bir alternatif olarak, dahili olarak bir bit vektörü olarak numaralandırılmış türdeEnumSet bir değerler kümesini temsil eden bir sınıf vardır .

.NET Framework bir malzeme BitArraytoplama sınıfı. Bir dizi tipi kullanarak bitleri depolar int( dizideki her eleman genellikle 32 biti temsil eder). Sınıf, rastgele erişimi ve bit düzeyinde operatörleri destekler, yinelenebilir ve Lengthözelliği, onu büyütmek veya kısaltmak için değiştirilebilir.

Standard ML'nin bit dizileri için desteği olmamasına rağmen , Standard ML of New Jersey, BitArraySML/NJ Kitaplığında bir uzantıya, yapıya sahiptir . Boyut olarak sabit değildir ve alışılmadık şekilde kaydırma işlemleri de dahil olmak üzere ayarlanmış işlemleri ve bit işlemlerini destekler.

Haskell aynı şekilde şu anda bitsel işlemler için standart desteğe sahip değildir, ancak hem GHC hem de Hugs Data.Bits, kaydırma ve döndürme işlemleri dahil olmak üzere çeşitli bitsel işlevlere ve operatörlere sahip bir modül sağlar ve bir Bit dizisini modellemek için boole değerleri üzerinde "kutusuz" bir dizi kullanılabilir, ancak bu eski modül desteğinden yoksundur.

In Perl , dizeleri genişletilebilir bit diziler olarak kullanılabilir. Her zamanki bitsel operatörler ( ~ | & ^) kullanılarak manipüle edilebilirler ve bireysel bitler vec işlevi kullanılarak test edilebilir ve ayarlanabilir .

Olarak Ruby , bir tamsayı (biraz erişmek (ancak ayarlanabilir) biçimde Fixnumya da Bignum) dirsek operatörü (kullanarak []bitler bir dizi olarak).

Apple'ın Core Foundation kitaplığı, CFBitVector ve CFMutableBitVector yapılarını içerir .

PL/I , sabit uzunlukta veya değişken olabilen, rastgele uzunluktaki bit dizilerinin dizilerini destekler . Dizi öğeleri hizalanmış olabilir - her öğe bir bayt veya sözcük sınırında başlar - veya hizalanmamış - öğeler dolgu olmadan hemen birbirini takip eder.

PL/pgSQL ve PostgreSQL'in SQL'i yerel tür olarak bit dizilerini destekler . İki SQL bit türü vardır: ve , burada pozitif bir tam sayıdır. bit(n)bit varying(n)n

VHDL , Verilog ve SystemVerilog gibi donanım tanımlama dilleri , genel olarak iki duraklı , donanım veriyolları ve donanım sinyalleri gibi depolama öğelerini modellemek için kullanıldığından, bit vektörlerini doğal olarak destekler . OpenVera , e ve SystemVerilog gibi donanım doğrulama dillerinde , donanım modellerinden değerleri örneklemek ve simülasyonlar sırasında donanıma aktarılan verileri temsil etmek için bit vektörleri kullanılır.

Common Lisp , bir sınıf ve bir tür belirteci olarak ikili kapasitede hareket eden bit-vector, yerleşik öğesinin özel bir durumu olarak tek boyutlu bir uygulama sağlar array. Dizinin bir türevi olarak, isteğe bağlı olarak bit vektörünün dinamik olarak yeniden boyutlandırılabilir olarak belirlenmesine izin veren make-arraybir öğe türüyle yapılandırılacak genel işleve dayanır bit. bit-vectorAncak ölçüde sonsuz değildir. simple-bit-vectorDinamik özellikleri açıkça dışlayan daha kısıtlı bir tür vardır. Bit vektörleri, okuyucu makrosu olarak temsil edilir ve daha özlü bir şekilde oluşturulabilir . Tüm dizilere uygulanabilen genel işlevlere ek olarak, bit vektörleri için özel işlemler mevcuttur. Tek bitlere ve işlevleri kullanılarak erişilebilir ve değiştirilebilir ve çok sayıda mantıksal işlem desteklenir. #*bitsbitsbit

Ayrıca bakınız

Referanslar

Dış bağlantılar