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

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?

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.

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.

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 );

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).

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.

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”.

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);

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 .

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.

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.

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.

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.

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.

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
//...

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;