Bit-Level Programmierung @ PS-Trainer

Bitwise in Programmiersprachen

BitLevel-Operatoren:

Fast alle modernen Programmiersprachen verwenden für Bit-Operationen ähnliche Operatoren (Tabelle rechts).

Beachten sie den Unterschied zu den ähnlich aussehenden Vergleichs-Operatoren (nächster Absatz) oder zu → Regulären Ausdrücken !

BitLevel-Operatoren werden meist auf Ganze Zahlen (Byte, Integer) unterschiedlicher Länge (8,16,32.. Bit) angewendet und ergeben jeweils genau 1 Ergebnis der gleichen Länge.
Die Anwendung auf Gleitkomma-Variable ( → IEEE-754) ist möglich, erfordert jedoch genaue Kenntnisse der internen Struktur.
Selten (Kryptografie, Berechnung der CRC-Kontrollsumme) werden diese Operatoren auf Strings angewendet.

♦ Live-Demo der BitLevel Verknüpfungs-Operatoren.
♦ Live-Demo der Shift-Operatoren

BitLevel-Operatoren (allgemein) - Die Syntax einzelner Programmiersprachen kann abweichend lauten !

Operator		Beispiel
NOT	~	r = ~a
AND	&	r = a & b
OR	\|	r = a \| b
XOR	^	r = a ^ b
ASR	>>	r = a >> n
ASL	<<	r = a << n

Vergleichs-Operatoren:

Diese Operatoren verwenden ähnliche Zeichen und werden daher häufig mit den teilweise gleichnamigen Bit-Level Operatoren verwechselt.
• Mit Vergleichs-Operatoren wird die Bedingung für eine Verzweigung (Wenn - Dann) oder für eine Schleife ermittelt. Das Ergebnis ist ein logischer Wert (true oder false), d.h. immer ein 1-Bit Wert.
• Je nach Programmiersprache kann man das Ergbnis an logische (Bool-)-Variable zuweisen oder als Zahlen (0 oder 1) an numerische (Integer)-Variable.
• Der Operator GT steht hier stellvertretend für die ganze Gruppe (GE >=,GT >,LE <=,LT < ).

Vergleichs-Operatoren sind keine Bit-Level Operatoren. Sie ergeben immer ein "logisches" 1-Bit Ergebnis:

Operator		Beispiel
EQ	==	if(a==b) {...}
NE	!=	if(a!=b) {...}
GT	>	if(a>b) {...}
AND	&&	if(a>0 && b<0) {...}
OR	\|\|	if(a>0 \|\| b<0) {...}

Priorität

Bitwise-Operatoren haben in allen Programmiersprachen sehr geringe Priorität.
► Vewenden sie daher bei Bit-Rechnungen im Zweifel immer ( Klammern ).

Sicher:

r = (x AND y) + z

Unsicher:

r = x AND y + z

Speicher-Breite

Wenn bei einer arithmetischen oder logischen Operation die vereinbarte Speicher-Größe überschritten wird, kann das Ergebnis je nach verwendeter Programmiersprache (evtl. sogar nach Version) variieren !

● Ein besonders sensibler Fall ist die Bit-Umkehrung (BitLevel NOT) positiver Zahlen. Ihre binäre Darstellung enthält theoretisch unendlich viele führende 0-Bits. Praktisch ist die Anzahl führender 0-Bits durch die vereinbarte Speicher-Größe (z.B. 8,16,32,64 Bit) begrenzt. Moderne Programmiersprachen ohne ausdrückliche Typ-Vereinbarung entscheiden selbst die benötigte Speicher-Größe !
Die Bit-Umkehrung verwandelt jedes 0-Bit in ein 1-Bit. Bei dynamischer Speichergröße ergibt das eine unbekannte Anzahl führender 1-Bits und damit eine gefährliche Fehlerquelle !

Abhilfe:

