Jakie są dobre dla operatorów bitowych? [Zamknięte]

19

Języki programowania często zawierają różne operatory bitowe (np. Bitowe przesunięcie w lewo i prawo, bitowe AND, OR, XOR ...). Nie bardzo się przyzwyczajają, a przynajmniej takie jest moje doświadczenie. Czasami są one używane w wyzwaniach programistycznych lub pytaniach do wywiadu, lub rozwiązanie może ich wymagać, np .:

  • Bez użycia operatora równości utwórz funkcję, która zwraca wartość, truegdy dwie wartości są równe
  • Bez użycia trzeciej zmiennej zamień wartość dwóch zmiennych

Te z kolei prawdopodobnie mają niewiele zastosowań w świecie rzeczywistym . Myślę, że powinny być szybsze, ponieważ bezpośrednio manipulują pamięcią na niskim poziomie.

Dlaczego takie są w większości języków programowania? Wszelkie przypadki użycia rzeczywistym świecie?

Anto
źródło
@Anto - Prostym przykładem byłoby wysyłanie danych o wartości 256 KB z szybkością 256 słów jednocześnie (4096 bajtów) do klienta.
Ramhound,
1
„Bez użycia operatora równości utwórz funkcję, która zwraca true, gdy dwie wartości są równe” - w C return !(x-y);:? Nie wiem
Andrew Arnold,
@Andrew: To rozwiązanie, ale możesz to zrobić również z operatorami bitowymi.
Anto
19
„Nie bardzo się przyzwyczajają” - na pewno? Używam ich cały czas. Nie wszyscy pracujemy w Twojej domenie problemowej.
Ed S.
2
Za mało, aby uzyskać pełną odpowiedź, ale spróbuj odczytać 4 górne bity bajtu bez zbędnych drobiazgów, a następnie zastanów się, że niektóre formaty danych są bardzo ciasno upakowane.
Brendan Long,

Odpowiedzi:

53

Nie, mają wiele rzeczywistych aplikacji i są podstawowymi operacjami na komputerach.

Są używane do

  • Żonglowanie blokami bajtów, które nie pasują do typów danych języków programowania
  • Przełączanie kodowania tam iz powrotem z dużego na mały endian.
  • Pakowanie 4 6-bitowych kawałków danych do 3 bajtów dla niektórych połączeń szeregowych lub USB
  • Wiele formatów obrazów ma różną liczbę bitów przypisanych do każdego kanału kolorów.
  • Wszystko, co dotyczy pinów IO we wbudowanych aplikacjach
  • Kompresja danych, która często nie ma danych pasujących do ładnych 8-bitowych granic. \
  • Algorytmy mieszania, CRC lub inne kontrole integralności danych.
  • Szyfrowanie
  • Psuedorandom generowania liczb
  • Raid 5 używa bitowej XOR między woluminami do obliczania parzystości.
  • ton więcej

W rzeczywistości, logicznie, wszystkie operacje na komputerze ostatecznie sprowadzają się do kombinacji tych operacji niskiego poziomu bitowe, odbywających się w ciągu bram elektrycznych procesora.

whatsisname
źródło
1
+1 za dość obszerną listę, którą nawet dodajesz
Anto
28
+1. @Anto: Ta lista nie jest jeszcze wyczerpująca. Pełna lista przypadków użycia dla operatorów bitowych w programowaniu systemów byłaby tak długa, jak wyczerpująca lista zapytań SQL w aplikacjach biznesowych. Ciekawostka: Używam operacje bitowe cały czas, ale nie jest napisane instrukcję SQL w latach ;-)
nikie
4
@nikie: Cały czas piszę SQL, ale od lat nie używam bitowych operatorów! :)
FrustratedWithFormsDesigner,
3
Pracuję w systemach wbudowanych - operatory bitowe to chleb i masło. Używana codziennie bez namysłu.
szybko_niedz.
9
Czy od czasu do czasu korzystam z funkcji zmiany bitów w SQL, czy dostanę nagrodę?
Ant
13

