Działanie i użycie bitowe


102

Rozważ ten kod:

x = 1        # 0001
x << 2       # Shift left 2 bits: 0100
# Result: 4

x | 2        # Bitwise OR: 0011
# Result: 3

x & 1        # Bitwise AND: 0001
# Result: 1

Rozumiem operatory arytmetyczne w Pythonie (i innych językach), ale nigdy nie rozumiałem zbyt dobrze operatorów „bitowych”. W powyższym przykładzie (z książki o Pythonie) rozumiem lewą zmianę, ale nie rozumiem dwóch pozostałych.

Do czego służą operatory bitowe? Byłbym wdzięczny za kilka przykładów.



Odpowiedzi:


163

Operatory bitowe to operatory, które działają na wartościach wielobitowych, ale koncepcyjnie po jednym bicie.

  • ANDma wartość 1 tylko wtedy, gdy oba wejścia mają wartość 1, w przeciwnym razie wynosi 0.
  • ORwynosi 1, jeśli jedno lub oba jego wejścia mają wartość 1, w przeciwnym razie wynosi 0.
  • XORwynosi 1 tylko wtedy , gdy dokładnie jedno z jego wejść ma wartość 1, w przeciwnym razie wynosi 0.
  • NOT ma wartość 1 tylko wtedy, gdy jego wejście wynosi 0, w przeciwnym razie wynosi 0.

Można je najlepiej przedstawić jako tabele prawdy. Możliwości wejściowe są na górze i po lewej stronie, wynikowy bit jest jedną z czterech (dwóch w przypadku NIE, ponieważ ma tylko jedno wejście) wartości pokazanych na przecięciu wejść.

AND | 0 1     OR | 0 1     XOR | 0 1    NOT | 0 1
----+-----    ---+----     ----+----    ----+----
 0  | 0 0      0 | 0 1       0 | 0 1        | 1 0
 1  | 0 1      1 | 1 1       1 | 1 0

Jednym z przykładów jest to, że jeśli chcesz tylko 4 dolne bity liczby całkowitej, to ORAZ to z 15 (binarne 1111), więc:

    201: 1100 1001
AND  15: 0000 1111
------------------
 IS   9  0000 1001

Bity zerowe w 15 w tym przypadku skutecznie działają jak filtr, zmuszając bity wyniku również do zera.

Ponadto >>i <<często są uwzględniane jako operatory bitowe i „przesuwają” wartość odpowiednio w prawo i w lewo o określoną liczbę bitów, odrzucając bity, które toczą się na końcu, do którego się przesuwasz, i wprowadzając zero bitów na drugi koniec.

Na przykład:

1001 0101 >> 2 gives 0010 0101
1111 1111 << 4 gives 1111 0000

Zwróć uwagę, że przesunięcie w lewo w Pythonie jest niezwykłe, ponieważ nie używa stałej szerokości, w której bity są odrzucane - podczas gdy wiele języków używa stałej szerokości w oparciu o typ danych, Python po prostu rozszerza szerokość, aby obsłużyć dodatkowe bity. Aby uzyskać zachowanie odrzucania w Pythonie, możesz śledzić przesunięcie w lewo z bitowym przesunięciem, na andprzykład w 8-bitowym przesunięciu wartości w lewo o cztery bity:

bits8 = (bits8 << 4) & 255

Mając to na uwadze, kolejny przykład operatorów bitowe jest, jeśli masz dwie wartości 4-bitowe, które chcesz zapakować do jednej z 8-bitowym, można użyć wszystkich trzech swoich operatorów ( left-shift, andi or):

packed_val = ((val1 & 15) << 4) | (val2 & 15)
  • & 15Operacja będzie upewnić się, że obie wartości mają jedynie niższe 4 bity.
  • To << 44-bitowe przesunięcie w lewo, aby przejść val1do pierwszych 4 bitów wartości 8-bitowej.
  • Po |prostu łączy te dwa razem.

Jeśli val1wynosi 7 i val24:

                val1            val2
                ====            ====
 & 15 (and)   xxxx-0111       xxxx-0100  & 15
 << 4 (left)  0111-0000           |
                  |               |
                  +-------+-------+
                          |
