Ctrl+K

九九のない世界

九九のない世界#

Leibnizの二進法#

和の筆算#

from itertools import zip_longest

def long_addition(a,b):
    a = map(int,reversed(str(a)))
    b = map(int,reversed(str(b)))
    q=0
    for n,m in zip_longest(a, b, fillvalue=0):
        q, r = divmod(q+n+m,10)
        yield str(r)
    if q:
        yield str(q)

long_addition(2, 5)

<generator object long_addition at 0x7d1af24079a0>

list(_)

['7']

%%ai vioras
{In[5]}のプログラムについて

このプログラムは、Pythonで長い加算（大きな数の足し算）を行うためのものです。以下にその説明をします：

  1. aとbは入力される二つの数値です。

  2. map(int,reversed(str(a)))とmap(int,reversed(str(b)))は、aとbをそれぞれ文字列に変換し、その文字列を反転させ、反転させた文字列の各文字を整数に変換することで、各桁の数値を順番に取り出せるようにしています。これは、加算を1の位から始めるためです。

  3. zip_longest(a, b, fillvalue=0)は、aとbの各桁を結合しています。fillvalue=0は、aとbの桁数が異なる場合に短い方を0で埋めるためです。

  4. divmod(q+n+m,10)は、桁の和q+n+mを10で割った商q（次の桁への繰り上がり）と余りr（この桁の結果）を計算しています。

  5. yield str(r)は、この桁の結果を文字列として生成（yield）しています。

  6. 最後のif q: yield str(q)は、最後の桁で繰り上がりがある場合にその繰り上がりを生成しています。

このプログラムの出力は逆順のため、適切な結果を得るには出力を反転させる必要があります。

def long_addition2(a,b):
    a = map(int,reversed(bin(a)[2:]))
    b = map(int,reversed(bin(b)[2:]))
    q=0
    for n,m in zip_longest(a, b, fillvalue=0):
        q, r = divmod(q+n+m,2)
        print("{:d}+{:d}+{:d}={:d}{:d}".format(q,n,m, q,r))
        yield str(r)
    if q:
        yield str(q)

long_addition2(2, 5)

<generator object long_addition2 at 0x7d1af23c7810>

list(_)

0+0+1=01
0+1+0=01
0+0+1=01

['1', '1', '1']

%%ai vioras
{In[9]}のプログラムについて

このプログラムは、Pythonで長い二進数の加算（大きな二進数の足し算）を行うためのものです。以下にその説明をします：

  1. aとbは入力される二つの数値です。

  2. map(int,reversed(bin(a)[2:]))とmap(int,reversed(bin(b)[2:]))は、aとbをそれぞれ二進数に変換し（bin関数により）、その二進数表示の0bを除去した文字列を反転させ、反転させた文字列の各文字を整数に変換することで、各ビットを順番に取り出せるようにしています。これは、加算を最下位ビットから始めるためです。

  3. zip_longest(a, b, fillvalue=0)は、aとbの各ビットを結合しています。fillvalue=0は、aとbのビット長が異なる場合に短い方を0で埋めるためです。

  4. divmod(q+n+m,2)は、ビットの和q+n+mを2で割った商q（次のビットへの繰り上がり）と余りr（このビットの結果）を計算しています。

  5. print("{:d}+{:d}+{:d}={:d}{:d}".format(q,n,m, q,r))は、各ビットでの加算の結果を表示しています。

  6. yield str(r)は、このビットの結果を文字列として生成（yield）しています。

  7. 最後のif q: yield str(q)は、最後のビットで繰り上がりがある場合にその繰り上がりを生成しています。

このプログラムの出力は逆順のため、適切な結果を得るには出力を反転させる必要があります。

%%ai vioras
このプログラムを`divmod()`ではなく、論理演算の組み合わせで再実装して下さい

もちろんです。divmod関数は商と余りを一度に計算しますが、これをビット演算に置き換えることも可能です。余りはAND演算（&）で、商は右シフト演算（>>）で計算できます。

以下がその実装例です：

from itertools import zip_longest

def long_addition_bin(a, b):
    a = map(int, reversed(bin(a)[2:]))
    b = map(int, reversed(bin(b)[2:]))
    carry = 0
    for n, m in zip_longest(a, b, fillvalue=0):
        sum_val = carry + n + m
        carry = (sum_val & 2) >> 1  # 商（繰り上がり）
        remainder = sum_val & 1  # 余り
        print("{:d}+{:d}+{:d}={:d}{:d}".format(carry, n, m, carry, remainder))
        yield str(remainder)
    if carry:
        yield str(carry)

