Jak dobrze musi być dobrze zaokrąglony programista przy operacjach bitowych? [Zamknięte]

Przeglądałem ostatnio kod OpenJDK i znalazłem tam intrygujące fragmenty kodu, które mają związek z operacjami bitowymi . Zadałem nawet o tym pytanie na StackOverflow.

Kolejny przykład ilustrujący tę kwestię:

 1141       public static int bitCount(int i) {
 1142           // HD, Figure 5-2
 1143           i = i - ((i >>> 1) & 0x55555555);
 1144           i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
 1145           i = (i + (i >>> 4)) & 0x0f0f0f0f;
 1146           i = i + (i >>> 8);
 1147           i = i + (i >>> 16);
 1148           return i & 0x3f;
 1149       }

Ten kod można znaleźć w klasie Integer .

Nie mogę powstrzymać się od głupoty, kiedy na to patrzę. Czy opuściłem klasę lub dwie na studiach, czy to nie jest coś, co powinienem dostać ? Mogę wykonywać proste operacje bitowe (takie jak ANDing, ORing, XORing, shifting), ale daj spokój, jak ktoś wymyśli taki kod powyżej?

Jak dobrze musi być dobrze zaokrąglony programista przy operacjach bitowych?

Na marginesie ... Martwi mnie to, że osoba, która odpowiedziała na moje pytanie na StackOverflow, odpowiedziała na to w ciągu kilku minut. Jeśli mógł to zrobić, dlaczego po prostu gapiłem się jak jeleń w reflektory?

Powiedziałbym, że jako dobrze rozwinięty programista musisz zrozumieć operatory i operacje bitowe.

Zatem przynajmniej po odrobinie zastanowienia powinieneś być w stanie zrozumieć powyższy kod.

Operacje bitowe mają raczej niski poziom, więc jeśli pracujesz na stronach internetowych i oprogramowaniu LOB, jest mało prawdopodobne, abyś z nich dużo korzystał.

Podobnie jak inne rzeczy, jeśli nie użyjesz ich zbyt często, nie będziesz w nich biegły.

Dlatego nie powinieneś się martwić, że ktoś będzie w stanie szybko to rozgryźć, ponieważ (prawdopodobnie) często pracuje z tego rodzaju kodem. Możliwe pisanie kodu systemu operacyjnego, kodu sterownika lub innej skomplikowanej manipulacji bitami.

Jeśli rozumiesz, jak rozwiązać problemy, takie jak „ustal, czy ustawione są bity 3 i 8”, „wyczyść bit 5” lub „znajdź wartość całkowitą reprezentowaną przez bity 7-12”, masz wystarczającą wiedzę na temat operatorów bitowych, aby sprawdzić wartość Can Twiddle Bits Pole na „dobrze zaokrąglonej” liście kontrolnej.

To, co w twoim przykładzie pochodzi z Hacker's Delight , kompilacji wysokowydajnych algorytmów do manipulowania małymi bitami danych, takimi jak liczby całkowite. Ktokolwiek napisał ten kod, nie wypluł go po prostu w pięć minut; historia jest bardziej prawdopodobna, że ​​potrzebna była szybka, bezgałęziowa metoda liczenia bitów, a autor miał trochę czasu, aby wpatrywać się w łańcuchy bitów i gotować sposób na rozwiązanie problemu. Nikt nie zrozumie, jak to działa na pierwszy rzut oka, chyba że wcześniej go widzieli. Mając solidne zrozumienie podstaw bitowych i trochę czasu poświęconego na eksperymentowanie z kodem, prawdopodobnie możesz dowiedzieć się, jak to robi.

Nawet jeśli nie rozumiesz tych algorytmów, sama wiedza o ich istnieniu zwiększa twoją „zaokrąglenie”, ponieważ gdy nadchodzi czas radzenia sobie z, powiedzmy, wydajnym liczeniem bitów, wiesz, czego się uczyć. W świecie sprzed Google znacznie trudniej było dowiedzieć się o tych rzeczach; teraz są naciśnięcia klawiszy.

Użytkownik, który odpowiedział na twoje pytanie SO, mógł widzieć problem wcześniej lub studiował haszowanie. Napisz do niego i zapytaj.

Z twojego przykładu jest kilka rzeczy, które powinieneś absolutnie wiedzieć bez zastanowienia.

1143 i = i - ((i >>> 1) i 0x55555555);

Powinieneś rozpoznać wzór bitowy 0x555 ... jako naprzemienny wzór bitowy 0101 0101 0101 i że operatorzy kompensują go o 1 bit (po prawej), a to & jest operacją maskowania (i co oznacza maskowanie).

