BCD Zahlen in Binärdarstellung umwandeln

Gegeben Sei eine BCD codierte ganze positive Zahl. Sie soll in Binärdarstellung umgewandelt werden.

Bei BCD (binary coded decimal) codierte Zahlen werden die Dezimalziffern jeweils mit 4 Bits codiert (0000 bis 1001). Die restlichen Bitkombinationen bleiben ungenutzt. Wir betrachten nur 16 Bit-Wortbreite.

Die BCD-Codierung der Dezimalzahl 532  ist 0000 0101 0011 0001

Implementieren Sie ein Programm, welches ganze Zahlen im BCD Format in Binärdarstellung konvertiert.

Geben Sie nach Möglichkeit genau einen arithmetischen Ausdruck an, der eine BCD Zahl in Binärdarstellung überführt.

Rechnen mit ganzen Zahlen

Bei Algorithmen, die nach dem Teile-und-Beherrsche-Prinzip vorgehen oder bei Halbierungsverfahren, muss meist die Mitte eines Bereichs (eines Felds) berechnet werden. Der Bereich ist oft durch seine linke untere und rechte obere Grenze definiert. Dies sieht dann meist so aus:

int mitte = (links + rechts) / 2;

Diese Berechnung funktioniert in Java und anderen Programmiersprachen nicht immer. Was passiert, wenn die rechte Grenze sehr gross wird und der Bereich sich sehr weit rechts befindet? Wie muß die Mitte in Java berechnet werden, damit in jedem Fall das Ergebnis der Berechnung stimmt?

Dieser Fehler findet sich häufig in Lehrbüchern aber auch in Programmbibliotheken. In der Java-Version 1.6 wird in der Klasse Arrays die Mitte für die Binärsuche wie folgt berechnet (dabei ist aus Geschwindigkeitsgründen die Division durch 2 durch einen Rechts-Shift ersetzt):

int mid = (low + high) >>> 1;