Knowledge Base

お知らせや身辺のことを綴っています。

10進数→2進数の手計算をしていて気づいたこととかツールとか

最近寒くてしょうがないので、暖房が効いている居間からWake on LANでメインPCを立ち上げることはできないか模索していた。これまでWake on LANの設定は何となくでやっていたものの、技術系の人間として、ネットワークアドレスやブロードキャストアドレスを何不自由なく手計算で求められるくらいには計算部分をしっかり理解したいと思い、そのために必要な10進数→2進数の手計算を今回の記事のテーマとした。後半には、あまり関係がないかもしれないが、色々計算練習をする前にあった方がよいと思って自作したものを紹介する。

今回の記事について、筆者は算数が得意な人間ではないし、今回書き留めておく内容はそれが得意な人にとっては自明な内容かもしれないことを前もって申し上げる。

実際に気づいたこと

10進数は、機械的な筆算を適用することによって2進数に変換できるが、その際に計算しやすくするポイントとして2点あることに気が付いた。それらは、被除数の隣に余りを書くことと、被除数の1桁目をみるということだ。

まず、被除数の隣に余りを書くということについて説明する。こうすることで、実際にどのステップでどの数を割っているのかが分かりやすくなる。また、実際に割る回数が、2進数での桁数と同じになっているので、これを含めて些細なミスを減らすことができる。

また、あまりを求める際にも思考リソースを最小にできると思った。2進数を求めているのだから、あまりは0か1しかない。結局、被除数の1桁目をみて、それが奇数ならあまりは1になり、そうでなければ0になる。

奇数判定にx & 1 ―「x の1桁目(2進数の文脈では最下位ビット)が1ならば奇数である」という命題を使うことがある。これはその逆で、すなわち2進数の最下位ビットからもとめていく各ステップごとに「奇数ならば x の1桁目は1である」ということをやっている(のだと思う。自信がないので間違ってたら指摘してほしい)。

これさえ踏まえていれば、あとは暗算の問題だと思う。あとは、記事内容の水増しとして色々計算練習をするために便利だと思うものを自作したので紹介する。

準備したもの

こうした計算練習をするときにあった方がよいと思ったものを自作した。2項の数字を出力するプログラムと2のべき乗の壁紙である。すこし無駄じゃないか?と思う人もいるかもしれないが、それはそれとしてPythonのフォーマット文字列に親しむことができたので問題ではない。

2項の計算問題を出力するプログラム

まずこんなプログラムを作ってランダムな数字を出力して、その2項を足したり引いたりAND演算したりOR演算したりXOR演算した結果を表示して実際の計算が合っているかどうかを確認できるようなプログラムを書いた。

$ ./problems_generator.py
(182, 31)  # 人力ビット演算
press ENTER to show the answer:  # 解いたらEnter キーを押す
      and       10110 (22)
       or    10111111 (191)
      xor    10101001 (169)
      add    11010101 (213)
 subtract    10010111 (151)  # あってたら喜ぶ

スクリプトの中身はこんな感じ。 max_ 部分で問う範囲を変更できるが、表示が崩れてしまうし、IPアドレスでは256以上の数字は出てこないのでとりあえず十分とした。

#!/usr/bin/env python3

from random import random, randint
from sys import exit, argv
from typing import NamedTuple


class Answer(NamedTuple):
    and_:     int
    or_:      int
    xor:      int
    add:      int
    subtract: int

    def print(self):
        key = dict(zip(Answer._fields, ('and', 'or', 'xor', 'add', 'subtract')))
        for x in Answer._fields:
            y = getattr(self, x)
            name = format(key[x], ">9s")
            binary, decimal = format(y, ">11b"), str(y)
            value = f"%s (%s)" % (binary, decimal)
            print(name, value)


if __name__ == "__main__":
    max_ = 256
    x, y = [randint(0, max_) for _ in range(2)]
    x, y = (y, x) if y > x else (x, y)
    print((x, y))
    _ = input("press ENTER to show the answer: ")
    answer = Answer(x & y, x | y, x ^ y, x + y, x - y,)
    answer.print()

2のべき乗の壁紙

2のべき乗を暗記していると、たとえば2進数から10進数に変換する際に漸近的に求めていくことができるので便利だと思う。小学生の時九九を暗記した時、トイレやお風呂場にチャレンジの掛け算表を持って行って暗唱したり、CDを聴きまくったりした(「ろっくいちがろく★」)ように、イマージョンは学習手段として有効な戦略である。

そのため、2のべき乗に親しめるように、壁紙を作った。ターミナルエミュレーターで出力したスクリーンショットをMSペイントで少し編集しただけの代物だが、見栄えが良い上に実用的である。

スクリプトの中身はこんな感じ。こちらは引数で表示範囲を切り替えられるようにして、桁数に応じて動的にフォーマットしている。

#!/usr/bin/env python3
import sys


def count_max_digit(n, base):
    ans = 0
    while n > 0:
        n, r = divmod(n, base)
        ans += 1
    return ans


def make_key(n, prefix="", suffix=""):
    return f"{prefix}{n}{suffix}"


if __name__ == "__main__":
    if len(sys.argv) < 2:
        print("error: an extra argument must be given")
        sys.exit(1)

    e = int(sys.argv[1])
    exp2e = 2 ** e
    e_kwargs = {"prefix": "2e", }

    max_digit_e = len(make_key(e, **e_kwargs))
    max_digit_2 = count_max_digit(exp2e, 2)
    max_digit_10 = count_max_digit(exp2e, 10)

    a = [*map(lambda x: 2 ** x, range(e + 1))]
    keys = [make_key(e, **e_kwargs) for e in range(e + 1)]
    b = [(format(e, f"<{max_digit_e}s"), format(n, f"<{max_digit_10}d"), format(n, f"<{max_digit_2}b")) for e, n in zip(keys, a)]

    for v in b:
        print(*v, sep="  ")

おわりに

高校時代、毎回数学のテストでは血反吐を吐いていたが、身近な事象だったりコンピューターの知識だったりを絡めると、具体的な値とともにその概念を理解できるようになって良いなと思うことが増えてきた。もっと早くにプログラミングを始めればよかったなと思う。