| (or)                0111-0100

43

Jedno typowe użycie:

| służy do ustawiania pewnego bitu na 1

& służy do testowania lub usuwania określonego fragmentu

  • Ustaw bit (gdzie n to numer bitu, a 0 to najmniej znaczący bit):

    unsigned char a |= (1 << n);

  • Wyczyść trochę:

    unsigned char b &= ~(1 << n);

  • Przełącz trochę:

    unsigned char c ^= (1 << n);

  • Przetestuj trochę:

    unsigned char e = d & (1 << n);

Weźmy na przykład przypadek Twojej listy:

x | 2służy do ustawiania bitu 1 xna 1

x & 1służy do sprawdzania, czy bit 0 of xto 1 czy 0


38

do czego służą operatory bitowe? Byłbym wdzięczny za kilka przykładów.

Jednym z najczęstszych zastosowań operacji bitowych jest analizowanie kolorów szesnastkowych.

Na przykład, oto funkcja Pythona, która akceptuje ciąg znaków typu String #FF09BEi zwraca krotkę jego wartości Red, Green i Blue.

def hexToRgb(value):
    # Convert string to hexadecimal number (base 16)
    num = (int(value.lstrip("#"), 16))

    # Shift 16 bits to the right, and then binary AND to obtain 8 bits representing red
    r = ((num >> 16) & 0xFF)

    # Shift 8 bits to the right, and then binary AND to obtain 8 bits representing green
    g = ((num >> 8) & 0xFF)

    # Simply binary AND to obtain 8 bits representing blue
    b = (num & 0xFF)
    return (r, g, b)

Wiem, że są bardziej wydajne sposoby, aby to osiągnąć, ale uważam, że jest to naprawdę zwięzły przykład ilustrujący zarówno przesunięcia, jak i bitowe operacje logiczne.


14

Myślę, że druga część pytania:

Do czego służą operatory bitowe? Byłbym wdzięczny za kilka przykładów.

Został tylko częściowo rozwiązany. To są moje dwa centy w tej sprawie.

Operacje bitowe w językach programowania odgrywają podstawową rolę w przypadku wielu aplikacji. Prawie wszystkie obliczenia niskiego poziomu muszą być wykonywane przy użyciu tego rodzaju operacji.

We wszystkich aplikacjach, które wymagają przesyłania danych między dwoma węzłami, takich jak:

  • sieć komputerowa;

  • aplikacje telekomunikacyjne (telefony komórkowe, komunikacja satelitarna itp.).

W warstwie komunikacji niższego poziomu dane są zwykle przesyłane w tzw . Ramkach . Ramki to po prostu ciągi bajtów przesyłane kanałem fizycznym. Te ramki zazwyczaj zawierają rzeczywiste dane oraz kilka innych pól (zakodowanych w bajtach), które są częścią tego, co nazywa się nagłówkiem . Nagłówek zwykle zawiera bajty, które kodują pewne informacje związane ze stanem komunikacji (np. Z flagami (bitami)), licznikami ramek, kodami korekcji i wykrywania błędów itp. Aby uzyskać przesyłane dane w ramce i zbudować ramki do wysyłania danych, na pewno będziesz potrzebować operacji bitowych.

Ogólnie rzecz biorąc, gdy mamy do czynienia z tego rodzaju aplikacjami, dostępne jest API, więc nie trzeba zajmować się wszystkimi tymi szczegółami. Na przykład wszystkie współczesne języki programowania udostępniają biblioteki do połączeń przez gniazdo, więc w rzeczywistości nie trzeba budować ramek komunikacyjnych TCP / IP. Ale pomyśl o dobrych ludziach, którzy zaprogramowali dla ciebie te interfejsy API, na pewno mieli do czynienia z konstrukcją ram; używanie wszelkiego rodzaju operacji bitowych do przechodzenia między komunikacją niskiego poziomu a komunikacją wyższego poziomu.

