Die meisten Beispiele hier nehmen an dass man auf einer Ganzzahl operiert welche in der ZweierKomplementDarstellung? gespeichert ist. Abweichungen sind jeweils markiert. Binärzahlen werden auf dieser Seite jeweils kursiv dargestellt.

Falls wir die Bits nummerieren, so tun wir dies hier wie folgt für ein Byte:

7 6 5 4 3 2 1 0 Binärzahl Dezimalzahl 0 0 0 0 0 0 0 1 00000001 1 0 0 0 0 1 0 1 0 00001010 10

Zum Zahlen der 1er ist in HAKMEM ITEM 169 ein PDP-6/10 Assembler Hack beschrieben. Er funktioniert folgendermassen:

1. Arrangiere die bits so, dass jede 3ergruppe die Summe der Eingabebits enthaelt.

2. Analog zur Tatsache dass die Quersumme einer Zahl gleich ihrem 9errest ist, solange sie kleiner ist als 9, kann man die Summe dieser 3ergruppen bestimmen in dem man den 7errest nimmt.

Bestimmung des am wenigsten Signifikanten Bits:

Der folgende Code setzt alle Bits, ausser das am wenigsten signifikante welches 1 ist, auf 0.

y = x & (-x);

Zum Beispiel für 12: (12 & -12) = 00001100 & 11110111 = 00000100 = 4 .

Bestimmung des signifikantesten Bits:

Die Bestimmung des signifikantesten Bits ist relativ trickreich. Es gibt verschiedene Varianten. Hier wollen wir gleich die Stelle herausfinden, das heisst wir bestimmen den abgerundeten Zweierlogarithmus der Zahl x. Wir nehmen an das unsere Zahl n bits hat und das die Zahl vorzeichenlos ist.

Variante 1

Diese Variante ist die kanonische und wird nur der Vollständigkeit halber dargestellt. Falls die Zahl x null ist, gibt diese Variante -1 aus.

int log2 = -1; while (x > 0) { ++log2; x = x >> 1; }

Das heisst, wir verschieben die Zahl x so lange nach rechts bis sie 0 wird. Dies kostet genau so viel wie die gesuchte Zahl ist, im schlimmsten Fall also n.

Variante 2

Die Zweite Variante ist im Prinzip binäre Suche nach dem signifikantesten Bit. Sie gibt allerdings 0 aus wenn die Zahl x= 0 ist.

int cnt = n/2; int log = 0; while (x > 0) { int increment = (x >> (cnt + log)) == 0 ? 0 : cnt; log = log + increment; cnt = cnt/2; // (Oder cnt = cnt >> 1); }

Wir demonstrieren die Variante an einem Beispiel für x = 38 = 0000000 00100110, in welchem immer die Werte vor einem Schleifendurchgang sowie die Zahl increment dargestellt sind. Die Anzahl bits sind hier n = 16:

x >> cnt + log cnt log increment 0000000 00000000 8 0 0 0000000 00000010 4 0 4 0000000 00000000 2 4 0 0000000 00000001 1 4 1

Was am Schluss dazu führt das log wie gewünscht 5 ist.

Variante 3

Einige Prozessoren haben eine Instruktion eingebaut um das wichtigste Bit zu finden. Bei einem genügend neuen Intelprozessor sieht das zum Beispiel so aus:

bsr %1, %0

Falls anwendbar ist dies am schnellsten.

Variante 4

Nützlich kann auch sein, auszunutzen dass einige Prozessoren für FliessKommaZahlen? eine spezielle Anweisung eingebaut haben um den zweierlogarithmus zu berechnen. Das könnte dann so aussehen:

float f = x; int log = (int)ilogb(f);

Dies ist mit Vorsicht zu genissen, insbesondere bei grösseren x.

Variante 5

Eine wohl mehr akademische Variante beschreibt A. Brodnik in seinem Paper Computation of the least significant set bit. In Proceedings of the 2nd Electortechnical and Computer Science Conference, Slovenia, 1993. Da wird allerdings gezeigt, wie man das in konstanter Zeit machen kann ohne eine spezielle Instruktion wie in Variante 3 zu haben.

Die im Paper beschriebene Methode kann nun umgebaut werden, um

Prüfung, ob genau 1 Bit gesetzt ist (2^n):

(x & x-1) == 0 ?

Prüfung, ob ab LSB lückenlos 1-Bits vorliegen:

(x & x+1) == 0 ?

y = x & ~(1 << i); // Löschen y = x | (1 << i); // Setzen y = x ^ (1 << i); // Umschalten

Löschen, setzen oder umschalten der Bits i-1 bis 0.

Dies betrifft die i am wenigsten signifikanten Bits:

y = x & ~((1 << i) - 1); // Löschen y = x | ((1 << i) - 1); // Setzen y = x ^ ((1 << i) - 1); // Umschalten

Löschen, setzen oder umschalten der Bits n-1 bis n-i.

Hier ist n die Wortlängen, das heisst bit n-1 ist das signifikanteste Bit. Demnach verändern wir hier die i wichtigsten Bits.

y = x & (-1 >> i); // Löschen y = x | ~(-1 >> i); // Setzen y = x ^ ~(-1 >> i); // Umschalten

Dies wird zum Beispiel verwendet, um festzustellen in welchem Block sich ein bestimmtes Byte einer Datei im UNIX-Dateisystem befindet.

Dividieren und Rest modulo 1024 = 2^10:

quotient = x >> 10; rest = x & 1024-1;

Falls man eine Datei mit x bytes hat, kann man so auch feststellen wieviele Blöcke sie insgesamt benötigt:

blocks= x+1024-1 >> 10;