ÜbungBaut auf Katas: Dictionaries auf

icon: bi-toggles kind: uebung duration: 1 Doppelstunde languages: [ruby, python, javascript] idea: Zahlen in Bits, im Sechzehnersystem und in jedem anderen curriculum: "Sek I: Information und Daten (Zahlensysteme, Codierung)" requires: [kata-dicts]

Katas: Bits und Zahlensysteme

Du schreibst Funktionen, die Zahlen in Bits zerlegen und wieder zusammensetzen, ins Sechzehnersystem und in jedes andere schreiben, negative Zahlen in einem Byte darstellen und zum Schluss römisch.

1. Teilen mit Rest

Der Rechner speichert jede Zahl als Bits, als Nullen und Einsen. Im Zweiersystem ist jede Stelle doppelt so viel wert wie die rechts von ihr: 1101 ist 8 + 4 + 0 + 1 = 13. Die letzte Ziffer einer Zahl in einem Zahlensystem ist der Rest beim Teilen durch seine Basis, im Zehnersystem wie bei der Quersumme:

puts 13 % 2       # 1, das letzte Bit
puts 13 / 2       # 6: das letzte Bit ist weg, 6 ist 110
puts 1234 % 10    # 4, die letzte Ziffer
puts 1234 / 10    # 123

Bei ganzen Zahlen rundet / ab.