Jako konkretny przykład wyobraź sobie, że ktoś daje ci plik zawierający surowe dane, które zostały przechwycone bezpośrednio przez sprzęt telekomunikacyjny. W takim przypadku, aby znaleźć ramki, będziesz musiał odczytać surowe bajty w pliku i spróbować znaleźć jakieś słowa synchronizujące, skanując dane bit po bicie. Po zidentyfikowaniu słów synchronizujących będziesz musiał pobrać rzeczywiste ramki i PRZESUNIĄĆ je, jeśli to konieczne (a to dopiero początek historii), aby uzyskać rzeczywiste dane, które są przesyłane.

Inną bardzo odmienną rodziną aplikacji niskiego poziomu jest sytuacja, w której trzeba sterować sprzętem za pomocą (pewnego rodzaju starożytnych) portów, takich jak porty równoległe i szeregowe. Te porty są kontrolowane przez ustawienie niektórych bajtów, a każdy bit z tych bajtów ma określone znaczenie, jeśli chodzi o instrukcje, dla tego portu (patrz na przykład http://en.wikipedia.org/wiki/Parallel_port ). Jeśli chcesz zbudować oprogramowanie, które robi coś z tym sprzętem, będziesz potrzebować operacji bitowych, aby przetłumaczyć instrukcje, które chcesz wykonać, na bajty zrozumiałe dla portu.

Na przykład, jeśli masz kilka fizycznych przycisków podłączonych do portu równoległego, aby sterować innym urządzeniem, jest to wiersz kodu, który można znaleźć w aplikacji:

read = ((read ^ 0x80) >> 4) & 0x0f; 

Mam nadzieję, że to się przyczyni.


Dodałbym en.wikipedia.org/wiki/Bit_banging jako kolejną ścieżkę do zbadania, szczególnie jeśli czytam o portach równoległych i szeregowych jako przykład, w którym operacje bitowe mogą być przydatne.
Dan

6

Mam nadzieję, że to wyjaśnia te dwa:

x | 2

0001 //x
0010 //2

0011 //result = 3

x & 1

0001 //x
0001 //1

0001 //result = 1

4
Ups ... próbowałem być najszybszym pistoletem na zachodzie ... skończył jako idiota, który nawet nie zna binarnego dla dwóch osób :( Naprawiono to.
Amarghosh

1
x & 1nie ilustruje efektu tak dobrze, jak x & 2by to było.
dansalmo,

5

Pomyśl o 0 jako fałszywym i 1 jako o prawdziwym. Następnie bitowe i (&) i lub (|) działają tak samo jak zwykłe i i lub z wyjątkiem tego, że wykonują wszystkie bity wartości naraz. Zazwyczaj zobaczysz je używane jako flagi, jeśli masz 30 opcji, które można ustawić (np. Jako style rysowania w oknie), nie chcesz przekazywać 30 oddzielnych wartości boolowskich, aby ustawić lub usunąć każdą z nich, więc używasz | aby połączyć opcje w jedną wartość, a następnie użyj &, aby sprawdzić, czy każda opcja jest ustawiona. Ten styl przekazywania flag jest intensywnie używany przez OpenGL. Ponieważ każdy bit jest oddzielną flagą, otrzymujesz wartości flag na potęgach dwóch (czyli liczbach, które mają tylko jeden ustawiony bit) 1 (2 ^ 0) 2 (2 ^ 1) 4 (2 ^ 2) 8 (2 ^ 3) potęga dwóch mówi, który bit jest ustawiony, jeśli flaga jest włączona.

Zwróć także uwagę na 2 = 10, więc x | 2 to 110 (6), a nie 111 (7) Jeśli żaden z bitów nie nakłada się (co jest prawdą w tym przypadku) | działa jak dodawanie.


5

Nie widziałem tego wspomnianego powyżej, ale zobaczysz również, że niektórzy ludzie używają lewego i prawego przesunięcia do operacji arytmetycznych. Przesunięcie w lewo o x jest równoważne pomnożeniu przez 2 ^ x (o ile się nie przepełnia), a przesunięcie w prawo jest równoważne podzieleniu przez 2 ^ x.

Ostatnio widziałem ludzi używających x << 1 i x >> 1 do podwojenia i zmniejszenia o połowę, chociaż nie jestem pewien, czy po prostu starają się być sprytni, czy naprawdę mają wyraźną przewagę nad zwykłymi operatorami.


1
Nie wiem o Pythonie, ale w językach niższego poziomu, takich jak C lub nawet niższych - assembler, przesunięcie bitowe jest znacznie bardziej wydajne. Aby zobaczyć różnicę, możesz napisać program w C robiąc to na każdy sposób i po prostu skompilować go do kodu asemblera (lub jeśli znasz język asemblera, to już wiesz :)). Zobacz różnicę w liczbie instrukcji.
0xc0de

2
Mój argument przeciwko używaniu operatorów przesunięcia bitowego byłby taki, że większość współczesnych kompilatorów prawdopodobnie już optymalizuje operacje arytmetyczne, więc spryt jest w najlepszym razie dyskusyjny lub w najgorszym walczy z kompilatorem. Nie mam doświadczenia w C, kompilatorach ani projektach procesorów, więc nie zakładam, że mam rację. :)
P. Stallworth

