Durch 16 teilbare Zweierkomplementzahlen erkennen

Die Aufgabe

Aufgabe 1.4

Woran ist eine durch 16 teilbare Zweierkomplementzahl zu erkennen?

Gesucht ist ein Merkmal der Bitfolge: Woran sieht man, ohne zu rechnen, dass die Zahl ein Vielfaches von 16 ist? Die Aufgabe nennt keine Bitzahl; unsere Beispiele haben 8 Bit, die Regel gilt für jede Länge.

Merke: 16 = 2⁴. Alle Stellenwerte ab 2⁴ sind Vielfache von 16. Ein Rest kann nur von den vier hintersten Bits kommen.

Die Idee am Dezimalsystem.
Positive Zahlen: Stellenwerte ab 2⁴ sind Vielfache von 16.
Negative Zahlen: Die Zweierkomplementbildung ändert die vier hinteren Nullen nicht.

Die Idee im Dezimalsystem

Beispiel 4.700

4{.}700 = \underbrace{4 \cdot 1{.}000 + 7 \cdot 100}_{\text{Vielfache von } 100} + \underbrace{0 \cdot 10 + 0 \cdot 1}_{=\,0}

Eine Dezimalzahl ist durch 100 teilbar, wenn sie auf 00 endet. Der Grund: Die Stellenwerte 100, 1.000, 10.000, … sind alle Vielfache von 100. Nur die letzten zwei Ziffern (Stellenwerte 10 und 1) können einen Rest ergeben.

Aus Skript 1, Folie 1-12 („Zahlen“): Eine Zahl zur Basis B hat den Wert

x = \sum_{i=0}^{n-1} z_i \cdot B^i

: jede Ziffer mal ihrem Stellenwert, alles addiert.

Dual: alles ab 2⁴ ist ein Vielfaches von 16

Stellenwerte ab Stelle 4

2^4 = 16, \quad 2^5 = 2 \cdot 16, \quad 2^6 = 4 \cdot 16, \quad 2^7 = 8 \cdot 16, \;\ldots

x = \underbrace{z_7 \cdot 2^7 + \ldots + z_4 \cdot 2^4}_{\text{Vielfaches von } 16} + \underbrace{z_3 \cdot 8 + z_2 \cdot 4 + z_1 \cdot 2 + z_0 \cdot 1}_{\text{Rest } 0 \,\ldots\, 15}

Im Dualsystem sind die Stellenwerte Zweierpotenzen. 16 ist $2^4$ . Jeder Stellenwert ab Stelle 4 ist $2^4$ mal eine weitere Zweierpotenz, also ein Vielfaches von 16.

Die Stellen 3 bis 0 haben die Stellenwerte 8, 4, 2, 1. Zusammen ergeben sie höchstens 8 + 4 + 2 + 1 = 15, also immer weniger als 16. Sie bilden genau den Rest bei Division durch 16. Ist dieser Rest 0, ist die Zahl durch 16 teilbar, und das geht nur, wenn alle vier Bits 0 sind.

Schritt 0Die Aufgabe

Schritt 1Die Idee im Dezimalsystem

Schritt 2Dual: alles ab 2⁴ ist ein Vielfaches von 16

Abbildung 1Positive Zahlen

Die Aufgabe

Die Idee im Dezimalsystem

Dual: alles ab 2⁴ ist ein Vielfaches von 16