Ponieważ są to podstawowe operacje.

Na tej samej linii myślenia, można argumentować, że dodatek ma kilka zastosowań w świecie rzeczywistym, ponieważ może być zastąpiona całkowicie z odejmowaniem (i negacji) i mnożenia. Ale dodajemy, ponieważ jest to podstawowa operacja.

I nie myśl przez chwilę, że to, że nie widziałeś potrzeby operacji bitowych, nie oznacza, że ​​nie są one używane zbyt często. Rzeczywiście, użyłem operacji bitowych w prawie każdym języku, którego użyłem do takich rzeczy jak maskowanie bitów.

Z góry głowy używałem operacji bitowych do przetwarzania obrazu, pól bitowych i flag, przetwarzania tekstu (np. Wszystkie znaki danej klasy często mają wspólny wzór bitowy), kodowania i dekodowania danych zserializowanych, dekodowania VM lub CPU kody operacyjne i tak dalej. Bez operacji bitowych większość z tych zadań wymagałaby wielokrotnie bardziej złożonych operacji, aby wykonać zadanie mniej niezawodnie lub ze słabszą czytelnością.

Na przykład:

// Given a 30-bit RGB color value as a 32-bit int
// A lot of image sensors spit out 10- or 12-bit data
// and some LVDS panels have a 10- or 12-bit format
b = (color & 0x000003ff);
g = (color & 0x000ffc00) >> 10;
r = (color & 0x3ff00000) >> 20;

// Going the other way:
color = ((r << 20) & 0x3ff00000) | ((g << 10) & 0x000ffc00) | (b & 0x000003ff);

Dekodowanie instrukcji procesora dla procesorów typu RISC (na przykład podczas emulacji innej platformy) wymaga wyodrębnienia części o dużej wartości, jak wyżej. Czasami wykonywanie tych operacji z mnożeniem i dzieleniem i modulo itp. Może być nawet dziesięć razy wolniejsze niż równoważne operacje bitowe.

greyfade
źródło
12

Typowym przykładem jest wyodrębnianie poszczególnych kolorów z 24-bitowej wartości RGB i odwrotnie.


EDYCJA: From http://www.docjar.com/html/api/java/awt/Color.java.html

    value =  ((int)(frgbvalue[2]*255 + 0.5))    |
                (((int)(frgbvalue[1]*255 + 0.5)) << 8 )  |
                (((int)(frgbvalue[0]*255 + 0.5)) << 16 ) |
                (((int)(falpha*255 + 0.5)) << 24 );

źródło
Pokaż ten przykład w praktyce? Fragment kodu?
Anto
Lepszym przykładem może być przetwarzanie wartości RGB 16-bitowych (4,5bpc) lub 30-bitowych (10bpc).
greyfade,
@ Grey, dodaj takie przykłady.
6

Oto przykład ze świata rzeczywistego, który znajdziesz w Quake 3, Quake 4. Doom III. Wszystkie gry, które korzystały z silnika Q3 .

float Q_rsqrt( float number )
{
        long i;
        float x2, y;
        const float threehalfs = 1.5F;

        x2 = number * 0.5F;
        y  = number;
        i  = * ( long * ) &y;                       // evil floating point bit level hacking [sic]
        i  = 0x5f3759df - ( i >> 1 );               // what the fuck? [sic]
        y  = * ( float * ) &i;
        y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//    y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

        return y;
}

(Aby zrozumieć ten kod, musisz zrozumieć, w jaki sposób są przechowywane liczby zmiennoprzecinkowe, zdecydowanie nie mogę tego rozwinąć)

Jeśli chodzi o wykorzystanie, chyba że jesteś w dziedzinach wymagających przesunięcia bitów, takich jak sieć lub grafika, możesz uznać ich cel za nieco akademicki. Ale wciąż ciekawe (przynajmniej dla mnie).

