Manipulacja bitami

W przypadku innych zastosowań zobacz Manipulacja .

Nie mylić z waleniem bitami .

Manipulowanie bitami to czynność polegająca na algorytmicznym manipulowaniu bitami lub innymi fragmentami danych krótszymi niż słowo . Zadania programowania komputerowego , które wymagają manipulacji bitami, obejmują kontrolę urządzeń niskiego poziomu, algorytmy wykrywania i korekcji błędów, kompresję danych , algorytmy szyfrowania i optymalizację . W przypadku większości innych zadań nowoczesne języki programowania umożliwiają programistom bezpośrednią pracę z abstrakcjami zamiast z bitami, które reprezentują te abstrakcje. Kod źródłowy , który manipuluje bitami, wykorzystuje operacje bitowe : AND, OR, XOR, NOT i ewentualnie inne operacje analogiczne do operatorów boolowskich; istnieją również przesunięcia bitów i operacje liczenia jedynek i zer, znajdowania wysokiej i niskiej jedynki lub zera, ustawiania, resetowania i testowania bitów, wyodrębniania i wstawiania pól, pól maskujących i zerowych, zbierania i rozpraszania bitów do iz określonych pozycji bitowych lub pól . Operatory arytmetyczne liczb całkowitych mogą również wykonywać operacje bitowe w połączeniu z innymi operatorami.

Manipulowanie bitami może w niektórych przypadkach wyeliminować lub zmniejszyć potrzebę zapętlania struktury danych i może znacznie przyspieszyć, ponieważ manipulacje bitami są przetwarzane równolegle.

Terminologia

Bit twiddling , bit fiddling i bit bashing są często używane zamiennie z manipulacją bitami, ale czasami odnoszą się wyłącznie do sprytnych lub nieoczywistych sposobów lub zastosowań manipulacji bitami lub żmudnych lub trudnych zadań manipulacji danymi sterowania urządzeniem niskiego poziomu .

Termin kręcenie bitami pochodzi z wczesnego sprzętu komputerowego , w którym operatorzy komputerowi dokonywali korekt, poprawiając lub kręcąc kontrolkami komputerowymi. Wraz z ewolucją języków programowania komputerowego programiści przyjęli termin oznaczający każdą obsługę danych, która obejmowała obliczenia na poziomie bitów .

Operacja bitowa

Główny artykuł: operacja bitowa

Operacja bitowa działa na jednym lub większej liczbie wzorców bitowych lub liczb binarnych na poziomie poszczególnych bitów . Jest to szybkie, prymitywne działanie obsługiwane bezpośrednio przez jednostkę centralną (CPU) i służy do manipulowania wartościami w celu porównań i obliczeń.

Na większości procesorów większość operacji bitowych to pojedyncze cykle — znacznie szybsze niż dzielenie i mnożenie oraz rozgałęzienia. Podczas gdy nowoczesne procesory zwykle wykonują niektóre operacje arytmetyczne i logiczne równie szybko jak operacje bitowe ze względu na dłuższe potoki instrukcji i inne opcje projektowania architektonicznego , operacje bitowe zwykle zużywają mniej energii ze względu na mniejsze wykorzystanie zasobów.

Przykład manipulacji bitami

Aby ustalić, czy liczba jest potęgą dwójki, koncepcyjnie możemy wielokrotnie dzielić liczbę całkowitą przez dwa, aż liczba nie podzieli się równomiernie przez 2; jeśli jedynym pozostałym czynnikiem jest 1, pierwotna liczba była potęgą 2. Używając operatorów bitowych i logicznych, istnieje proste wyrażenie, które zwróci prawdę (1) lub fałsz (0):

      0        0 bool  isPowerOfTwo  =  (  x  !=  )  &&  ((  x  &  (  x  -  1  ))  ==  );

Druga metoda wykorzystuje fakt, że potęgi dwójki mają ustawiony jeden i tylko jeden bit w swojej reprezentacji binarnej:

 x == 0...0  1  0...0 x-1 == 0...001...1 x & (x-1) == 0...000...0

Jeśli liczba nie jest ani zerem, ani potęgą dwójki, będzie miała „1” w więcej niż jednym miejscu:

 x == 0...  1  ...0  1  0...0 x-1 == 0...  1  ...001...1 x & (x-1) == 0...  1  ...000...0

Jeśli używany jest wbudowany kod języka asemblera , wówczas dostępna może być instrukcja zliczająca liczbę jedynek lub zer w argumencie; operand z dokładnie jednym bitem „1” jest potęgą 2. Jednak taka instrukcja może mieć większe opóźnienie niż powyższa metoda bitowa.

