Działanie i użycie bitowe

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.

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

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

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.

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.

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

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.

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.

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}

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]

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.

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, ^.

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]),)

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

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

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.

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'