Chris S.
źródło
+1 Za te komentarze, nawet jeśli nie są twoje. Zachichotałem.
Bassinator,
4

Przesunięcie jest szybsze niż pomnożenie lub podzielenie przez potęgę dwóch. Na przykład << = 2 mnoży a przez 4. I odwrotnie, >> = 2 dzieli a przez cztery. Można również przesyłać dane bit-bang do urządzenia za pomocą bitowych operatorów. Na przykład możemy wysyłać N szeregowych strumieni danych z portu N pin za pomocą operacji shift, xor oraz operacji „i” wewnątrz N pętli. Wszystko, co można osiągnąć w logice cyfrowej, można również osiągnąć za pomocą oprogramowania i odwrotnie.

bit-Twiddler
źródło
1
Bądź ostrożny podczas dzielenia z zaokrąglaniem w górę lub w dół itp. Przesunięcie nie bierze tego pod uwagę, więc odkryłem, że lepiej jest używać podziału w kodzie, gdy mam na myśli podział, i pozwolić kompilatorowi zoptymalizować go na zmianę i dodać dla mnie.
Daemin,
@Dememin: Pracuję z liczbami całkowitymi, kiedy używam tej techniki. Domyślne zachowanie dla dzielenia liczb całkowitych w C i C ++ to obcięcie w kierunku zera; dlatego przesunięcie liczby całkowitej w prawo o potęgę dwóch daje taki sam wynik, jak podzielenie liczby całkowitej przez potęgę dwóch.
bit-twiddler,
1
@ bit-twiddler Przesunięcie w prawo nie działa tak samo jak dzielenie liczb ujemnych.
Daemin,
@Dememin: Wygląda na to, że masz ochotę udowodnić, że się mylę. Najpierw rzucasz problem zaokrąglania. Kiedy odrzucam to twierdzenie, stwierdzając, że podział w C i C ++ skraca się do zera, wyrzucasz problem liczby całkowitej ze znakiem. Gdzie powiedziałem, że stosuję operatora shift do liczby całkowitej ujemnej z dopełnieniem dwóch? To powiedziawszy, nadal można użyć operatora zmiany biegów, aby podzielić przez potęgę dwóch. Ponieważ jednak C i C ++ wykonują arytmetyczne przesunięcie w prawo zamiast zwykłego starego przesunięcia w prawo, należy najpierw sprawdzić, czy wartość jest ujemna. Jeśli wartość jest ujemna,
bit-twiddler
1
Dokładnie, zachowaj ostrożność, używając przesunięcia jako zamiennika mnożenia i dzielenia, ponieważ istnieją subtelne różnice. Nie więcej nie mniej.
Daemin,
3

Dawno, dawno temu operatory bitowe były przydatne. Dzisiaj są mniej. Och, nie są całkowicie bezużyteczne, ale od dawna nie widziałem takiego, który powinien był zostać użyty.

W 1977 r. Byłem programistą w asemblerze. Byłem przekonany, że asembler był jedynym prawdziwym językiem. Byłam pewna, że język jak Pascal były dla weenies akademickich, którzy nigdy nie byli dostać coś rzeczywistego zrobić.

Potem przeczytałem „The C Programming Language” Kernighana i Ritchie. To całkowicie zmieniło zdanie. Powód? Miał operatorów bitów! To był język asemblera! Po prostu miał inną składnię.

W tamtych czasach nie mogłem sobie wyobrazić pisania kodu bez ands, ors, shift i rotate. Obecnie prawie nigdy ich nie używam.

Krótka odpowiedź na twoje pytanie brzmi: „Nic”. Ale to nie do końca uczciwe. Zatem dłuższa odpowiedź brzmi: „Przeważnie nic”.

