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.
źródło
enums
i mogą miećFlags
atrybut. Mogą znacznie uprościć kod.bool
jest 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.Odpowiedzi:
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 .
źródło
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).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”.
źródło
char
tablicy przez umieszczenie dwóchchar
s w jednymint
.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:
std::bitset
BitSet
BitArray
bitvector
,bitarray
ibitset
bitarray
projekt iBitVector
projektTo 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 += 1
dwa razy, wynik jest równoważnynum += 2
.)Wolę zamiast tego użyć odpowiednich operacji bitowych, jeśli zapewnia je wybrany przez Ciebie język:
źródło
this.stateF = (num & 32) ? true : false
itp. Nie trzeba mutowaćnum
podczas wyodrębniania wartości.+
i-
. Teraz poszedłem o jeden lepszy i użyłem!= 0
zamiast trójskładnikowego, co wydaje mi się bardziej zwięzłe, a jednocześnie wciąż ekscentryczne.