1144 i = (i & 0x33333333) + ((i >>> 2) i 0x33333333);

Ponownie wzorzec, ten to 0011 0011 0011. Także, że tym razem przesuwa się o dwa i ponownie maskuje. przesuwanie i maskowanie są zgodne ze wzorem, który powinieneś rozpoznać ...

1145 i = (i + (i >>> 4)) i 0x0f0f0f0f;

wzór zestala się. Tym razem jest to 00001111 00001111 i, oczywiście, tym razem zmieniamy go na 4. za każdym razem przesuwamy się o rozmiar maski.

1148 zwraca i & 0x3f;

inny wzór bitowy, 3f jest blokiem zer, po którym następuje większy blok zer.

Wszystkie te rzeczy powinny być na pierwszy rzut oka oczywiste, jeśli jesteś „dobrze zaokrąglony”. Nawet jeśli nigdy nie sądzisz, że go użyjesz, prawdopodobnie nie wykorzystasz okazji do znacznego uproszczenia kodu, jeśli o tym nie wiesz.

Nawet w języku wyższego poziomu, wzorce bitowe są używane do przechowywania DUŻO większych ilości danych w mniejszych polach. Dlatego w grach zawsze widzisz ograniczenia 127/8, 63/4 i 255/6, ponieważ musisz przechowywać tak wiele tych rzeczy, że bez spakowania pól będziesz zmuszony użyć nawet dziesięciokrotnie ilość pamięci. (Cóż, ostateczne byłoby, gdybyś musiał przechowywać dużą liczbę boolanów w tablicy, możesz zaoszczędzić 32-64 razy więcej pamięci, niż gdybyś o tym nie pomyślał - większość języków implementuje booleany jako słowo, które często ma 32 bity. Ci, którzy nie czują się komfortowo na tym poziomie, oprą się możliwościom przechowywania takich danych po prostu dlatego, że boją się nieznanego.

Będą również unikać takich rzeczy, jak ręczne analizowanie pakietów dostarczanych przez sieć w formacie spakowanym - co jest trywialne, jeśli się nie boisz. Mogłoby to sprowadzić grę wymagającą pakietu 1k do 200 bajtów, mniejszy pakiet prześlizgnie się przez sieć bardziej wydajnie i zmniejszy opóźnienia i umożliwi wyższe prędkości interakcji (co może umożliwić zupełnie nowe tryby gry dla gry).

Zdarzyło mi się rozpoznać kod, ponieważ widziałem go wcześniej w oprogramowaniu do manipulowania ramkami wideo. Jeśli regularnie pracujesz z takimi kodekami audio i wideo, protokołami sieciowymi lub rejestrami układów, zobaczysz wiele operacji bitowych i stanie się to dla ciebie drugą naturą.

Nie powinieneś czuć się źle, jeśli twoja praca często nie pokrywa się z tymi domenami. Znam dobrze operacje bitowe, ale spowalniam czasem rzadkie sytuacje, w których muszę napisać GUI, z powodu wszystkich dziwactw związanych z układami, ważeniem i rozszerzaniem, i jestem pewien, że są drugą naturą dla innych. Twoje mocne strony są wszędzie tam, gdzie masz największe doświadczenie.

najważniejsze jest, abyś był świadomy tego, jak reprezentowane są liczby całkowite (ogólnie bitvector o stałej długości, gdzie długość zależy od platformy) i jakie operacje są na nim dostępne

główne operacje arytmetyczne + - * / %można zrozumieć bez konieczności ich rozumienia, chociaż może to być przydatne w przypadku mikrooptymalizacji (choć przez większość czasu kompilator będzie w stanie się tym zająć)

zestaw manipulacji bitami | & ~ ^ << >> >>>wymaga co najmniej przejściowego zrozumienia, aby móc z nich korzystać

jednak przez większość czasu będziesz ich używać tylko do przekazywania flag bitów do metody jako ORłączenie razem i przekazywanie int, a następnie ANDwykasowanie ustawień jest bardziej czytelne niż przekazywanie kilku (do 32) wartości logicznych na długiej liście parametrów i pozwala możliwe flagi do zmiany bez zmiany interfejsu

nie wspominając, że booleany są zwykle trzymane osobno w bajtach lub liczbach całkowitych zamiast pakowania ich razem, tak jak flagi

jeśli chodzi o fragment kodu, wykonuje on równoległą liczbę bitów, co pozwala na działanie algorytmu, O(log(n))gdzie n jest liczbą bitów zamiast naiwnej pętli, która jestO(n)

pierwszy krok jest najtrudniejszy do zrozumienia, ale jeśli zaczniesz od konfiguracji, która musi zastąpić sekwencje bitów 0b00do 0b00, 0b01do 0b01, 0b10do 0b01i 0b11do 0b10, łatwiej jest podążać

więc dla pierwszego kroku, i - ((i >>> 1) & 0x55555555)jeśli uznamy, iże jest równy, 0b00_01_10_11wynik powinien być0b00_01_01_10

(uwaga, że 0x5jest równa 0b0101)

iuf bierzemy i = 0b00_01_10_11oznacza 0b00_01_01_10 - (0b00_00_11_01 & 0b01_01_01_01)to, 0b00_01_10_11 - 0b00_00_01_01co z kolei staje się0b00_01_01_10

mogliby zrobić (i & 0x55555555) + ((i >>> 1) & 0x55555555)dla tego samego wyniku, ale jest to 1 dodatkowa operacja

następujące kroki są w podobnym stylu

Każdy powinien zrozumieć podstawowe operacje bitowe. Składa się z podstawowych operacji wykonywania zadań w zoptymalizowany, solidny sposób, który wymaga dużo praktyki.

Ci, którzy codziennie pracują z manipulacją bitami (jak osadzeni ludzie), będą oczywiście rozwijać silną intuicję i niezły zestaw sztuczek.

Ile umiejętności powinien mieć programista, który nie zajmuje się niskopoziomowymi rzeczami przy bitowej manipulacji? Wystarczająco dużo, aby móc usiąść ze zwrotką, taką jak wkleiłeś i powoli ją przepracować, jakby to była łamigłówka lub łamigłówka.

Z tego samego powodu powiedziałbym, że wbudowany programista powinien rozumieć tak dużo o http, jak programista rozumie manipulację bitową. Innymi słowy, „OK” to nie być mistrzem przy manipulacji bitami, jeśli nie używasz go przez cały czas.

Rozkosz hakera jest dziełem pochodnym. Przodkiem wszystkiego jest HakMem z 1972 roku. Http://w3.pppl.gov/~Hammett/work/2009/AIM-239-ocr.pdf

Ważne jest, aby wiedzieć, że oczywisty algorytm dla każdego zadania niekoniecznie jest najlepszy. Istnieje wiele przypadków, gdy wiedząc o istnieniu eleganckiego rozwiązania do partucular problemu jest to, co jest ważne.

Jak trudne są interpretacje operatorów bitowych?

Programuję systemy osadzone. Dużo ćwiczyłem to. Twoje powiązane pytanie dotyczące map skrótów z kodem

static int hash(int h) {
   // This function ensures that hashCodes that differ only by
   // constant multiples at each bit position have a bounded
   // number of collisions (approximately 8 at default load factor).
   h ^= (h >>> 20) ^ (h >>> 12);
   return h ^ (h >>> 7) ^ (h >>> 4);
}

miało dla mnie idealny sens, tak długo, jak długo dyktujemy na głos kod. Zdarzenia opisane w bitCountsą natychmiast jasne, ale ustalenie, dlaczego tak naprawdę liczy bity, zajmuje minutę. Komentarze byłyby jednak świetne i sprawiłyby, że zrozumienie tego, co robi kod, jest tylko trochę trudniejsze niż problem z skrótem.

Ważne jest, aby wprowadzić rozróżnienie między czytaniem a zrozumieniem kodu. Potrafię zinterpretować bitCountkod i odczytać, co robi, ale udowodnienie, dlaczego działa, a nawet, że działa, zajmie chwilę. Istnieje różnica między umiejętnością płynnego odczytu kodu a umiejętnością sprawdzania, dlaczego kod jest taki, jaki jest. Niektóre algorytmy są po prostu trudne. Co z hashkod sens, ale komentarz wyjaśnia dlaczego co zostało zrobione. Nie zniechęcaj się, jeśli funkcja wykorzystująca operatory bitowe jest trudna do zrozumienia, często są używane do robienia skomplikowanych zadań matematycznych, które byłyby trudne bez względu na format.

Analogia

Jestem przyzwyczajony do tego. Jednym z tematów, do których nie jestem przyzwyczajony, jest regex. Od czasu do czasu radzę sobie z nimi przy skryptach kompilacji, ale nigdy w codziennych pracach programistycznych.

Wiem, jak korzystać z następujących elementów wyrażenia regularnego:

• [] klasy postaci
• Te *, .oraz +symbole wieloznaczne
• Początek ^i koniec łańcucha$
• Klasy znaków \ ​​d, \ w i \ s
• Flaga / g

To wystarczy, aby stworzyć proste zapytania, a wiele zapytań, które widzę, nie oddala się od tego.

Cokolwiek nie ma na tej liście, sięgam po ściągawki. Wszystko, z wyjątkiem {}i ()- Ściągawka nie wystarczy. Wiem wystarczająco dużo o tych facetach, aby wiedzieć, że będę potrzebować tablicy, podręcznika referencyjnego, a może współpracownika. Możesz spakować kilka szalonych algorytmów w kilka krótkich wierszy wyrażenia regularnego.

Aby zaprojektować wyrażenie regularne, które wymaga lub sugeruje cokolwiek, co nie znajduje się na mojej liście znanych elementów, zamierzam wymienić wszystkie klasy danych wejściowych, które spodziewam się rozpoznać i umieścić je w pakiecie testowym. Zamierzam tworzyć regex powoli i przyrostowo, z wieloma przerywanymi krokami, i przekażę te kroki kontroli źródła i / lub zostawię je w komentarzu, aby zrozumieć, co miało się stać później, gdy się zepsuje. Jeśli jest w kodzie produkcyjnym, upewnię się, że zostanie sprawdzony przez kogoś z większym doświadczeniem.

Czy to jest miejsce w przypadku operatorów bitowych?

Więc chcesz być dobrze zaokrąglony?

Według mojej oceny, jeśli potrafisz zinterpretować, jak działa taki kod, wyciągając kawałek papieru lub przechodząc do tablicy i ręcznie wykonując operacje, kwalifikujesz się jako dobrze zaokrąglony. Aby zakwalifikować się jako dobry, wszechstronny programista w dziedzinie operacji bitowych, powinieneś być w stanie zrobić cztery rzeczy:

1. Płynnie czytać i zapisywać typowe operacje.
   Dla programisty aplikacji typowe operacje z operatorami bitowymi obejmują podstawowe operatory |oraz &ustawianie i usuwanie flag. To powinno być łatwe. Powinieneś być w stanie czytać i pisać takie rzeczy

   open('file', O_WRONLY | O_APPEND | O_CREAT );
   // Use an OR operator ^ here and ^ here to set multiple flags
   

   bez spowalniania (zakładając, że wiesz, co oznaczają flagi ).

2. Być w stanie odczytać bardziej złożone operacje przy pewnej pracy
   Liczenie bitów naprawdę szybko w czasie O (log (n)) bez rozgałęzień, upewniając się, że liczba kolizji w hashCodes może się różnić o ograniczoną liczbę, oraz parsowanie adresów e-mail , numerów telefonów lub HTML z wyrażeniem regularnym to trudne problemy. Rozsądne jest, aby każdy, kto nie jest ekspertem w tych obszarach, sięgnął po tablicę, nie można nierozsądnie zacząć rozumieć.

3. Umiejętność pisania skomplikowanych algorytmów przy dużym nakładzie pracy
   Jeśli nie jesteś ekspertem, nie powinieneś oczekiwać, że będziesz w stanie wykonywać skomplikowane i trudne zadania. Jednak dobry programista powinien być w stanie to zrobić poprzez ciągłą pracę. Zrób to wystarczająco, a wkrótce będziesz ekspertem :)