Operacje manipulacji bitami

Zobacz też: Zestawy instrukcji manipulacji bitami

Procesory zazwyczaj zapewniają tylko podzbiór użytecznych operatorów bitowych. Języki programowania nie obsługują bezpośrednio większości operacji bitowych, więc do ich kodowania należy używać idiomów. Na przykład język programowania „C” zapewnia tylko bitowe AND(&), OR(|), XOR(^) i NOT(~). Fortran zapewnia AND (.i.), OR (.or.), XOR (.neqv.) i EQV(.eqv.). Algol zapewnia syntaktyczne wyodrębnianie i wstawianie pól bitowych. Gdy języki zapewniają operacje bitowe, które nie są bezpośrednio mapowane na instrukcje sprzętowe, kompilatory muszą syntetyzować operację z dostępnych operatorów.

Szczególnie użyteczną operacją na bitach jest zliczanie początkowych zer używanych do znajdowania najwyższego bitu słowa maszynowego, chociaż może ono mieć różne nazwy w różnych architekturach. Nie ma prostego idiomu języka programowania, więc musi być dostarczony przez wewnętrzną procedurę kompilatora lub bibliotekę systemową. wykonywanie jakichkolwiek operacji na starszym bicie słowa jest bardzo kosztowne (zobacz Znajdź pierwszy zestaw#CLZ ), ze względu na asymetryczną propagację przeniesienia operacji arytmetycznych. Na szczęście większość architektur procesorów zapewnia to od połowy lat 80. Towarzysząca operacja zliczania jedynek , zwana także POPCOUNT, która zlicza liczbę ustawionych bitów w słowie maszynowym, jest również zwykle dostarczana jako operator sprzętowy. Prostsze operacje bitowe, takie jak ustawianie bitów, resetowanie, testowanie i przełączanie, są często dostarczane jako operatorzy sprzętowi, ale można je łatwo symulować, jeśli nie są - na przykład (SET R0, 1; LSHFT R0, i; OR x, R0) ustawia bit i w argumencie x.

Niektóre z bardziej użytecznych i złożonych operacji bitowych, które muszą być zakodowane jako idiomy w języku programowania i zsyntetyzowane przez kompilatory, obejmują:

  • usuń od określonej pozycji bitowej w górę (pozostaw dolną część słowa)
  • usuń z określonej pozycji bitowej w dół (pozostaw górną część słowa)
  • maska ​​od niskiego bitu w dół (wyraźne dolne słowo)
  • maska ​​od wysokiego bitu (wyraźne dolne słowo)
  • ekstrakt bitfielda
  • wstaw pole bitowe
  • operacje rozpraszania/zbierania pola bitowego, które rozdzielają ciągłe części pola bitowego na słowo maszynowe lub gromadzą różne pola bitowe w słowie w ciągłą część pola bitowego (patrz najnowsze operatory Intel PEXT/PDEP). Używany przez kryptografię i kodowanie wideo.
  • inwersja macierzy

Niektóre operacje arytmetyczne można sprowadzić do prostszych operacji i operacji bitowych:

  • zmniejsz pomnóż przez stałą do sekwencji shift-add

Na przykład pomnożenie przez 9 to kopiowanie operandu, przesunięcie w górę o 3 (pomnożenie przez 8) i dodanie do oryginalnego operandu.

  • zredukuj dzielenie przez stałą do sekwencji przesunięcie-odejmowanie

Maskowanie

Główny artykuł: maska ​​(informatyka)

Maska to dane używane do operacji bitowych , szczególnie w polu bitowym .

Używając maski, wiele bitów w Byte , nibble , word (itd.) Można ustawić na włączone, wyłączone lub odwrócone z on na off (lub odwrotnie) w pojedynczej operacji bitowej. Bardziej wszechstronne zastosowania maskowania, stosowane warunkowo do operacji, nazywane są predykacjami .

Zobacz też

Dalsza lektura

  •   Warren, Henry S. (2013). Rozkosz hakera (wyd. 2). Addison-Wesley Professional. P. 512. ISBN 978-0321842688 .
  •   Knuth, Donald E. (2009). Sztuka programowania komputerowego, tom 4, zeszyt 1: Bitowe sztuczki i techniki; Binarne diagramy decyzyjne (wyd. 1). Addison-Wesley Professional. P. 272. ISBN 978-0321580504 . ( Szkic Zeszytu 1a dostępny do pobrania)

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Bit_manipulation&oldid=1126688371 ”