To powinno być wyższe. Miałem do czynienia z pewnym kodem, który używał operatorów bitowych dokładnie w ten sposób i ta odpowiedź pomogła mi to rozgryźć.
Philippe Oger

4

Zestawy

Zbiory można łączyć za pomocą operacji matematycznych.

  • Operator |sumy łączy dwa zestawy, aby utworzyć nowy zawierający elementy w jednym z nich.
  • Operator przecięcia &pobiera elementy tylko w obu.
  • Operator różnicy -pobiera elementy w pierwszym zestawie, ale nie w drugim.
  • Operator różnicy symetrycznej ^pobiera elementy w obu zestawach, ale nie w obu.

Spróbuj sam:

first = {1, 2, 3, 4, 5, 6}
second = {4, 5, 6, 7, 8, 9}

print(first | second)

print(first & second)

print(first - second)

print(second - first)

print(first ^ second)

Wynik:

{1, 2, 3, 4, 5, 6, 7, 8, 9}

{4, 5, 6}

{1, 2, 3}

{8, 9, 7}

{1, 2, 3, 7, 8, 9}

Ta odpowiedź jest całkowicie niezwiązana z pytaniem i wydaje się, że została skopiowana i wklejona z innego miejsca.
udokumentowano

Pytanie brzmi „Do czego służą operatory bitowe?”. Ta odpowiedź przedstawia mniej znane, ale bardzo przydatne użycie operatorów bitowych.
Taegyung

3

Ten przykład pokaże operacje dla wszystkich czterech wartości 2-bitowych:

10 | 12

1010 #decimal 10
1100 #decimal 12

1110 #result = 14

10 & 12

1010 #decimal 10
1100 #decimal 12

1000 #result = 8

Oto jeden przykład użycia:

x = raw_input('Enter a number:')
print 'x is %s.' % ('even', 'odd')[x&1]

2

Innym częstym przypadkiem użycia jest manipulowanie / testowanie uprawnień do plików. Zobacz moduł statystyczny Pythona: http://docs.python.org/library/stat.html .

Na przykład, aby porównać uprawnienia pliku z żądaną polisą uprawnień, możesz zrobić coś takiego:

import os
import stat

#Get the actual mode of a file
mode = os.stat('file.txt').st_mode

#File should be a regular file, readable and writable by its owner
#Each permission value has a single 'on' bit.  Use bitwise or to combine 
#them.
desired_mode = stat.S_IFREG|stat.S_IRUSR|stat.S_IWUSR

#check for exact match:
mode == desired_mode
#check for at least one bit matching:
bool(mode & desired_mode)
#check for at least one bit 'on' in one, and not in the other:
bool(mode ^ desired_mode)
#check that all bits from desired_mode are set in mode, but I don't care about 
# other bits.
not bool((mode^desired_mode)&desired_mode)

Wyniki oceniam jako wartości logiczne, ponieważ obchodzi mnie tylko prawda lub fałsz, ale warto byłoby wydrukować wartości bin () dla każdego z nich.


1
Mylisz się w ostatnim przykładzie. Oto jak powinien wyglądać tak: not bool((mode ^ desired_mode) & 0777). Lub (łatwiejsze do zrozumienia) not (mode & 0777) ^ desired_mode == 0. AND pozostawi tylko interesujące bity, XOR sprawdzi, jakie wszystkie żądane bity są ustawione. Jawne == 0porównanie jest bardziej znaczące niż bool().
Vadim Fint