Jeśli poszedłeś na przyzwoity uniwersytet, powinieneś był zostać poproszony o przyjęcie na zajęcia z matematyki dyskretnej. Nauczyłbyś się binarnych, ósemkowych i szesnastkowych bram arytmetycznych i logicznych.

W tej notatce normalne jest, że czuję się tym zagubiony, jeśli jest to dla ciebie pociecha, ponieważ piszę przede wszystkim aplikacje internetowe, rzadko muszę patrzeć lub pisać taki kod, ale ponieważ rozumiem arytmetykę binarną i zachowanie operatorów bitowych Mogę w końcu dowiedzieć się, co się tutaj dzieje, mając wystarczająco dużo czasu.

Jako programista telefonów komórkowych musiałem sobie z tym poradzić. Jest to dość powszechne, gdy urządzenie nie ma dużo pamięci lub prędkość transmisji jest ważna. W obu przypadkach starasz się spakować jak najwięcej informacji w kilka bajtów.

Nie przypominam sobie używania bitowych operatorów od około 5 lat PHP (może to tylko ja), a nie od około 10 lat programowania Windows, chociaż niektóre elementy systemu Windows niższego poziomu zawierają wiele bitów.

Mówicie: „Nie mogę nic poradzić na to, że czuję się głupio, kiedy na to patrzę”. NIE - gniewaj się.