Begrenzen sie nach jeder verdächtigen Operation die Speicherbreite.
Bei Verarbeitung einzelner Bytes wird das Ergebnis mit 255.=#FF auf BitLevel AND-verknüpft, bei Verarbeitung von 2-Byte Worten mit #FFFF usw.

Beispiel: Bit-Inversion mit nachfolgender Begrenzung auf die signifikate Anzahl (8) Bits.

n = -5
m = ~n

m = m & 255

Theoretisch ist auch der umgekehrte Fall möglich: Sie müssen dann fehlende führende 1-Bits mit einer OR-Verknüpfung ergänzen.

Vorzeichen

Negative ganze Zahlen werden zum Speichern in eine spezielle Form gebracht, das → 2er-Komplement. Dadurch hat man Vorteile beim Rechnen auf Prozessor-Ebene.

♦ Details und Live-Demo zum 2er-Komplement

Maschinensprache

Der Befehls-Satz gängiger Prozessoren umfasst stets alle BitLevel-Operatoren. Im Gegensatz zu höheren Programmiersprachen werden diese Befehle in Maschinensprache ('Assembler') häufig angewendet.

Je näher zur Hardware (Register) sie gelangen, desto mehr müssen sie sich mit Befehlen auf Bit-Ebene auseinandersetzen.

Kalkulations-Programme und Basic (LibreOffice-Basic, Visual Basic, VBA)
Ein Standard Kalkulations-Programm (z.B. LibreOffice, MS-Excel, ...) ist auf fast jedem PC installiert. Man kann es mit Unterstützung einiger → Basic-(VBA)-Funktionen gut für einfache BitLevel-Experimente verwenden. Das erfordert keine besonderen Resourcen und bietet in kurzer Zeit anschauliche Ergebnisse.	Weder Kalkulations-Programme noch die Programmiersprache Basic bieten in der Standard-Version brauchbare Operatoren oder Funktionen. Die zusätzlichen Funktionen sind daher relativ umfangreich und werden auf einer → eigenen Webseite vorgestellt: ♦ Details zu BitLevel-Funktionen in Kalkulations-Programmen und Basic (VBA).

C/C++

C/C++ ist die klassische Programmiersprache für Low-Level Anwendungen und bietet alle Möglichkeiten zur Programmierung auf BitLevel, jedoch leider keine Funktion zur binär formatierten → Ausgabe von Variablen. Eine derartige Funktion zur Ausführung eigener Experimente wird im nächsten Absatz demonstriert.

Die Tabelle rechts zeigt die in C/C++ verwendeten BitLevel Operatoren (rot) mit Beispielen.

♣ Beachten sie in eigenen Programmen immer die Werte allfälliger führender Bits, auch dann wenn sie die diese im Programm nicht verwenden. Durch Verknüpfung mit AND kann man allfällig führende 1-Bits sicher löschen, durch Verknüpfung mit OR kann man allfällige 0-Bits sicher auf =1 setzen.
♣ Bei Shift-Operationen geht das austretende (Carry)-Bit verloren, an der gegenüber liegenden Stelle wird ein 0-Bit eingesetzt.

BitLevel-Opertaoren in C/C++

Operator	Syntax	Beispiel
NOT	r = ~a	~1010 = 0101
AND	r = a & b	1010 & 1100 = 1000
OR	r = a \| b	1010 \| 1100 = 1110
XOR	r = a ^ b	1010 ^ 1100 = 0110
ASR	r = b >> n	1100 >> 1 = 0110
ASL	r = b << n	1100 << 1 = 1000

Ausgabe im Binär-Format

Das Beispiel rechts stellt die Funktion binstr8() vor, die sich für Experimente auf BitLevel eignet.

