Jak nazywa się przechowywanie / pakowanie wielu stanów logicznych w jedną liczbę?

55

Jest to rodzaj prostej kompresji, w której używasz jednej zmiennej numerycznej do przechowywania wielu stanów logicznych / binarnych, wykorzystując podwojenie oraz fakt, że każda liczba podwojenia to 1 + suma wszystkich poprzednich.

Jestem pewien, że to musi być stara, dobrze znana technika. Chciałbym wiedzieć, jak się nazywa, aby się do niej poprawnie odwoływać. Przeprowadziłem kilka wyszukiwań pod każdym względem, który mogę wymyślić, aby to opisać, ale nie znalazłem nic poza niektórymi artykułami na blogu, w których autorzy artykułu sami się zorientowali i nie wiedzą, jak to nazwać ( przykład 1 , przykład 2 ).

Na przykład oto bardzo prosta implementacja mająca zilustrować tę koncepcję:

packStatesIntoNumber () {
  let num = 0
  if (this.stateA) num += 1
  if (this.stateB) num += 2
  if (this.stateC) num += 4
  if (this.stateD) num += 8
  if (this.stateE) num += 16
  if (this.stateF) num += 32
  return num
}

unpackStatesFromNumber (num) {
  assert(num < 64)
  this.stateF = num >= 32; if (this.stateF) num -= 32
  this.stateE = num >= 16; if (this.stateE) num -= 16
  this.stateD = num >= 8; if (this.stateD) num -= 8
  this.stateC = num >= 4; if (this.stateC) num -= 4
  this.stateB = num >= 2; if (this.stateB) num -= 2
  this.stateA = num >= 1; if (this.stateA) num -= 1
}

Możesz także użyć operatorów bitowych, parsowania liczb 2, wyliczeń ... Istnieje wiele bardziej wydajnych sposobów implementacji, interesuje mnie nazwa tego podejścia bardziej ogólnie.

user56reinstatemonica8
źródło
8
W języku C # istnieją enumsi mogą mieć Flagsatrybut. Mogą znacznie uprościć kod.
Bernhard Hiller
12
Nazwałbym to „symulacją pól bitowych”. Jest to prawie zawsze zły pomysł, chyba że efektywność przestrzeni jest niezwykle ważna.
Kilian Foth
7
@KilianFoth A booljest ogólnie przechowywany wewnętrznie jako 32-bitowa liczba całkowita. Dlatego pakowanie może mieć znaczenie 32-krotne. To naprawdę dużo. To znaczy, my programiści zawsze jesteśmy gotowi wyrzucić połowę naszych zasobów, ale generalnie niechętnie wyrzucam 97% z nich. Takie czynniki marnotrawstwa mogą łatwo zrobić różnicę między możliwością uruchamiania ważnych przypadków użycia a brakiem pamięci.
cmaster
3
Historycznie, zwykle sposób, w jaki maski bitowe są używane do deklarowania, ustawiania i pobierania wartości. Używanie zmian jest dziwne i nie jest najlepszą ilustracją tego podejścia.
JimmyJames
3
@cmaster Powodem, dla którego zapisywane są boole, jest to, że współużytkowanie pojedynczej lokalizacji pamięci (32 lub 64 bity na dzisiejszych komputerach) może mieć bardzo negatywny wpływ na wydajność pamięci podręcznej, chyba że zwracasz dużą uwagę na kod języka maszynowego. Jeśli masz naprawdę ogromną liczbę bitów, prawdopodobnie warto, ale jeśli nie, prawdopodobnie lepiej nie wstępnie optymalizować i po prostu pakować bity, gdy będziesz gotowy do transmisji do sieci lub dysku.
Bill K

Odpowiedzi:

107

Jest to najczęściej określane jako pole bitowe , a innym terminem, który często słyszysz, są maski bitowe , które są używane do pobierania lub ustawiania pojedynczych wartości bitowych lub całego pola bitowego jednocześnie.

Wiele języków programowania ma w tym celu pomocnicze struktury. Jak zauważa @BernhardHiller w komentarzach, C # ma wyliczenia z flagami ; Java ma klasę EnumSet .

Glorfindel
źródło
4
Zinterpretowałbym „pole bitowe” jako funkcję języka, która pozwala przypisywać poszczególne bity do pól struktury, zamiast robić to ręcznie za pomocą operatorów bitowych.
Peter Green
22
@PeterGreen To byłoby inne niż standardowa interpretacja.
Eric,
1
„Mapowanie bitów” lub „Mapowanie bitów”, choć wspólne dla zestawów rekordów i przetwarzania tablic, może również mieć zastosowanie w tym przypadku. Podczas wyodrębniania wspólnych elementów z wielu zestawów wartość można rozłożyć, aby zidentyfikować komponenty modelu stowarzyszonego. Mówimy nawet o liczbach ósemkowych w trybie pliku. Maski bitowe (dowolne maski) są zazwyczaj filtrami (jak w przypadku portów IO i rejestrów kierunku danych).
mckenzm
1
C # również ma BitArray, co pozwala przechowywać dowolną liczbę bitów i indeksować je (podczas gdy flagi są ograniczone do typu liczb całkowitych i przeznaczone do użycia jako maski).
Luaan,
Prawdziwe; Właśnie wspomniałem o dwóch strukturach, które znam najbardziej. Prawdopodobnie jest ich kilkadziesiąt, zwłaszcza w innych językach.
Glorfindel
20

