Bitmanipulation

[albertus]

Guten Tag,

ich bin gerade dabei mich in den Bit-Operatoren einzuarbeiten. Bis jetzt habe ich sie nicht gebraucht jetzt aber ist abzusehen das ich sie brauchen werde.

Auf Stackoverflow.com habe ich folgende zwei Funktionen gefunden um Bits in einem Interger zu löschen und zu setzen. Diese Funktionen funktionieren. Ich nutze diese Funktionen und noch andere Doku um das Prinzip der Bitmanipulation zu verstehen. Anders gesagt ich möchte, das was die Funktionen machen händisch auf Papier nachrechnen können. Hier die beiden Funktionen:

Code: Alles auswählen

def set_bit(value, bit):   return value | (1<<bit)

def clear_bit(value, bit): return value & ~(1<<bit)

Hier das Ergebnis eines Testes:

Code: Alles auswählen

# Lösche im Interger 255 das Bit an Index 3
print("dezimal:", clear_bit_a(255,3), "binär:", bin(clear_bit_a(255,3)))

# Das erfühlt meine Erwartungen

# Setze im Interger 247 das Bit an Index 3
print("dezimal:", set_bit_a(247,3), "binär:", bin(set_bit_a(247,3)))

# Auch das erfühlt meine Erwartungen.

Wenn ich bei der Zahl 247 das 3 Bit Index setzen will kann ich das händisch per Papier und Bleistift nachrechnen, es Funktioniert wie ich es mir dachte. Anders sieht die Sache beim Löschen aus. Hier eine Beispielrechnung die zeigen soll wo es hakt

1. Bitmaske erzeugen:

1 << 3 = 8 = bin(8) = 0b1000

2. Die Bitmaske Invertieren

~8 = -9 = -0b1001

3. Die Maske per & mit der 255 verknüpfen. Hier hagt es, den wenn Wikipedia recht hat dann müsste folgende Rechnung richtig sein:

0b1000
& -0b1001
--------------
0B1000

Das ist aber niemals das was ich erwarten würde. Wo liegt hier mein Denkfehler?

[EyDu]

Dein dritter Schritt ist irgendwie etwas durcheinander. Da steht ``8 & ~8``, das willst du aber wohl gar nicht ausdrücken. Mal für dich schritt weise:

Code: Alles auswählen

28 & ~(1<<3)

Code: Alles auswählen

28 & ~(8)

Code: Alles auswählen

0b11100 & ~(0b1000)

Code: Alles auswählen

0b11100 & 0b1...1110111

Code: Alles auswählen

0b10100

[BlackJack]

@albertus: Der zweite Schritt stimmt schon nicht. `~` bedeutet alle Bits ”umdrehen” und bei 1000₂ kommt dabei ganz sicher nicht 1001₂ heraus, sondern 0111₂. Wenn -9 = 1001₂ wäre, was denkst Du denn was 9 in Binär wäre? Das kann ja nicht das gleiche sein.

[jerch]

@albertus:
Das liegt daran, dass in Python die Ausgabe von `bin` für negative Zahlen anders funktioniert, als Du es erwartest. `bin` schreibt die Binärrepräsentation der positiven Zahl und deutet mit dem '-' an, dass diese negativiert werden muss.
`bin` kann die echte Binärrepräsentation nicht aufschreiben, da es in Python keine festgeschriebene "Bit-Breite" für Zahlentypen gibt und somit das MSB nicht ausdrückbar ist. Abhilfe schafft die Einführung einer Breite bei der Ausgabe:

Code: Alles auswählen

In [1]: f = lambda x, b=8: bin(x & (1<<b) - 1)[2:].zfill(b)

In [2]: f(0)
Out[2]: '00000000'

In [3]: f(1)
Out[3]: '00000001'

In [4]: f(-1)
Out[4]: '11111111'

In [5]: f(-1, 32)
Out[5]: '11111111111111111111111111111111'

In [6]: f(8, 32)
Out[6]: '00000000000000000000000000001000'

In [7]: f(~8, 32)
Out[7]: '11111111111111111111111111110111'

[EyDu]

negativiert

negiert

[albertus]

@albertus: Der zweite Schritt stimmt schon nicht. `~` bedeutet alle Bits ”umdrehen” und bei 1000₂ kommt dabei ganz sicher nicht 1001₂ heraus, sondern 0111₂. Wenn -9 = 1001₂ wäre, was denkst Du denn was 9 in Binär wäre? Das kann ja nicht das gleiche sein.

Genau das würde ich ja auch erwarten wenn ich in IDLE (Version 3.5.5) genau das eingebe:

>>> ~8
-9
>>>

deshalb bin ich ja so verwirrt

[EyDu]

Das ist alles nur eine Frage der Darstellung. ``~8`` ist exakt das selbe wie ``-9``. Und, wie jerch schon schrieb, stellt Python negative Binärzahlen nicht im Zweierkomplement dar, sondern mittels Vorzeichen. Für 9 also 0b1001 und -9 entsprechend -0b1001. Andernfalls müssten unendlich viele Einsen direkt nach dem b ausgegeben werden, da Python beliebig lange Integer unterstützt. Die Ausgabe würde aber etwas lange dauern Wandle also, mit dem Code von jerch, deine Zahlen einfach per Hand in eine binäre Darstellung um.