Wujek Bob.
źródło
przychodzi mi na myśl xkcd.com/378 .
Maks.
Operatory bitowe są przydatne do dziś. Fakt, że w Twojej domenie nie są używane, nie czyni go nieużywanym, a nawet rzadko używanym. Oto prosty przykład: spróbuj wdrożyć AES bez operatorów bitowych. To jeden z prostych przykładów czegoś, co robi się na większości komputerów codziennie setki lub tysiące razy dziennie.
WŁAŚNIE MOJA poprawna OPINIA,
Kodowanie / dekodowanie danych bez użycia bitowych operatorów jest co najwyżej bolesne. Na przykład dodanie załączników MIME do wiadomości wymaga, abyśmy byli w stanie obsłużyć kodowanie danych od trzech do czterech (inaczej kodowanie radix64).
bit-twiddler
2

Szyfrowanie

Proponuję rzucić okiem na bardzo mały fragment kodu algorytmu szyfrowania DES :

temp = ((left >>> 1) ^ right) & 0x55555555; right ^= temp; left ^= (temp << 1);
temp = ((right >>> 8) ^ left) & 0x00ff00ff; left ^= temp; right ^= (temp << 8);
temp = ((right >>> 2) ^ left) & 0x33333333; left ^= temp; right ^= (temp << 2);
temp = ((left >>> 16) ^ right) & 0x0000ffff; right ^= temp; left ^= (temp << 16);
temp = ((left >>> 4) ^ right) & 0x0f0f0f0f; right ^= temp; left ^= (temp << 4);
Scott Whitlock
źródło
Chociaż nie jestem pewien, DES jest obecnie zalecany: P
Armand,
@Alison: Nie, ale algorytmy szyfrujące, które go zastąpiły, wymagają jeszcze więcej operacji manipulacji bitami. :-)
Carson63000,
@Alison - oczywiście, ale TripleDES jest po prostu DES wykonywany 3 razy z 3 razy kluczowymi bitami.
Scott Whitlock,
2

Wiele dobrych odpowiedzi, więc nie powtórzę tych zastosowań.

