Gehele getallen, binair

Gehele getallen, binair

Hierboven zagen we een binaire voorstelling voor natuurlijke getallen. We kunnen echter ook negatieve getallen binair voorstellen. De meest gangbare aanpak hiervoor is de zogenaamde 2-complementsnotatie. Hierbij wordt een negatief getal voorgesteld met oneindig veel 1-bits:

0  = ...0...000
1  = ...0...001
2  = ...0...010
3  = ...0...011
-1 = ...1...111
-2 = ...1...110
-3 = ...1...101
-4 = ...1...100
-5 = ...1...011

We kunnen zo'n voorstelling bestaande uit oneindig veel cijfers (maar waarbij de cijfers, afgezien van een eindig aantal, allemaal gelijk zijn aan 0 of allemaal gelijk zijn aan 1), voorstellen in OCaml als volgt:

type Z =
  Teken of bool
| Cijfer of bool * Z

Met het sleutelwoord type definiëren we in OCaml een nieuw type. Het type Z heeft twee constructoren: de constructor Teken neemt als enige argument een Booleaanse waarde, en de constructor Cijfer neemt twee argumenten: een Booleaanse waarde en een andere waarde van Z.

De waarde Teken b stelt de binaire voorstelling voor, bestaande uiteindig veel keren het cijfer b. De waarde Cijfer (b, z) stelt de binaire voorstelling voor beginnende met die van z en gevolgd door het cijfer b als minst significante cijfer.

We kunnen dit type gebruiken om gehele getallen voor te stellen als volgt:

0  = ...0...000 = Teken false
1  = ...0...001 = Cijfer (true, Teken false)
2  = ...0...010 = Cijfer (false, Cijfer (true, Teken false))
3  = ...0...011 = Cijfer (true, Cijfer (true, Teken false))
-1 = ...1...111 = Teken true
-2 = ...1...110 = Cijfer (false, Teken true)
-3 = ...1...101 = Cijfer (true, Cijfer (false, Teken true))
-4 = ...1...100 = Cijfer (false, Cijfer (false, Teken true))
-5 = ...1...011 = Cijfer (true, Cijfer (true, Cijfer (false, Teken true)))