PhDr. Mgr. Jeroným Klimeš, Ph.D. 2024-07-07
Následující text se týká především Linuxu a Bash, ale může být inspirativní i pro jiné operační systémy.
Po přečtení těchto pár řádků by vám měly začít připadat vtipné tyto vtipy:
Je 10 druhů lidí. Ti, kteří umějí dvojkovou soustavu & ti, kteří ne.
Q: Why do programmers always mix up Halloween and Christmas?
A: Because Oct 31 == Dec 25!
Dnes jsem si udělal takový výlet do světa rekursí. Hádám se teď s připojováním k síti a řeším převod masky z tvaru 255.255.255.0 na cislo 24, které se pak zadává k IP adrese: 192.168.0.10/24.
To se dělá tak, že čísla 255 převedete do binární soustavy, tedy:
11111111.11111111.1111111.00000000
Pak se posčítají jedničky a je to. To není nic až tak těžkého.
binarni="11111111.11111111.11111111.00000000"
echo $(( $(sed -r "s/\.//g;s/./&+/g" <<<$binarni)0 ))
To nám řekne, že v řetězci je 24 jedniček. První sed příkaz odstraní tečky, druhý přidá za každou číslici plus a echo nakonec sečte řetězec tvaru (1+1+1+1+0+0+0+0)
Jenže v Bash není žádná elegantní funkce na převod decimálního čísla na binární.
Našel jsem jednu tak komickou, že jsem se opravdu začal smát. Posuďte sami:
D2B=({0..1}{0..1}{0..1}{0..1}{0..1}{0..1}{0..1}{0..1})
echo ${D2B[7]} # vrací: 00000111
Vtip je v té první řádce. To je totální bashismus. První řádka vygeneruje array s 255 binárními čísly. Ta druhá řádka vezme prostě jen to sedmé.
Tak jsem si uvědomil, že tento animovaný vtip v mém případě není vtipem, protože jsem sám sebe přistihl, že mě rozesmála binární soustava:
Bashismus je označení pro bastlení v počítači. Uděláte něco, co sice funguje, ale je to poskládané páté přes deváte. Tady například kdyby se takto převáděly větší čísla, tak si ucpete kapacitu procesoru počítače – vyráběním toho array - a dále pak ucpete paměť počítače, protože ten ohromný array samozřejmě musí někde ležet v paměti, ve stacku.
Když jsem byl v té veselé náladě, tak jsem si řekl, že by to mělo jít rekursivně přes mé oblíběné zbytkové třídy. Našel jsem si proto funkci na faktoriál a tu jsem trochu upravil:
factorial()
{
if (( $1 <= 1 )); then
echo 1
else
last=$(factorial $(( $1 - 1 )))
echo $(( $1 * last ))
fi
}
factorial 5
Na rekursivních funkcích je vtipné to, že volají samy sebe. Poslední řádka volá funkci faktorial s parametrem 5. Ta zavolá sama sebe s parametrem 4. Toto druhé volání zavolá třetí s parametrem 3, a tak to jde, až nezbyde nic.
Tak jsem to lidově řečeno opajc:
number=10
binary()
{
if (( $1 < $base )); then
echo $1
else
echo -n $(( $1 % $base ))
binary $(( $1 / $base ))
fi
}
base=2
rev <<<$(binary $number)
Deset se převádí do dvojkové či jakékoli jiné soustavy (proměnná $base) takto:
10/2=5 zbytek 0
5/2=2 zbytek 1
2/2=1 zbytek 0
1/2=0 zbytek 1
Zajímají nás právě ty zbytky. Problém je ale v tom, že binární číslo vzniklé v rekurzí, tzn. ze zbytků, jde pozpátku: 0101 je pozpátku 1010, čili 10 ve desítkové soustavě.
Každé volání této rekurze tedy vrací zbytek a úkolem posledního řádku je obrátit pořadí písmen, což v Linuxu dělá funkce rev. Občas se hodí u hebrejských slov, které jsou také pozpátku.
Tolik tedy k převádění čísel z desítkové do dvojkové soustavy pomocí rekurzivní funkce.
Ta rekurzivní funkce mi udělala radost. Přeci jenom rekuzivně neprogramuju každý den. Potřeboval bych takových rekurzivních funkcí napsat tak sto, abych si je zautomatizoval. Zatím je to jen vlašťovka, co jaro nedělá.
Tuto funkci jsem dal též sem, páč sem občas přispívám:
https://stackoverflow.com/questions/10278513/bash-shell-decimal-to-binary-base-2-conversion