Dziwne, trochę inne terminy tutaj, ale nie widzę tego, który od razu przyszedł mi do głowy (i to w tytule twojego pytania!) - Pakowanie bitów jest tym, co zawsze słyszałem.

Myślałem, że to naprawdę oczywiste, ale dziwnie, kiedy google, to wydaje się być terminem, który jest powszechnie używany, ale nie jest oficjalnie zdefiniowany (Wikipedia wydaje się przekierowywać na pole bitowe, które jest sposobem na pakowanie bitów, ale nie jest nazwą proces). Wyszukiwanie definicji wydaje się prowadzić do tej strony:

http://www.kinematicsoup.com/news/2016/9/6/data-compression-bit-packing-101

Co nie jest świetne do celów SO, ale jest to najlepsza definicja / opis, jaki mogę znaleźć, w tym ten zwięzły opis: „Pakowanie bitów to prosta koncepcja: używaj jak najmniej bitów do przechowywania danych”.

Bill K.
źródło
Czy możesz podać jakieś referencje? Ciekawy termin
Greg Burghardt,
13
Pakowanie bitów jest technicznie poprawne, ale odnosi się również do bardziej ogólnej rzeczy niż tylko stanów logicznych - przechowywania danych w ogóle w jak najmniejszej liczbie bitów. Na przykład jego inne użycie może oznaczać kompresję chartablicy przez umieszczenie dwóch chars w jednym int.
Izkata
@GregBurghardt Wiesz, to interesujące. Nie pomyślałem o tym, gdy pisałem, ponieważ termin był tak powszechny w latach 80. i 90., kiedy nauczyłem się programowania w C i asemblerze - teraz, chociaż wyszukiwarka google WIELU wspomina, nie ma dla niego ostatecznej strony w Wikipedii . Pierwsza odpowiedź w Google ma następującą definicję: „Pakowanie bitów to prosta koncepcja: używaj jak najmniej bitów do przechowywania danych”. kinematicsoup.com/news/2016/9/6/…
Bill K
właśnie wtedy dowiedziałem się o pakowaniu bitów, chociaż możesz być bardziej szalony niż zwykłe zmienianie nieużywanych zer na wartości całkowite. kilka lat temu natknąłem się na system, który przechowywał jeden z jego parametrów jako 8-bitowy zmiennoprzecinkowy. IIRC 5 bitów dla niepodpisanej mantysy (wszystkie wartości były dodatnie, nie trzeba jawnie przechowywać znaku) i 3 więcej dla podstawowego wykładnika 10. W czasie, gdy zakładałem, że jest to starsza kludge sprzętowa bez ścieżki naprzód, ale dzięki uczeniu maszynowemu, które ostatnio zaczęło robić rzeczy z int4 vs int8, mogłem zaobserwować spadek obciążenia z FP16.
Dan Neely,
1
@DanNeely Tego rodzaju rzeczy są również często obsługiwane przez procesory graficzne - handel między precyzją, pamięcią i obliczeniami jest tam bardzo ważny. Zostało to całkiem dobrze wykorzystane w obliczeniach opartych na GPU.
Luaan
14

Istnieje wiele różnych terminów używanych do opisania tego.

Najczęściej bity nazywane są „flagami bitowymi” lub „polami bitowymi”.
(Warto jednak zauważyć, że „pola bitowe” czasami odnoszą się do konkretnej funkcji języków C i C ++, która jest powiązana, ale nie dokładnie taka sama.)

Sama liczba całkowita jest różnie określana jako „tablica bitów”, „zestaw bitów” lub „wektor bitowy”, w zależności od zastosowań i okoliczności.

Tak czy inaczej, ekstrakcja bitów z zestawu bitów / wektor / tablica odbywa się poprzez przesunięcie i maskowanie.
(tj. za pomocą maski bitowej ).


Niektóre przykłady każdego aktywnego terminu:


To nie jest tak naprawdę związane z pytaniem, ale chciałbym powiedzieć: nie używaj dodawania i odejmowania do ustawiania i usuwania bitów, ponieważ metody te są podatne na błędy.
(tzn. jeśli zrobisz to num += 1dwa razy, wynik jest równoważny num += 2.)

Wolę zamiast tego użyć odpowiednich operacji bitowych, jeśli zapewnia je wybrany przez Ciebie język:

packStatesIntoNumber ()
{
  let num = 0
  if (this.stateA) num |= 1
  if (this.stateB) num |= 2
  if (this.stateC) num |= 4
  if (this.stateD) num |= 8
  if (this.stateE) num |= 16
  if (this.stateF) num |= 32
  return num
}

unpackStatesFromNumber (num)
{
  this.stateF = ((num & 32) != 0);
  this.stateE = ((num & 16) != 0);
  this.stateD = ((num & 8) != 0);
  this.stateC = ((num & 4) != 0);
  this.stateB = ((num & 2) != 0);
  this.stateA = ((num & 1) != 0);
}
Pharap
źródło
1
this.stateF = (num & 32) ? true : falseitp. Nie trzeba mutować numpodczas wyodrębniania wartości.
Roger Lipscombe
3
@RogerLipscombe Dobra uwaga, tak naprawdę nie czytałem, co robi kod, tylko reagowałem na użycie +i -. Teraz poszedłem o jeden lepszy i użyłem != 0zamiast trójskładnikowego, co wydaje mi się bardziej zwięzłe, a jednocześnie wciąż ekscentryczne.
Pharap