Używam ich dość często w kodzie zarządzanym (C # / .Net) i nie ma to nic wspólnego z oszczędnością miejsca, wydajnością lub sprytnymi algorytmami przesuwania bitów. Czasami pewna logika dobrze nadaje się do przechowywania danych w ten sposób. Często używam ich, gdy mam wyliczenie, ale instancje mogą jednocześnie przyjmować wiele wartości z tego wyliczenia. Nie mogę opublikować przykładu kodu z pracy, ale szybkie google dla „Wylicza flagi” („Flagi” jest sposobem C # definiowania wyliczenia do użycia w bitowy sposób) daje ten dobry przykład: http: // www.dotnetperls.com/enum-flags .

Steve
źródło
2

Istnieje również przetwarzanie równoległe bitowe. Jeśli twoje dane to tylko 1 i 0, możesz spakować 64 z nich w długie, niepodpisane długie słowo i uzyskać 64 równoległe operacje. Informacje genetyczne to dwa bity (reprezentujące kodowanie AGCT DNA), a jeśli możesz wykonywać różne obliczenia równolegle, możesz zrobić znacznie więcej niż nie. Nie wspominając o gęstości danych w pamięci - jeśli pamięć, pojemność dysku lub przepustowość komunikacji jest ograniczona, oznacza, że ​​należy rozważyć kompresję / dekompresję. Nawet liczby całkowite o niskiej wartości predison, które pojawiają się w obszarach takich jak przetwarzanie obrazu, mogą korzystać z trudnych obliczeń równoległych bitów. To cała sztuka sama w sobie.

Omega Centauri
źródło
1

Dlaczego je znaleziono?

Prawdopodobnie dlatego, że odpowiadają instrukcjom montażu, a czasem są po prostu przydatne do rzeczy w językach wyższego poziomu. To samo dotyczy przerażającego, GOTOktóry odpowiada JMPinstrukcji montażu.

Jakie są ich zastosowania?

Naprawdę jest tylko wiele zastosowań, aby wymienić, więc przedstawię ostatnie, aczkolwiek wysoce zlokalizowane, użycie. Dużo pracuję z montażem 6502 i pracowałem nad małą aplikacją, która konwertuje adresy pamięci, wartości, porównuje wartości itp. W kody, które mogą być używane w urządzeniu GameGenie (Zasadniczo aplikacja oszukiwać dla NES). Kody są tworzone przez trochę manipulacji.


źródło
1

Wielu programistów jest obecnie przyzwyczajonych do komputerów z prawie nieskończoną pamięcią.

Ale niektórzy z nich nadal używają małych mikrokontrolerów, w których liczy się każdy bit (na przykład, gdy masz tylko 1k lub mniej pamięci RAM), a operatory bitowe pozwalają programistowi na używanie tych bitów pojedynczo zamiast marnować trochę dużo większe programowanie encja abstrakcyjna, która może być potrzebna do utrzymania stanu wymaganego przez algorytm. We / wy na tych urządzeniach może również wymagać odczytu lub kontroli na podstawie bitowej.

„Prawdziwy świat” ma znacznie więcej tych małych mikrokontrolerów niż serwery lub komputery.

W przypadku czysto teoretycznych typów CS maszyny Turinga dotyczą bitów stanu.

hotpaw2
źródło
1

Jeszcze jedno z wielu możliwych zastosowań operatorów bitowych ...

Operatory bitowe mogą również pomóc w zwiększeniu czytelności kodu. Rozważ następującą deklarację funkcji ....

int  myFunc (bool, bool, bool, bool, bool, bool, bool, bool);

...

myFunc (false, true, false, false, false, true, true, false);

Bardzo łatwo jest zapomnieć, który parametr boolowski oznacza co podczas pisania, a nawet czytania kodu. Łatwo jest również stracić kontrolę nad liczeniem. Taki układ można wyczyścić.

/* More descriptive names than MY_FLAGx would be better */
#define MY_FLAG1    0x0001
#define MY_FLAG2    0x0002
#define MY_FLAG3    0x0004
#define MY_FLAG4    0x0008
#define MY_FLAG5    0x0010
#define MY_FLAG6    0x0020
#define MY_FLAG7    0x0040
#define MY_FLAG8    0x0080

int  myFunc (unsigned myFlags);

...

myFunc (MY_FLAG2 | MY_FLAG6 | MY_FLAG7);

Dzięki bardziej opisowym nazwom flag staje się znacznie bardziej czytelny.

iskrzący
źródło
1

Jeśli wiesz coś o Unicode , prawdopodobnie znasz już UTF-8. Wykorzystuje szereg testów bitowych, przesunięć i masek do spakowania 20-bitowego kodu do 1 do 4 bajtów.

MSalters
źródło
0

Nie używam ich często, ale czasem przydają się. Przychodzi na myśl obsługa enum .

Przykład:

enum DrawBorder{None = 0, Left = 1, Top = 2, Right = 4, Bottom = 8}

DrawBorder drawBorder = DrawBorder.Left | DrawBorder.Right;//Draw right & left border
if(drawBorder & DrawBorder.Left == DrawBorder.Left)
  //Draw the left border
if(drawBorder & DrawBorder.Top == DrawBorder.Top)
  //Draw the top border
//...
Carra
źródło
0

Nie jestem pewien, czy to wykorzystanie zostało już odnotowane:

Widzę LUB dość dużo podczas pracy z kodem źródłowym illumos (openSolaris) w celu zmniejszenia wielu zwracanych wartości do 0 lub 1, np.

int ret = 0;
ret |= some_function(arg, &arg2); // returns 0 or 1
ret |= some_other_function(arg, &arg2); // returns 0 or 1
return ret;
Awalias
źródło