このプログラムでは、sum_val & 2により、sum_valの2の位のビットが1であるかどうか（つまり、sum_valが2以上であるかどうか）を確認しています。その結果を右シフトにより1桁下げて繰り上がりを得ています。また、sum_val & 1により、sum_valの1の位のビット（つまり、sum_valを2で割った余り）を得ています。

def long_addition2(a,b):
    a = map(int,reversed(bin(a)[2:]))
    b = map(int,reversed(bin(b)[2:]))
    q=0
    for n,m in zip_longest(a, b, fillvalue=0):
        #q, r = divmod(q+n+m,2)
        print("{:d}+{:d}+{:d}=({:d}&{:d}|{:d}&{:d}|{:d}&{:d})({:d}|{:d}|{:d})".format(q,n,m, q,n,q,m,n,m, q,n,m), end="")
        r = q ^ n ^ m
        q = q & n | q & m | n & m
        print("={:d}{:d}".format(q,r))
        yield str(r)
    if q:
        yield str(q)

long_addition2(2, 5)

<generator object long_addition2 at 0x7d1af239b740>

list(_)

0+0+1=(0&0|0&1|0&1)(0|0|1)=01
0+1+0=(0&1|0&0|1&0)(0|1|0)=01
0+0+1=(0&0|0&1|0&1)(0|0|1)=01

['1', '1', '1']

%%ai vioras
わたしは{In[14]}のように実装しました

その実装は素晴らしいです！あなたは論理ゲートを使用して二進数の加算を行っています。具体的には、XOR（排他的論理和、記号：^）とAND（論理積、記号：&）、OR（論理和、記号：|）を使った実装です。

  1. r = q ^ n ^ mは、XORを用いてビットの和（加算結果）を計算しています。XORは2つの入力が異なるときにのみ1を出力するため、3つのビットの中で1が奇数個あるときに1を出力し、偶数個あるときに0を出力します。これは、加算の結果と一致します。

  2. q = q & n | q & m | n & mは、ANDとORを用いて繰り上がりを計算しています。ANDは2つの入力がともに1のときにのみ1を出力するため、3つのビットの中で1が2つ以上あるときに1を出力します。これは、繰り上がりと一致します。

  3. print("{:d}+{:d}+{:d}=({:d}&{:d}|{:d}&{:d}|{:d}&{:d})({:d}|{:d}|{:d})".format(q,n,m, q,n,q,m,n,m, q,n,m), end="")とprint("={:d}{:d}".format(q,r))は、各ビットでの加算の過程と結果を表示しています。

このように、論理ゲートを用いて二進数の加算を行うことは、ハードウェアレベルでの加算回路の実装にも通じる考え方です。そのため、あなたの実装は非常に深い理解を示しています。素晴らしいですね！

積の筆算#

%%ai vioras
乗算のプログラムに変更してください

二進数の乗算を行うプログラムを作成することが可能です。基本的なアルゴリズムは、一方の数値の各ビットを見て、そのビットが1の場合には他方の数値を左にシフトしたものを加算する、というものです。以下にその実装例を示します：

def long_multiplication_bin(a, b):
    a_bin = list(map(int, reversed(bin(a)[2:])))
    b_bin = bin(b)[2:]
    
    result = 0
    for i, bit in enumerate(a_bin):
        if bit == 1:
            result += int(b_bin) << i
    return bin(result)[2:]

ここで、<<は左シフト演算子で、数値を左にシフトします（二進数での乗算に相当します）。また、bin(result)[2:]は計算結果を二進数表記にするためのもので、[2:]で'0b'を取り除いています。

%%ai vioras
`int()`の使い方が間違っています。二進法からの変換を示すために第２引数に$2$を与えてください

ご指摘いただきありがとうございます。二進数の文字列を整数に変換するためには、int関数の第二引数に基数2を指定する必要があります。以下にその修正を加えたコードを示します：

def long_multiplication_bin(a, b):
    a_bin = list(map(int, reversed(bin(a)[2:])))
    b_bin = bin(b)[2:]
    
    result = 0
    for i, bit in enumerate(a_bin):
        if bit == 1:
            result += int(b_bin, 2) << i
    return bin(result)[2:]

ここで、int(b_bin, 2)により二進数表記の文字列b_binを整数に変換しています。

def long_multiplication_bin(a, b):
    a_bin = list(map(int, reversed(bin(a)[2:])))
    b_bin = bin(b)[2:]
    
    result = 0
    for i, bit in enumerate(a_bin):
        if bit == 1:
            result += int(b_bin, 2) << i
    return bin(result)[2:]

long_multiplication_bin(3, 5)

'1111'

int(_, 2)

15
Contents