Nie sądzę, że jest to specyficzne dla operacji na plikach. Na przykład w PyQt robisz coś podobnego dla setWindowFlags. Przykład: setWindowFlags(SplashScreen | WindowStaysOnTopHint). Nadal uważam to za mylące, ponieważ wydaje się, że przełącznik, który ustawiasz jako „włączony”, wydaje się bardziej intuicyjny w przypadku „i” w takim przypadku.
eric

2

Bitowe reprezentacje liczb całkowitych są często używane w obliczeniach naukowych do reprezentowania tablic informacji prawda-fałsz, ponieważ operacja bitowa jest znacznie szybsza niż iterowanie przez tablicę wartości logicznych. (Języki wyższego poziomu mogą wykorzystywać koncepcję tablicy bitowej).

Ładnym i dość prostym przykładem tego jest ogólne rozwiązanie w grze Nim. Spójrz na kod Pythona na stronie Wikipedii . To sprawia, że intensywne użytkowanie wyłącznych mnożenie lub, ^.


1

Może istnieć lepszy sposób na znalezienie miejsca, w którym element tablicy znajduje się między dwiema wartościami, ale jak pokazuje ten przykład, znak & działa tutaj, podczas gdy i nie.

import numpy as np
a=np.array([1.2, 2.3, 3.4])
np.where((a>2) and (a<3))      
#Result: Value Error
np.where((a>2) & (a<3))
#Result: (array([1]),)

1

nie widziałem tego wspomnianego, ten przykład pokaże operację dziesiętną (-) dla wartości 2-bitowych: AB (tylko jeśli A zawiera B)

ta operacja jest potrzebna, gdy trzymamy w naszym programie czasownik, który reprezentuje bity. czasami musimy dodać bity (jak powyżej), a czasami musimy usunąć bity (jeśli czasownik zawiera wtedy)

111 #decimal 7
-
100 #decimal 4
--------------
011 #decimal 3

z pythonem: 7 i ~ 4 = 3 (usuń z 7 bity reprezentujące 4)

001 #decimal 1
-
100 #decimal 4
--------------
001 #decimal 1

z pythonem: 1 & ~ 4 = 1 (usuń z 1 bity reprezentujące 4 - w tym przypadku 1 nie oznacza „zawiera” 4).


0

Chociaż manipulowanie bitami liczby całkowitej jest przydatne, często w przypadku protokołów sieciowych, które mogą być określone z dokładnością do bitu, można wymagać manipulacji dłuższymi sekwencjami bajtów (które nie są łatwo przekształcane w jedną liczbę całkowitą). W tym przypadku przydatne jest użycie biblioteki bitstring, która pozwala na operacje bitowe na danych - np. Można zaimportować ciąg 'ABCDEFGHIJKLMNOPQ' jako ciąg znaków lub jako szesnastkowo-bitowy przesuwać go (lub wykonywać inne operacje bitowe):

>>> import bitstring
>>> bitstring.BitArray(bytes='ABCDEFGHIJKLMNOPQ') << 4
BitArray('0x142434445464748494a4b4c4d4e4f50510')
>>> bitstring.BitArray(hex='0x4142434445464748494a4b4c4d4e4f5051') << 4
BitArray('0x142434445464748494a4b4c4d4e4f50510')

0

następujące operatory bitowe: & , | , ^ i ~ zwracają wartości (na podstawie ich danych wejściowych) w ten sam sposób, w jaki bramki logiczne wpływają na sygnały. Możesz ich użyć do emulacji obwodów.


0

Aby odwrócić bity (tj. Uzupełnienie / odwrócenie 1), możesz wykonać następujące czynności:

Ponieważ wartość ExORed ze wszystkimi 1s skutkuje inwersją, dla danej szerokości bitowej można użyć ExOR do ich odwrócenia.

In Binary
a=1010 --> this is 0xA or decimal 10
then 
c = 1111 ^ a = 0101 --> this is 0xF or decimal 15
-----------------
In Python
a=10
b=15
c = a ^ b --> 0101
print(bin(c)) # gives '0b101'
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.