B-adisch / Hornerverfahren

Eine B-adische Darstellung schreibt eine Zahl n als Summe von Potenzen einer Basis B ≥ 2 mit Ziffern aus der Menge {0, …, B − 1}: n = ∑ b_i · Bⁱ, kompakt als (b_k … b₀)_B notiert. Bekannte Beispiele sind das Binärsystem mit B = 2 (Ziffern 0 und 1), das Oktalsystem mit B = 8 (Ziffern 0 bis 7), das Dezimalsystem mit B = 10 (Ziffern 0 bis 9) und das Hexadezimalsystem mit B = 16 (Ziffern 0 bis 9 sowie A bis F). Um eine Dezimalzahl in eine B-adische Darstellung umzuwandeln, nutzt man das Hornerverfahren mit wiederholter ganzzahliger Division durch B; die Reste werden von unten nach oben gelesen und ergeben die Ziffern. Beispielsweise gilt 185 ÷ 8 = 23 Rest 1, 23 ÷ 8 = 2 Rest 7 und 2 ÷ 8 = 0 Rest 2, also 185 = (271)₈. Umgekehrt erhält man eine Dezimalzahl aus einer B-adischen Darstellung, indem man Ziffer mal Bⁱ über alle Positionen summiert: (271)₈ = 2 · 64 + 7 · 8 + 1 = 185. Weil 8 = 2³ und 16 = 2⁴ gilt, lassen sich Binär- und Oktal- bzw. Hex-Darstellungen schnell stellenweise umrechnen, indem man jeweils 3 oder 4 Binärziffern zu einer Oktal- bzw. Hexziffer zusammenfasst, ausgehend vom niederwertigsten Bit rechts.