Właśnie poznałeś wyniki kowbojskiego programisty.

Czy nie wie nic o pisaniu łatwego do utrzymania kodu? Mam szczerą nadzieję, że to on powróci do tego za rok i spróbuje zapamiętać, co to znaczy.

Nie wiem, czy wycinasz komentarze, czy też ich nie ma, ale ten kod nie przejdzie recenzji kodu w miejscu, gdzie byłem kierownikiem ds. Kontroli jakości (i byłem kilka razy).

Oto dobra zasada - jedynymi dozwolonymi w kodzie liczbami całkowitymi są 0 1 i 1. Wszystkie pozostałe liczby powinny być #definicje, koszty, wyliczenia itp., W zależności od twojego języka.

Jeśli te 3 i 0x33333333 powiedzą coś takiego jak NUM_WIDGET_SHIFT_BITS i WIDGET_READ_MASK, kod byłby łatwiejszy do odczytania.

Wstydź się za to, kto umieścił to w projekcie open source, ale nawet w przypadku osobistego kodu dobrze komentuj i używaj znaczących definicji / wyliczeń i miej własne standardy kodowania.

Ten konkretny fragment kodu pochodzi bezpośrednio z książki Hacker's Delight , rysunek 5.2. Jest online w C (funkcja pop) tutaj . Uwaga autor zaleca teraz stosowanie zaktualizowanych wersji: http://www.hackersdelight.org/HDcode/newCode/pop_arrayHS.c.txt