[albertus]

@albertus:
Das liegt daran, dass in Python die Ausgabe von `bin` für negative Zahlen anders funktioniert, als Du es erwartest. `bin` schreibt die Binärrepräsentation der positiven Zahl und deutet mit dem '-' an, dass diese negativiert werden muss.

`bin` kann die echte Binärrepräsentation nicht aufschreiben, da es in Python keine festgeschriebene "Bit-Breite" für Zahlentypen gibt und somit das MSB nicht ausdrückbar ist. Abhilfe schafft die Einführung einer Breite bei der Ausgabe:

Code: Alles auswählen

In [1]: f = lambda x, b=8: bin(x & (1<<b) - 1)[2:].zfill(b)

Guten Abend jerch,

gerade ist bei mir im Kopf ein Kronleuchter angegangen jetzt sehe ich so einiges klarer.

Danke

[albertus]

Erst mal Danke an alle,

jetzt verstehe ich wie man Bits setzt, löscht und abfragt. Das ist schon eine Menge mehr, als noch vor 5 Tagen .

Aber da ich gerade beim Fragen bin . Bei den Bits gibt es ein MSB und dieses ist bei allen CPU Typen die ich kenne links. Gibt es eigentlich auch CPUs bei denen das genau andersherum ist? Bei den Bytes ist das ja bekannt (Sichtwort: Big-Endiann, Little-Endiann) aber für Bits habe ich trotz vieler Google Suchanfragen, nicht sehr viel in Erfahrung bringen können.

[jerch]

@albertus:
Was ist links und was rechts in der CPU? Register, ALU, Busse, Speicher? Die Endianess bezieht sich idR auch auf die Bitreihenfolge der Maschinen, so sind wohl alle little endian Maschinen auch LSB0, während die big endian häufig MSB0 sind.
Auf Programmierebene stört die Bitreihenfolge im Gegensatz zur Bytereihenfolge weniger, da Operationen wie Shifts unabhängig von der Ausrichtung am Effekt normiert sind (Linksshift verschiebt immer in Richtung MSB, egal ob der jetzt "links" oder "rechts" ist.) Kann natürlich sein, dass es Mikrocontroller gibt, die sich da nicht dran halten.

[BlackJack]

@albertus: Definiere bitte mal ”links” in diesem Zusammenhang. Und vor allem was das mit der CPU zu tun haben soll‽ Und was dort dann ”links” und ”rechts” wäre? Menschen schreiben Zahlen, egal zu welcher Basis, in unserem Kulturraum immer mit der höchstwertigen Ziffer beginnend. Das hat rein gar nichts mit Rechnern zu tun.

[albertus]

@albertus: Definiere bitte mal ”links” in diesem Zusammenhang. Und vor allem was das mit der CPU zu tun haben soll‽ Und was dort dann ”links” und ”rechts” wäre?

Du hast natürlich recht Links und Rechts machen bei einer CPU so keinen Sinne, ich habe es bildlich gemeint. Auf folgender Webseite: http://www.mikrocontroller.net/articles/Digitaltechnik habe ich dazu folgendes gefunden:

In der üblichen Schreibweise (INTEL) werden die einzelnen Bits von rechts nach links abgezählt. "MSB" nennt man das höchstwertige Bit (ganz links, Bit 7), "LSB" das niederwertigste (ganz rechts, Bit 0).

Auf dem PowerPC ist es umgekehrt, dort ist Bit #0 das MSB (links) und Bit 7/15/31/63 ganz rechts das LSB.

so war meine Vorstellung und ich bin davon ausgegangen das es bei anderen auch so ist was wohl nicht stimmte.

Aber wie jerch schon sagte:

Auf Programmierebene stört die Bitreihenfolge im Gegensatz zur Bytereihenfolge weniger, da Operationen wie Shifts unabhängig von der Ausrichtung am Effekt normiert sind (Linksshift verschiebt immer in Richtung MSB, egal ob der jetzt "links" oder "rechts" ist.)

die Exoten interessieren mich nicht und wenn dem nichts hinzufügen ist, dann kratzt mich die Bit-Reihenfolge nicht wirklich

Menschen schreiben Zahlen, egal zu welcher Basis, in unserem Kulturraum immer mit der höchstwertigen Ziffer beginnend. Das hat rein gar nichts mit Rechnern zu tun.

Was eindeutig ein Fehler wahr, als die Arabischen Zahlen in unserem Kulturraum eingeführt wurden. Den die Araber schreiben von rechts nach links

[BlackJack]

@albertus: Ich kann mir kaum vorstellen das jemand ernsthaft Binärzahlen ”falsch” herum aufschreibt, weil das sehr verwirrend ist diese eine Zahlenbasis anders zu schreiben als Zahlen in allen anderen Basen.

Die arabischen Zahlen sind eigentlich indische Zahlen. Keine Ahnung ob da von links nach rechts geschrieben wurde, aber falls ja, dann wäre das umkehren der Schreibrichtung in ein Schriftsystem das von rechts nach links geschrieben wird nicht per se ein Fehler.