WisFaq!

Binaire getallen bewijzen

Hoe kan je bewijzen dat je met het binaire getallenstelsel alle getallen kan schrijven die er bestaan?

Alvast bedankt!

Annemiek

Annemiek
21-11-2007

Antwoord

Hallo, Annemiek.

Het bewijs is dat er een procedure bestaat waardoor men elk gegeven (positief geheel) getal A op unieke wijze schrijft als een som van machten van 2:
1) Vind het grootste gehele getal m (positief of 0), zodat 2^m kleiner of gelijk is aan A.
2) Vervang A door A-2^m, en, als de uitkomst van deze aftrekking nog positief is, ga dan terug naar 1).
Voorbeeld: A=201.
Ga na dat bovenstaande procedure oplevert
201 = 128+64+8+1 = 2⁷+2⁶+2³+2⁰.
De binaire schrijfwijze hangt hier direct mee samen:
200 = 1·2⁷ + 1·2⁶ + 0·2⁵ + 0·2⁴ + 1·2³ + 0·2² + 0·2¹ + 1·2⁰;
je krijgt dan 11001001.
Bij het bewijs hoort ook de opmerking dat de procedure niet oneindig lang doorgaat. Dat komt doordat je van A telkens een macht van 2, dus een positief getal, aftrekt. De uitkomsten van dit aftrekken worden dus steeds kleiner, en de procedure eindigt zodra de uitkomst niet meer positief is. Omdat de uitkomst tevens nooit negatief kan worden, eindigt het altijd netjes op 0.

hr
22-11-2007