Jeśli chcesz nauczyć się tego rodzaju mikrooptymalizacji, proponuję tę książkę; to dobra zabawa, ale chyba, że ​​często zajmujesz się programowaniem bitów na bardzo niskim poziomie, prawdopodobnie nie zrozumiesz tego; i przez większość czasu twój kompilator będzie mógł wykonać dla ciebie wiele tego rodzaju optymalizacji.

Pomaga również przepisać wszystkie liczby szesnastkowe w formacie binarnym, aby zrozumieć tego rodzaju algorytmy i pracować nad nimi na przypadku testowym lub dwóch.

Wyjaśnienie na przykładzie. Dane są sekwencjami bitów. Zliczmy bity bajtu 01001101, mając do dyspozycji następujące operacje: 1. Możemy sprawdzić wartość ostatniego bitu. 2. Możemy zmienić sekwencję.

1. 01001101 -> ostatni bajt to 1, ogółem = 1. zmiany
2. 10100110 -> ostatni bajt to 0, ogółem = 1. zmiany
3. 01010011 -> ostatni bajt to 1, ogółem = 2. zmiany
4. 10101001 -> ostatni bajt to 1, ogółem = 3. zmiany
5. 11010100 -> ostatni bajt to 0, ogółem = 3. zmiany
6. 01101010 -> ostatni bajt to 0, łącznie = 3. zmiany
7. 00110101 -> ostatni bajt to 1, łącznie = 4. zmiany
8. 10011010 -> ostatni bajt to 0, łącznie = 4. zmiany

Nasza odpowiedź: 4.

To nie było trudne, prawda? Wielka sprawa z operacjami bitowymi polega na tym, że możemy zrobić ograniczone rzeczy. Nie możemy uzyskać dostępu bezpośrednio. Ale możemy na przykład poznać wartość ostatniego bitu porównując go do MASKI 00000001 i możemy sprawić, że każdy bit będzie ostatnim z operacji zmiany. Oczywiście wynikowy algorytm będzie wyglądał przerażająco dla tych, do których się nie przywykł. Nie ma nic wspólnego z inteligencją.

Nie powiedziałbym, że potrzebujesz, chyba że praca, którą wykonujesz, jest związana z:

• Przetwarzanie audio
• Przetwarzanie wideo
• Grafika
• Praca w sieci (szczególnie tam, gdzie ważny jest rozmiar pakietu)
• Ogromne ilości danych

Przechowywanie uprawnień w flagach w stylu uniksowym jest również kolejnym zastosowaniem, jeśli masz szczególnie złożony model uprawnień dla swojego systemu lub naprawdę chcesz wcisnąć wszystko w jeden bajt, kosztem czytelności.

Poza tymi obszarami uważałbym to za duży plus, gdyby programista / starszy programista mógł wykazać przesunięcie bitów i używanie | & i ^, ponieważ pokazuje zainteresowanie zawodem, które, jak można powiedzieć, prowadzi do bardziej stabilnego i niezawodnego kodu.

Jeśli chodzi o to, aby nie „uzyskać” metody od pierwszego wejrzenia, jak już wspomniano, musisz wyjaśnić, co ona robi i trochę tła. Nie powiedziałbym, że ma to związek z inteligencją, ale z tym, jak dobrze znasz codzienną pracę z systemem szesnastkowym i rozpoznawanie problemów, które niektóre wzorce mogą rozwiązać.