► Programm main()
• Die Variable sb deklariert einen String (Array vom Typ char der Länge 9), welcher zur Aufnahme der Binär-Strings dient.
• Die Variablen ia,ib erhalten die angegebenen Bitmuster. Nur das niedrigstwertige Byte (die Bits 0...7 von rechts) wird hier verwendet.
• Ihre Werte werden an der Konsole ausgegeben, und zwar dezimal und mit Hilfe der Funktion binstr8() als String (Text, Zeichenkette von '0' und '1'-Zeichen.
• Danach wird die Anwendung der BitLevel-Operatoren & | ~ demonstriert, und das Ergebnis in der Variablen ir ebenfalls dezimal und als Binär-String ausgegeben.

► Funktion binstr8()
Die Funktion erwartet 2 Argumente.
• Das 1. Argument ipat vom Typ int ist jenes Bitmuster (als ganze Zahl), welches in einen Binär-String umgewandelt werden soll.
• Das 2. Argument *s ist ein Pointer auf einen String, der Platz für mindestens 9 Zeichen haben muss.
• Das Muster wird in einer for-Schleife analysiert, und zwar je 1 Bit in jedem Durchgang der Schleife.
• Das höchstwertige Bit Nr.7 des untersuchten Bytes wird mittels AND-Verknüpfung isoliert und durch RightShift um 7 Binär-Stellen an die niedrigst-wertige Position (Bit 0) gebracht.
• Der → ASCII-Code der Zeichen '0','1' beträgt dezimal 48,49, daher wird an die vom Pointer *s angegebene Adresse der Wert '0' + isoliertes Bit geschrieben. Unmittelbar danach wird der Pointer *s mit dem Operator ++ auf die nächste String-Adresse gesetzt.
• Danach werden die Bits der Variablen ipat mit LeftShift um 1 Binär-Stelle nach links verschoben: Das ist die Vorbereitung für die Analyse des nächsten Bits.
• Nach Ende der Schleife wird der String mit einem 0-Byte abgeschlossen.
• Zuletzt wird (optional) der gleiche Pointer zurückgegeben, der als 2.Argument erhalten wurde.

C-Experimente auf BitLevel, z.B. als Quelltext-Datei bintest.c :

#include <stdio.h>

char* binstr8(int,char*);

int main() {

char sb[9];
int ia,ib,ir;

// Bitmuster

ia = 0xAA; // 0b10101010
ib = 0xF0; // 0b11110000
binstr8(ia,sb);
printf("ia = %3d = 0b%s\n",ia,sb);
binstr8(ib,sb);
printf("ib = %3d = 0b%s\n",ib,sb);

// Verknuepfung

ir = ia & ib;
printf("ia & ib = 0b%s\n",binstr8(ir,sb));
ir = ia | ib;
printf("ia | ib = 0b%s\n",binstr8(ir,sb));
ir = ~ia;
printf("~ia = 0b%s\n",binstr8(ir,sb));
return 0;

}

char* binstr8(int ipat,char *s) {

int i,j;
char *t;
t = s;
for(i=0;i<8;i++) {

j = (ipat & 0x80)>>7;
*s ++= j + 48;
ipat<<=1;

}
*s=0;
return t;

}

■ Anwendung:
Das aufrufende Programm (hier: main() ) muss einen String der Länge>=9 bereitstellen (hier die Variable sb ).
• Man kann die Funktion binstr8() alleinstehend aufrufen, wie zur Ausgabe der Bitmuster demonstriert. Da die Funktion (optional) einen String-Pointer zurückgibt, kann man sie auch als Argument der → Ausgabe-Funktion printf() verwenden, wie zur Ausgabe der Verknüpfungs-Ergebnisse ir gezeigt.
• Die Funktion binstr8(ir,sb) analysiert die untersten 8 Bit des 1.Arguments und schreibt den erzeugten Binär-String in die als Pointer erhaltene String-Variable. Im Beispiel wird vom Programm immer der gleiche String sb verwendet, alternativ kann man beliebig viele verschiedene Strings verwenden.
♣ Die erzeugten Strings sind nur zur Ausgabe sinnvoll, man kann damit nicht rechnen !

Ausgabe:

ia = 170 = 0b10101010
ib = 240 = 0b11110000
ia & ib = 0b10100000
ia | ib = 0b11111010
~ia = 0b01010101

♣ Anregung: Probieren sie auch andere Bitmuster aus, z.B.

ia=0x8000; ia=1; ib=0x0F;

♣ Probieren sie auch andere BitLevel-Operatoren, z.B.

XOR(^), ASL(<<), ASR(>>)

Javascript

JavaScript bietet alle Standard BitLevel-Operatoren.
Die Live-Funktionen aller Demo-Seiten dieses Webs (→ Bool-Operatoren, → Shift-Operatoren, → 2er-Komplement) sind in Javascript programmiert.

● Javascript bietet die Möglichkeit, mit der Funktion parseInt() einen String von Binär-Daten in Zahlenwerte umzuwandeln. Das optionale 2.Argument dieser Funktion akzeptiert u.a. die Zahl 2 für das binäre Zahlensystem. Beispiel:

var x = parseInt("1011",2);

ergibt x = 11.0
(Dezimalzahlen werden hier zur besseren Unterscheidung mit 1 Nachkommastelle angegeben)

● Javascript bietet mit der Methode toString() die Möglichkeit, einen Zahlenwert als Binär-String auszugeben. Das Zahlensystem wird als optionales Argument angegeben. Beispiel:

var x = 11;
var t = x.toFixed(1) + " = 0b" + x.toString(2);

ergibt den String: 11.0 = 0b1011

BitLevel-Opertaoren in Javascript

Operator	Syntax	Beispiel
NOT	r = ~a	~1010 = 0101
AND	r = a & b	1010 & 1100 = 1000
OR	r = a \| b	1010 \| 1100 = 1110
XOR	r = a ^ b	1010 ^ 1100 = 0110
ASR	r = b >> n	1100 >> 1 = 0110
ASR	r = b << n	1100 << 1 = 1000

Die rechts (vereinfacht) vorgestellte Javascript-Funktion js_bintest() ist im Quelltext dieser Webseite enthalten:

der JavaScript Funktion js_bintest()

• Zunächst werden die Werte der beiden Test-Variablen a,b als ganze Zahlen interaktiv eingegeben. Man kann ganze dezimale Werte eingeben, mit führender 0 octale Werte (z.B. 0177) oder mit führenden Zeichen 0x hexadezimale Werte (z.B. 0xF0).
Im Live-Test werden die Werte auf positive ganze Zahlen 0..255 abgeschnitten.

• Danach werden die BitLevel Operatoren auf eine der Variablen a,b oder auf beide angewendet. Das Ergebnis (in der Variablen r ) wird dezimal und binär ausgegeben und als String in der Variablen t gespeichert.

• Zuletzt wird der fertige String in einem Alarm-Fenster ausgegeben.

♣ Führende 0-Bits werden von der Methode toString() nicht ausgegeben ! - Sie werden in der Live-Variante der Funktion dazugefügt.

Live-Experiment mit den Javascript BitLevel-Funktionen:

function js_bintest() {

var a = parseInt(prompt("ia=","0xAA"));
var b = parseInt(prompt("ib=","0xF0"));
var t = "Live-Test mit JavaScript:";
t = "\ta=" + a + " = " + a.toString(2);
t += "\nb=" + b + " = " + b.toString(2);
var r = ~a;
t += "\n~a = " + r + " = " + r.toString(2);
r = a & b;
t += "\na & b = " + r + " = " + r.toString(2);
r = a | b;
t += "\na | b = " + r + " = " + r.toString(2);
r = a ^ b;
t += "\na ^ b = " + r+ " = " + r.toString(2);
r = b >> 1;
t += "\nb >> 1 = " + r + " = " + r.toString(2);
r = b << 1;
t += "\nb << 1 = " + r + " = " + r.toString(2);
alert(t);

}

Die Live verwendete Funktion bietet zusätzlich Möglichkeiten, mit führenden Zeichen 0b Binär-Strings einzugeben, sowie mit führenden Zeichen # oder 0x hexadezimale Werte-Strings.

Perl

Perl bietet alle Standard BitLevel Operatoren, und darüber hinaus bequeme Funktionen zur Ein- und Ausgabe von Binär-Strings, sowie zur Codierung und Decodierung von Binärzahlen.

● Mit Prefix (vorangestellte Zeichen) 0b kann man binäre Werte direkt im Quelltext eingeben. Beispiel:

$x = 0b10101010;

ergibt $x= 170.0
♦ Details zur Verwendung von Zahlen in Perl

● Die Standard Perl Funktionen → printf() und sprintf() bieten mit %b einen Platzhalter zur Ausgabe binär formatierter Zahlen, z.B.

printf("x = 0b%08b",$x);

ergibt die Ausgabe x = 0b10101010
♦ Details zur Codierung von Zahlen-Strings in Perl

BitLevel-Opertaoren in Perl

Operator	Syntax	Beispiel
NOT	$r = ~$a	~1010 = 0101
AND	$r = $a & $b	1010 & 1100 = 1000
OR	$r = $a \| $b	1010 \| 1100 = 1110
XOR	$r = $a ^ $b	1010 ^ 1100 = 0110
ASR	$r = $b >> $n	1100 >> 1 = 0110
ASR	$r = $b << $n	1100 << 1 = 1000

Vorsicht vor Verwechslung mit den ähnlich aussehenden Vergleichs-Operatoren und Operatoren für → Reguläre Ausdrücke !

ActivePerl Manual: Kapitel perlop

● Perl verwendet für Ganze Zahlen (derzeit) meist 32 Bit Breite. Das kann man durch Einstellung von Optionen beim Compilieren ändern. Zukünftige Versionen können auch andere Speicher-Größen verwenden. Man sollte sich darauf nicht verlassen, sondern in kritischen Fällen die gewünschte Breite selbst festlegen oder zumindest kontrollieren.

● Für BitLevel-Operationen wird ohne besondere Vereinbarung der Typ unsigned Integer verwendet. Man kann einen eigenen Block anlegen, innerhalb dessen z.B. signed Integer gilt.

{

use integer;

}

Außerhalb des Blocks gilt weiterhin unsigned Integer
Integer Wortbreite je nach Compilierung, dzt. meist 32 Bit.

Die Standard Perl Funktion → pack() kann man u.a. dazu verwenden, um Daten von beliebigen BitMustern zu erzeugen, z.B für 2 Variable der Type Short Integer (S) und 1 Variable der Type Long Integer (L):

$t = pack('S',1);
dump_bytes($t);
$t = pack('S',256);
dump_bytes($t);
$t = pack('S',65535);
dump_bytes($t);
$t = pack('L',0x10203040);
dump_bytes($t);

Ausgabe:

(2 Byte): 01 00
(2 Byte): 00 01
(2 Byte): FF FF
(4 Byte): 40 30 20 10

(Beachten sie die interne Darstellung in umgekehrter Reihenfolge).
♦ Details zur Binär-Codierung und Decodierung in Perl

Die Standard Funktion unpack() gibt eine Liste der gewünschten Variablen-Typen (hier einzelne Bytes) zurück. Sie wird im Beispiel an ein Array zugewiesen und

sub dump_bytes() {

my($x) = @_;
my($v,@ua);
print '('.length($x).' Byte):';
@ua = unpack('C*',$x);
foreach $v(@ua) {

printf(' %02X',$v & 0xFF);

}
print "\n";

}

Die Perl-Funktion dump_bytes() zeigt die Bytes der als Argument übergebenen Variablen hexadezimal an.

PHP

PHP bietet alle Standard BitLevel Operatoren, und darüber hinaus bequeme Funktionen zur Ausgabe von Binär-Strings, sowie zur Codierung und Decodierung von Binärzahlen.

● Die Standard PHP Funktionen → printf() und sprintf() bieten mit %b einen Platzhalter zur Ausgabe binär formatierter Zahlen, z.B.

printf("x = 0b%08b",$x);

ergibt die Ausgabe x = 0b10101010

BitLevel-Opertaoren in PHP

Operator	Syntax	Beispiel
NOT	$r = ~$a	~1010 = 0101
AND	$r = $a & $b	1010 & 1100 = 1000
OR	$r = $a \| $b	1010 \| 1100 = 1110
XOR	$r = $a ^ $b	1010 ^ 1100 = 0110
ASR	$r = $b >> $n	1100 >> 1 = 0110
ASR	$r = $b << $n	1100 << 1 = 1000

● PHP verwendet für ganze Zahlen normalerweise Variable vom Typ Integer mit 32 Bit Speicher-Breite.

● Wenn eine Zahl über diesen Bereich hinausgeht, oder wenn im Laufe einer Rechnung ein Gleitkomma-Resultat auftritt, dann wird ungefragt der Gleitkomma-Typ Double verwendet.

Manual: Kapitel Language Reference | Operators | Bitweise Operators

● Die Standard-Funktione pack() wird genauso wie in ↑ Perl verwendet.

$t = pack('S',1);
dump_bytes($t);
$t = pack('S',256);
dump_bytes($t);
$t = pack('S',65535);
dump_bytes($t);
$t = pack('L',0x10203040);
dump_bytes($t);

Ausgabe (auf einer Webseite):

(2 Byte): 01 00
(2 Byte): 00 01
(2 Byte): FF FF
(4 Byte): 40 30 20 10

Beachten sie die Ausgabe der Daten in der intern gespeicherten (umgekehrten) Reihenfolge.

● Die Standard-Funktione unpack() gibt ein → Array der gewünschten Variablen-Typen zurück, z.B.

function dump_bytes($x) {

print '('.strlen($x).' Byte):';
$ua = unpack('c*',$x);
foreach($ua as $v) {

printf(' %02X',$v & 0xFF);

}
print "<br />\n";

}

Die PHP-Funktion dump_bytes() zeigt die Bytes des als Argument übergebenen Variablen hexadezimal an.

BitLevel	Operationen auf Bit-Ebene
Live-Demo	Bitmuster, Operatoren NOT, AND, OR
Shift-Operatoren	LSL, LSR, ASL, ASR, ROL, ROR, SWAP
Vorzeichen	Negative Zahlen, 2er-Komplement
Kalkulation	Benutzer-definierte Basic-Funktionen
Basic	LibreOffice-Basic, Visual Basic (VBA): Hilfs-Funktionen
Auf dieser Seite:
Programmierung	Operatoren, Priorität, Speicher-Breite
Binär-Strings	Simulation aller BitLevel-Funktionen mit Strings
BitLevel-Rechnung	Arithmetische Berechnung
C/C++	Bietet alle Standard-Operatoren
Javascript	Live-Test: Alle Standard-Operatoren
Perl	Bietet alle Standard-Operatoren
PHP	Bietet alle Standard-Operatoren
Verwandte Themen	Interne Darstellung: Gleitkomma-Zahlen, Zeichencodes Umwandlung Strings ↔ (Binär)-Zahlen

Programmierung auf Bit-Level

Die Bit-Level Möglichkeiten von Programmiersprachen

Bitwise in Programmiersprachen

BitLevel-Operatoren:

Vergleichs-Operatoren:

Priorität

Speicher-Breite

Vorzeichen

Maschinensprache

Kalkulations-Programme und
Basic (LibreOffice-Basic, Visual Basic, VBA)

C/C++

Ausgabe im Binär-Format

Javascript

Perl

PHP

Programmierung auf Bit-Level

Die Bit-Level Möglichkeiten von Programmiersprachen

Bitwise in Programmiersprachen

BitLevel-Operatoren:

Vergleichs-Operatoren:

Priorität

Speicher-Breite

Vorzeichen

Maschinensprache

Kalkulations-Programme und Basic (LibreOffice-Basic, Visual Basic, VBA)

C/C++

Ausgabe im Binär-Format

Javascript

Perl

PHP

Kalkulations-Programme und
Basic (LibreOffice-Basic, Visual Basic, VBA)