print(13 % 2)      # 1, das letzte Bit
print(13 // 2)     # 6: das letzte Bit ist weg, 6 ist 110
print(1234 % 10)   # 4, die letzte Ziffer
print(1234 // 10)  # 123

// teilt und rundet ab; / gibt eine Kommazahl.

console.log(13 % 2);                  // 1, das letzte Bit
console.log(Math.floor(13 / 2));      // 6: das letzte Bit ist weg, 6 ist 110
console.log(1234 % 10);               // 4, die letzte Ziffer
console.log(Math.floor(1234 / 10));   // 123

/ gibt eine Kommazahl; Math.floor rundet ab.

Teilt man immer wieder und sammelt die Reste, hat man alle Ziffern, von rechts nach links. Was Bits und Bytes im Rechner sind, steht im Handbuch unter Bits und Bytes.

2. Einstieg

Aufgabe 1Eine Zahl in BitsEinstieg

Schreib eine Funktion to_binary(n), die eine Zahl ab 0 als Text aus Nullen und Einsen zurückgibt, so wie sie im Rechner steht: to_binary(13) ergibt '1101', denn 13 = 8 + 4 + 1. Ohne to_s(2).

def to_binary(n)
end

Tipp

n % 2 ist das letzte Bit, das ganz rechts. n / 2 streicht es weg. Wiederhole, bis nichts mehr übrig ist, wie bei der Quersumme.

Nächster Tipp

Jedes neue Bit gehört vor die, die du schon hast.

Aufgabe 1Eine Zahl in BitsEinstieg

Schreib eine Funktion to_binary(n), die eine Zahl ab 0 als Text aus Nullen und Einsen zurückgibt, so wie sie im Rechner steht: to_binary(13) ergibt '1101', denn 13 = 8 + 4 + 1. Ohne bin.

def to_binary(n):
    pass

Tipp

n % 2 ist das letzte Bit, das ganz rechts. n // 2 streicht es weg. Wiederhole, bis nichts mehr übrig ist, wie bei der Quersumme.

Nächster Tipp

Jedes neue Bit gehört vor die, die du schon hast.

Aufgabe 1Eine Zahl in BitsEinstieg

Schreib eine Funktion toBinary(n), die eine Zahl ab 0 als Text aus Nullen und Einsen zurückgibt, so wie sie im Rechner steht: toBinary(13) ergibt '1101', denn 13 = 8 + 4 + 1. Ohne toString(2).

function toBinary(n) {
}

Tipp

n % 2 ist das letzte Bit, das ganz rechts. Math.floor(n / 2) streicht es weg. Wiederhole, bis nichts mehr übrig ist, wie bei der Quersumme.

Nächster Tipp

Jedes neue Bit gehört vor die, die du schon hast.

Aufgabe 2Bits zurück in eine ZahlEinstieg

Schreib eine Funktion from_binary(bits), die einen Text aus Nullen und Einsen in die Zahl zurückverwandelt: from_binary('1101') ergibt 13. Ohne to_i(2).

def from_binary(bits)
end

Tipp

Lies von links nach rechts. Bei jedem Bit verdoppelt sich, was du schon hast, und das neue Bit kommt dazu: '110' ist 1, dann 1·2 + 1 = 3, dann 3·2 + 0 = 6.

Aufgabe 2Bits zurück in eine ZahlEinstieg

Schreib eine Funktion from_binary(bits), die einen Text aus Nullen und Einsen in die Zahl zurückverwandelt: from_binary('1101') ergibt 13. Ohne int.

def from_binary(bits):
    pass

Tipp

Lies von links nach rechts. Bei jedem Bit verdoppelt sich, was du schon hast, und das neue Bit kommt dazu: '110' ist 1, dann 1·2 + 1 = 3, dann 3·2 + 0 = 6.

Aufgabe 2Bits zurück in eine ZahlEinstieg

Schreib eine Funktion fromBinary(bits), die einen Text aus Nullen und Einsen in die Zahl zurückverwandelt: fromBinary('1101') ergibt 13. Ohne parseInt und Number.

function fromBinary(bits) {
}

Tipp

Lies von links nach rechts. Bei jedem Bit verdoppelt sich, was du schon hast, und das neue Bit kommt dazu: '110' ist 1, dann 1·2 + 1 = 3, dann 3·2 + 0 = 6.

Aufgabe 3Ein einzelnes BitEinstieg

Die Bits einer Zahl zählt man von rechts, beim Bit 0. Schreib eine Funktion bit(n, i), die das Bit i von n zurückgibt, 0 oder 1: bit(13, 2) ergibt 1, denn 13 ist 1101. Nur mit Rechnen, ohne die Zahl in einen Text zu verwandeln und ohne n[i].

def bit(n, i)
end

Tipp

n % 2 ist Bit 0. Teilst du n durch 2, rücken alle Bits einen Platz nach rechts, und Bit 1 wird zu Bit 0.

Aufgabe 3Ein einzelnes BitEinstieg

def bit(n, i):
    pass

Tipp

n % 2 ist Bit 0. Teilst du n durch 2 (//), rücken alle Bits einen Platz nach rechts, und Bit 1 wird zu Bit 0.

Aufgabe 3Ein einzelnes BitEinstieg

function bit(n, i) {
}

Tipp

n % 2 ist Bit 0. Teilst du n durch 2 und rundest ab, rücken alle Bits einen Platz nach rechts, und Bit 1 wird zu Bit 0.

Aufgabe 4Wie viele Bits?Einstieg

Schreib eine Funktion binary_length(n), die zählt, wie viele Bits n braucht: binary_length(13) ergibt 4, denn 13 ist 1101. Die 0 braucht ein Bit. Nur mit Rechnen.

def binary_length(n)
end

Tipp

Wie oft kann man n durch 2 teilen, bis 1 übrig ist? Jedes Teilen streicht ein Bit.

Aufgabe 4Wie viele Bits?Einstieg

Schreib eine Funktion binary_length(n), die zählt, wie viele Bits n braucht: binary_length(13) ergibt 4, denn 13 ist 1101. Die 0 braucht ein Bit. Nur mit Rechnen.

def binary_length(n):
    pass

Tipp

Wie oft kann man n durch 2 teilen, bis 1 übrig ist? Jedes Teilen streicht ein Bit.

Aufgabe 4Wie viele Bits?Einstieg

Schreib eine Funktion binaryLength(n), die zählt, wie viele Bits n braucht: binaryLength(13) ergibt 4, denn 13 ist 1101. Die 0 braucht ein Bit. Nur mit Rechnen.

function binaryLength(n) {
}

Tipp

Wie oft kann man n durch 2 teilen, bis 1 übrig ist? Jedes Teilen streicht ein Bit.

3. Übung

Aufgabe 5Einsen zählenÜbung

Schreib eine Funktion count_ones(n), die zählt, wie viele Bits von n eine 1 sind: count_ones(13) ergibt 3. Nur mit Rechnen.

def count_ones(n)
end

Tipp

Wie bei der Quersumme, nur im Zweiersystem: n % 2 ist das letzte Bit, n / 2 streicht es.

Aufgabe 5Einsen zählenÜbung

Schreib eine Funktion count_ones(n), die zählt, wie viele Bits von n eine 1 sind: count_ones(13) ergibt 3. Nur mit Rechnen.

def count_ones(n):
    pass

Tipp

Wie bei der Quersumme, nur im Zweiersystem: n % 2 ist das letzte Bit, n // 2 streicht es.

Aufgabe 5Einsen zählenÜbung

Schreib eine Funktion countOnes(n), die zählt, wie viele Bits von n eine 1 sind: countOnes(13) ergibt 3. Nur mit Rechnen.

function countOnes(n) {
}

Tipp

Wie bei der Quersumme, nur im Zweiersystem: n % 2 ist das letzte Bit, Math.floor(n / 2) streicht es.

Aufgabe 6HexadezimalÜbung

Im Sechzehnersystem gibt es sechzehn Ziffern: 0 bis 9, dann a bis f für 10 bis 15. Farben im Netz schreibt man so (#ff8800). Schreib eine Funktion to_hex(n), die n als Text im Sechzehnersystem zurückgibt, mit kleinen Buchstaben: to_hex(255) ergibt 'ff'. Ohne to_s(16).

def to_hex(n)
end

Tipp

Genau wie bei den Bits, nur mit 16 statt 2.

Nächster Tipp

Für die Ziffer hilft ein Text mit allen sechzehn: '0123456789abcdef'[11] ist 'b'.

Aufgabe 6HexadezimalÜbung

def to_hex(n):
    pass

Tipp

Genau wie bei den Bits, nur mit 16 statt 2.

Nächster Tipp

Für die Ziffer hilft ein Text mit allen sechzehn: '0123456789abcdef'[11] ist 'b'.

Aufgabe 6HexadezimalÜbung

Im Sechzehnersystem gibt es sechzehn Ziffern: 0 bis 9, dann a bis f für 10 bis 15. Farben im Netz schreibt man so (#ff8800). Schreib eine Funktion toHex(n), die n als Text im Sechzehnersystem zurückgibt, mit kleinen Buchstaben: toHex(255) ergibt 'ff'. Ohne toString(16).

function toHex(n) {
}

Tipp

Genau wie bei den Bits, nur mit 16 statt 2.

Nächster Tipp

Für die Ziffer hilft ein Text mit allen sechzehn: '0123456789abcdef'[11] ist 'b'.

Aufgabe 7Hexadezimal zurückÜbung

Schreib eine Funktion from_hex(text), die eine Zahl im Sechzehnersystem, mit kleinen Buchstaben, in die Zahl zurückverwandelt: from_hex('ff') ergibt 255. Ohne hex und to_i(16).

def from_hex(text)
end

Tipp

Wie bei den Bits: von links nach rechts, mal 16 und die neue Ziffer dazu. '0123456789abcdef'.index('b') ist 11.

Aufgabe 7Hexadezimal zurückÜbung

Schreib eine Funktion from_hex(text), die eine Zahl im Sechzehnersystem, mit kleinen Buchstaben, in die Zahl zurückverwandelt: from_hex('ff') ergibt 255. Ohne int.

def from_hex(text):
    pass

Tipp

Wie bei den Bits: von links nach rechts, mal 16 und die neue Ziffer dazu. '0123456789abcdef'.index('b') ist 11.

Aufgabe 7Hexadezimal zurückÜbung

Schreib eine Funktion fromHex(text), die eine Zahl im Sechzehnersystem, mit kleinen Buchstaben, in die Zahl zurückverwandelt: fromHex('ff') ergibt 255. Ohne parseInt und Number.

function fromHex(text) {
}

Tipp

Wie bei den Bits: von links nach rechts, mal 16 und die neue Ziffer dazu. '0123456789abcdef'.indexOf('b') ist 11.

Ausprobieren: Eine Farbe im Netz besteht aus drei Bytes, Rot, Grün und Blau, jedes von 0 bis 255: #ff8800 ist ff, 88, 00. Rechne mit deiner Funktion aus, wie viel Rot, Grün und Blau in #1e90ff steckt.

Aufgabe 8Eine Zweierpotenz?Übung

1, 2, 4, 8, 16 … sind Zweierpotenzen: Im Zweiersystem haben sie genau eine 1. Schreib eine Funktion power_of_two(n), die true zurückgibt, wenn n eine Zweierpotenz ist, und sonst false: power_of_two(64) ergibt true, power_of_two(12) ergibt false.

def power_of_two(n)
end

Tipp

Teil n durch 2, solange es gerade ist. Was bleibt bei einer Zweierpotenz übrig?

Nächster Tipp

Denk an die 0: Sie ist immer wieder gerade.

Aufgabe 8Eine Zweierpotenz?Übung

1, 2, 4, 8, 16 … sind Zweierpotenzen: Im Zweiersystem haben sie genau eine 1. Schreib eine Funktion power_of_two(n), die True zurückgibt, wenn n eine Zweierpotenz ist, und sonst False: power_of_two(64) ergibt True, power_of_two(12) ergibt False.

def power_of_two(n):
    pass

Tipp

Teil n durch 2, solange es gerade ist. Was bleibt bei einer Zweierpotenz übrig?

Nächster Tipp

Denk an die 0: Sie ist immer wieder gerade.

Aufgabe 8Eine Zweierpotenz?Übung

1, 2, 4, 8, 16 … sind Zweierpotenzen: Im Zweiersystem haben sie genau eine 1. Schreib eine Funktion powerOfTwo(n), die true zurückgibt, wenn n eine Zweierpotenz ist, und sonst false: powerOfTwo(64) ergibt true, powerOfTwo(12) ergibt false.

function powerOfTwo(n) {
}

Tipp

Teil n durch 2, solange es gerade ist. Was bleibt bei einer Zweierpotenz übrig?

Nächster Tipp

Denk an die 0: Sie ist immer wieder gerade.

4. Knobelei

Aufgabe 9Negative Zahlen in einem ByteKnobelei

Ein Byte hat acht Bits. Für Zahlen von -128 bis 127 nimmt der Rechner das Zweierkomplement: Eine Zahl ab 0 steht wie gewohnt da, eine negative Zahl n als 256 + n. Schreib eine Funktion twos_complement(n), die die acht Bits als Text zurückgibt, mit Nullen vorn: twos_complement(5) ergibt '00000101', twos_complement(-1) ergibt '11111111'. Ohne to_s(2).

def twos_complement(n)
end

Tipp

Erst die Zahl, die im Byte steht: bei einer negativen 256 + n. Dann ihre Bits wie in der ersten Kata.

Nächster Tipp

Rechne genau achtmal, dann stehen vorn von selbst Nullen: 8.times do … end.

Aufgabe 9Negative Zahlen in einem ByteKnobelei

def twos_complement(n):
    pass

Tipp

Erst die Zahl, die im Byte steht: bei einer negativen 256 + n. Dann ihre Bits wie in der ersten Kata.

Nächster Tipp

Rechne genau achtmal, dann stehen vorn von selbst Nullen: for _ in range(8):.

Aufgabe 9Negative Zahlen in einem ByteKnobelei

Ein Byte hat acht Bits. Für Zahlen von -128 bis 127 nimmt der Rechner das Zweierkomplement: Eine Zahl ab 0 steht wie gewohnt da, eine negative Zahl n als 256 + n. Schreib eine Funktion twosComplement(n), die die acht Bits als Text zurückgibt, mit Nullen vorn: twosComplement(5) ergibt '00000101', twosComplement(-1) ergibt '11111111'. Ohne toString(2).

function twosComplement(n) {
}

Tipp

Erst die Zahl, die im Byte steht: bei einer negativen 256 + n. Dann ihre Bits wie in der ersten Kata.

Nächster Tipp

Rechne genau achtmal, dann stehen vorn von selbst Nullen: for (let i = 0; i < 8; i++).

Aufgabe 10Jedes ZahlensystemKnobelei

Schreib eine Funktion to_base(n, base), die eine Zahl ab 0 in einem Zahlensystem mit der Basis base von 2 bis 16 schreibt, mit den Ziffern 0 bis 9 und a bis f: to_base(255, 2) ergibt '11111111', to_base(255, 8) ergibt '377'. Ohne to_s(base).

def to_base(n, base)
end

Tipp

Was du für 2 und für 16 geschrieben hast, geht mit jeder Basis: Rest beim Teilen durch base, dann durch base teilen.

Aufgabe 10Jedes ZahlensystemKnobelei

def to_base(n, base):
    pass

Tipp

Was du für 2 und für 16 geschrieben hast, geht mit jeder Basis: Rest beim Teilen durch base, dann durch base teilen.

Aufgabe 10Jedes ZahlensystemKnobelei

Schreib eine Funktion toBase(n, base), die eine Zahl ab 0 in einem Zahlensystem mit der Basis base von 2 bis 16 schreibt, mit den Ziffern 0 bis 9 und a bis f: toBase(255, 2) ergibt '11111111', toBase(255, 8) ergibt '377'. Ohne toString(base).

function toBase(n, base) {
}

Tipp

Was du für 2 und für 16 geschrieben hast, geht mit jeder Basis: Rest beim Teilen durch base, dann durch base teilen.

Aufgabe 11Von einem System ins andereKnobelei

Schreib eine Funktion convert(text, source, target), die eine Zahl, im System mit der Basis source geschrieben, im System mit der Basis target zurückgibt: convert('ff', 16, 2) ergibt '11111111'. Deine Funktionen von eben darfst du mitbenutzen, wenn du sie hier hineinschreibst.

def convert(text, source, target)
end

Tipp

Zwei Schritte: erst lesen, wie bei from_hex, nur mit source; dann schreiben wie bei to_base, mit target.

Aufgabe 11Von einem System ins andereKnobelei

def convert(text, source, target):
    pass

Tipp

Zwei Schritte: erst lesen, wie bei from_hex, nur mit source; dann schreiben wie bei to_base, mit target.

Aufgabe 11Von einem System ins andereKnobelei

function convert(text, source, target) {
}

Tipp

Zwei Schritte: erst lesen, wie bei fromHex, nur mit source; dann schreiben wie bei toBase, mit target.

5. Extras Extra

Ein Extra für Schnelle: Die Seite ist ohne dieses Kapitel vollständig.

Zwei Katas, die nicht mitzählen: ein Zahlensystem ohne Stellen.

Aufgabe 12Römische ZahlenExtra

Die Römer schrieben I für 1, V für 5, X für 10, L für 50, C für 100, D für 500 und M für 1000; vier gleiche Zeichen hintereinander gibt es nicht, statt IIII schreibt man IV (eins vor fünf), ebenso IX, XL, XC, CD und CM. Schreib eine Funktion roman(n) für 1 bis 3999: roman(1994) ergibt 'MCMXCIV'.

def roman(n)
end

Tipp

Nimm immer das größte Zeichen, das noch hineinpasst, wie beim Herausgeben von Wechselgeld: 1994 ist 1000, dann 900, 90, 4.

Nächster Tipp

Die Paare wie CM sind eigene Zeichen mit eigenem Wert. Eine Liste von Paaren aus Wert und Zeichen, vom größten zum kleinsten, macht den Rest einfach.

Aufgabe 12Römische ZahlenExtra

def roman(n):
    pass

Tipp

Nimm immer das größte Zeichen, das noch hineinpasst, wie beim Herausgeben von Wechselgeld: 1994 ist 1000, dann 900, 90, 4.

Nächster Tipp

Die Paare wie CM sind eigene Zeichen mit eigenem Wert. Eine Liste von Paaren aus Wert und Zeichen, vom größten zum kleinsten, macht den Rest einfach.

Aufgabe 12Römische ZahlenExtra

function roman(n) {
}

Tipp

Nimm immer das größte Zeichen, das noch hineinpasst, wie beim Herausgeben von Wechselgeld: 1994 ist 1000, dann 900, 90, 4.

Nächster Tipp

Die Paare wie CM sind eigene Zeichen mit eigenem Wert. Eine Liste von Paaren aus Wert und Zeichen, vom größten zum kleinsten, macht den Rest einfach.

Aufgabe 13Römische Zahlen lesenExtra

Und zurück: Schreib eine Funktion from_roman(text), die eine römische Zahl in die gewohnte verwandelt: from_roman('MCMXCIV') ergibt 1994. Steht ein Zeichen vor einem größeren, wird es abgezogen, sonst dazugezählt.

def from_roman(text)
end

Tipp

Ein Hash ordnet jedem Zeichen seinen Wert zu. Geh die Zeichen mit ihrem Index durch, dann kannst du das nächste ansehen: text[i + 1].

Aufgabe 13Römische Zahlen lesenExtra

def from_roman(text):
    pass

Tipp

Ein Dictionary ordnet jedem Zeichen seinen Wert zu. Geh die Zeichen mit ihrem Index durch, dann kannst du das nächste ansehen: text[i + 1].

Aufgabe 13Römische Zahlen lesenExtra

Und zurück: Schreib eine Funktion fromRoman(text), die eine römische Zahl in die gewohnte verwandelt: fromRoman('MCMXCIV') ergibt 1994. Steht ein Zeichen vor einem größeren, wird es abgezogen, sonst dazugezählt.

function fromRoman(text) {
}

Tipp

Ein Objekt ordnet jedem Zeichen seinen Wert zu. Geh die Zeichen mit ihrem Index durch, dann kannst du das nächste ansehen: text[i + 1].