課題の解説

課題 1: 位取り記法の加算

• Addition - Wikipedia

  1. それぞれの数字を文字列に変換する

  2. 各桁を逆順にしてから加算を行う

  3. 最後に結果を再び逆順にする

# 1. 数字を文字列に変換
num1, num2 = 12345, 678
str(num1), str(num2)

('12345', '678')

# 2.1 各桁を逆順にする
str(num1)[::-1], str(num2)[::-1]

('54321', '876')

# 2.2 下の桁から処理する
list(zip(*(str(num1)[::-1], str(num2)[::-1])))

[('5', '8'), ('4', '7'), ('3', '6')]

Note

組み込みのzip()関数は長さの違うリストは切り詰められます

zip?

Init signature: zip(self, /, *args, **kwargs)
Docstring:     
zip(*iterables, strict=False) --> Yield tuples until an input is exhausted.

   >>> list(zip('abcdefg', range(3), range(4)))
   [('a', 0, 0), ('b', 1, 1), ('c', 2, 2)]

The zip object yields n-length tuples, where n is the number of iterables
passed as positional arguments to zip().  The i-th element in every tuple
comes from the i-th iterable argument to zip().  This continues until the
shortest argument is exhausted.

If strict is true and one of the arguments is exhausted before the others,
raise a ValueError.
Type:           type
Subclasses:     

# 2.2 下の桁から処理する際に長い桁に合わせる
import itertools

list(itertools.zip_longest(*(str(num1)[::-1], str(num2)[::-1]), fillvalue='0'))

[('5', '8'), ('4', '7'), ('3', '6'), ('2', '0'), ('1', '0')]

itertools.zip_longest?

Init signature: itertools.zip_longest(self, /, *args, **kwargs)
Docstring:     
zip_longest(iter1 [,iter2 [...]], [fillvalue=None]) --> zip_longest object

Return a zip_longest object whose .__next__() method returns a tuple where
the i-th element comes from the i-th iterable argument.  The .__next__()
method continues until the longest iterable in the argument sequence
is exhausted and then it raises StopIteration.  When the shorter iterables
are exhausted, the fillvalue is substituted in their place.  The fillvalue
defaults to None or can be specified by a keyword argument.
Type:           type
Subclasses:     

# 2.3 繰り上がりを考慮しない各桁の加算
for d in itertools.zip_longest(*(str(num1)[::-1], str(num2)[::-1]), fillvalue='0'):
    print(sum(map(int, d)))

13
11
9
2
1

Note

繰り上がりは下の桁から順次処理する必要があり、並行処理はできません

%%ai vioras
次の2つのプログラムの違いを探してください
---
def add_two_numbers_str(num1, num2):
    # 数字を文字列に変換し、逆順にする
    num1 = str(num1)[::-1]
    num2 = str(num2)[::-1]
    
    # 2つの数の長さを揃える
    max_len = max(len(num1), len(num2))
    num1 = num1.ljust(max_len, '0') 
    num2 = num2.ljust(max_len, '0')
    
    carry = 0
    result = ''

    for i in range(max_len):
        temp = int(num1[i]) + int(num2[i]) + carry
        result += str(temp % 10)
        carry = temp // 10

    if carry > 0:
        result += str(carry)
    
    # 結果を逆順にして返す
    return result[::-1]
---
def add_two_binary_numbers(num1, num2):
    # 数字を二進数の文字列に変換し、逆順にする
    num1 = bin(num1)[2:][::-1]
    num2 = bin(num2)[2:][::-1]
    
    # 2つの数の長さを揃える
    max_len = max(len(num1), len(num2))
    num1 = num1.ljust(max_len, '0')
    num2 = num2.ljust(max_len, '0')
    
    carry = 0
    result = ''

    for i in range(max_len):
        temp = int(num1[i]) + int(num2[i]) + carry
        result += str(temp % 2)
        carry = temp // 2

    if carry > 0:
        result += str(carry)
    
    # 結果を逆順にして返す
    return result[::-1]
---

これらの2つのプログラムは非常に似ていますが、使用する数値の形式が異なります。

• add_two_numbers_str関数は、2つの整数を文字列に変換し、その文字列を逆順にします。そして、各桁を順番に加算し、必要に応じて繰り上がりを行います。この関数は、2つの整数を十進数として扱います。

• 一方、add_two_binary_numbers関数は、2つの整数を二進数の文字列に変換し、その文字列を逆順にします。そして、各ビット（0または1）を順番に加算し、必要に応じて繰り上がりを行います。この関数は、2つの整数を二進数として扱います。

基本的なアルゴリズムは同じですが、add_two_numbers_strは十進加算を行い、add_two_binary_numbersは二進加算を行うという違いがあります。具体的には、加算後の結果が10（add_two_numbers_str）または2（add_two_binary_numbers）以上になった場合に繰り上がりを行い、それぞれ10または2で割った余りを現在の桁の結果としています。

%%ai vioras
具体的に異なる行を示し、詳細に動作の違いを説明してください

もちろんです。それでは、2つの関数の具体的な違いを行ごとに見ていきましょう。

1. 数字を文字列に変換する行:

   num1 = str(num1)[::-1]  # add_two_numbers_str
   num1 = bin(num1)[2:][::-1]  # add_two_binary_numbers
   

   add_two_numbers_strでは、整数をそのまま文字列に変換します。一方、add_two_binary_numbersでは、整数を二進数の文字列に変換します。Pythonのbin関数は、数値を'0b'で始まる二進数の文字列に変換するため、[2:]で最初の2文字をスキップしています。

2. 各桁を加算する行:

   temp = int(num1[i]) + int(num2[i]) + carry  # add_two_numbers_str and add_two_binary_numbers
   

   これらの行は、コードは同じですが動作が異なります。add_two_numbers_strでは、各桁の値（0～9）を加算します。一方で、add_two_binary_numbersでは、各ビットの値（0または1）を加算します。

3. 結果と繰り上がりを計算する行:

   result += str(temp % 10)  # add_two_numbers_str
   carry = temp // 10  # add_two_numbers_str
   
   result += str(temp % 2)  # add_two_binary_numbers
   carry = temp // 2  # add_two_binary_numbers
   

   add_two_numbers_strでは、10で割った余りが現在の桁の結果となり、10での整数除算の結果が次の繰り上がりとなります。これは十進数の加算に対応しています。

   一方、add_two_binary_numbersでは、2で割った余りが現在のビットの結果となり、2での整数除算の結果が次の繰り上がりとなります。これは二進数の加算に対応しています。

これらの違いにより、add_two_numbers_str関数は十進数の加算を行い、add_two_binary_numbers関数は二進数の加算を行います。

num=123
str(num), bin(num)

('123', '0b1111011')

list(map(type, (str(num), bin(num))))

[str, str]

type(num)

int

bin(num), bin(num)[2:], bin(num)[2:][::-1]

('0b1111011', '1111011', '1101111')

int(bin(num)[2:][::-1][1])

1

int('F', 16)

15

str?

Init signature: str(self, /, *args, **kwargs)
Docstring:     
str(object='') -> str
str(bytes_or_buffer[, encoding[, errors]]) -> str

Create a new string object from the given object. If encoding or
errors is specified, then the object must expose a data buffer
that will be decoded using the given encoding and error handler.
Otherwise, returns the result of object.__str__() (if defined)
or repr(object).
encoding defaults to sys.getdefaultencoding().
errors defaults to 'strict'.
Type:           type
Subclasses:     StrEnum, DeferredConfigString, _rstr, _ScriptTarget, _ModuleTarget, LSString, include, Keys, InputMode, ColorDepth, ...

bin?

Signature: bin(number, /)
Docstring:
Return the binary representation of an integer.

>>> bin(2796202)
'0b1010101010101010101010'
Type:      builtin_function_or_method

int?

Init signature: int(self, /, *args, **kwargs)
Docstring:     
int([x]) -> integer
int(x, base=10) -> integer

Convert a number or string to an integer, or return 0 if no arguments
are given.  If x is a number, return x.__int__().  For floating point
numbers, this truncates towards zero.

If x is not a number or if base is given, then x must be a string,
bytes, or bytearray instance representing an integer literal in the
given base.  The literal can be preceded by '+' or '-' and be surrounded
by whitespace.  The base defaults to 10.  Valid bases are 0 and 2-36.
Base 0 means to interpret the base from the string as an integer literal.
>>> int('0b100', base=0)
4
Type:           type
Subclasses:     bool, IntEnum, IntFlag, _NamedIntConstant, StrictBool, ConstrainedInt, ByteSize, _CacheHashWrapper, symbol

汎用化

%%ai vioras
基数を引数とする関数に統合できますか？

もちろんです。基数（radix）を引数として取る関数を作成し、その基数に基づいて加算を行うことが可能です。以下に、そのような関数の一例を示します：

def add_numbers_in_radix(num1, num2, radix):
    # 数字を指定された基数の文字列に変換し、逆順にする
    num1 = int_to_base(num1, radix)[::-1]
    num2 = int_to_base(num2, radix)[::-1]
    
    # 2つの数の長さを揃える
    max_len = max(len(num1), len(num2))
    num1 = num1.ljust(max_len, '0')
    num2 = num2.ljust(max_len, '0')
    
    carry = 0
    result = ''

    for i in range(max_len):
        temp = int(num1[i], radix) + int(num2[i], radix) + carry
        result += int_to_base(temp % radix, radix)
        carry = temp // radix

    if carry > 0:
        result += int_to_base(carry, radix)
    
    # 結果を逆順にして返す
    return result[::-1]

def int_to_base(num, base):
    # Convert an integer to a string in the given base
    # This function is used because the built-in `bin` and `hex` functions add prefixes
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if num < base:
        return alphabet[num]
    else:
        return int_to_base(num // base, base) + alphabet[num % base]

このadd_numbers_in_radix関数は、指定された基数（radix）に基づいて2つの数字を加算します。基数は10（十進数）や2（二進数）など、任意の整数を指定できます。

また、int_to_base関数は、整数を指定された基数の文字列に変換します。これは組み込みのbinやhex関数がプレフィックス（'0b'や'0x'）を追加するため、その代わりに使用します。

def add_numbers_in_radix(num1, num2, radix):
    # 数字を指定された基数の文字列に変換し、逆順にする
    num1 = int_to_base(num1, radix)[::-1]
    num2 = int_to_base(num2, radix)[::-1]
    
    # 2つの数の長さを揃える
    max_len = max(len(num1), len(num2))
    num1 = num1.ljust(max_len, '0')
    num2 = num2.ljust(max_len, '0')
    
    carry = 0
    result = ''

    for i in range(max_len):
        temp = int(num1[i], radix) + int(num2[i], radix) + carry
        result += int_to_base(temp % radix, radix)
        carry = temp // radix

    if carry > 0:
        result += int_to_base(carry, radix)
    
    # 結果を逆順にして返す
    return result[::-1]

def int_to_base(num, base):
    # Convert an integer to a string in the given base
    # This function is used because the built-in `bin` and `hex` functions add prefixes
    alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if num < base:
        return alphabet[num]
    else:
        return int_to_base(num // base, base) + alphabet[num % base]

int_to_base(123, 2)

'1111011'

int_to_base(123, 8)

'173'

int_to_base(123, 16)

'7B'

%%ai vioras
`int_to_base`はPythonのライブラリにはありませんか？

Pythonの標準ライブラリには、int_to_baseと同じ機能を持つ関数は存在しません。しかし、Pythonのformat, bin, oct, hexなどの関数を使用すると、整数を異なる基数の文字列（二進数、八進数、十六進数など）に変換することが可能です。

しかし、これらの関数は特定の基数（2, 8, 16）でしか使用できず、また二進数と八進数の表現はそれぞれ’0b’と’0o’のプレフィックスが付きます。

そのため、任意の基数で整数を文字列に変換するためには、カスタム関数を作成する必要があります。その一例が先ほど示したint_to_base関数です。

一方、Pythonのint関数は、文字列と基数を引数に取ることで、その基数の文字列を整数に変換することができます。例えば、int('1010', 2)は二進数の’1010’を整数の10に変換します。

二進数の加算

%%ai vioras
次の2つのプログラムの違いを探してください
---
def add_two_binary_numbers(num1, num2):
    # 数字を二進数の文字列に変換し、逆順にする
    num1 = bin(num1)[2:][::-1]
    num2 = bin(num2)[2:][::-1]
    
    # 2つの数の長さを揃える
    max_len = max(len(num1), len(num2))
    num1 = num1.ljust(max_len, '0')
    num2 = num2.ljust(max_len, '0')
    
    carry = 0
    result = ''

    for i in range(max_len):
        temp = int(num1[i]) + int(num2[i]) + carry
        result += str(temp % 2)
        carry = temp // 2

    if carry > 0:
        result += str(carry)
    
    # 結果を逆順にして返す
    return result[::-1]
---
def add_two_binary_numbers(num1, num2):
    # 数字を二進数の文字列に変換する
    num1 = bin(num1)[2:]
    num2 = bin(num2)[2:]
    
    # 2つの数の長さを揃える
    max_len = max(len(num1), len(num2))
    num1 = num1.zfill(max_len)
    num2 = num2.zfill(max_len)
    
    result = ''
    carry = 0

    for i in range(max_len-1, -1, -1):
        bit1 = int(num1[i])
        bit2 = int(num2[i])
        
        # XOR演算で各ビットを加算する
        sum_bit = bit1 ^ bit2 ^ carry
        
        # ANDと左シフト演算で桁上がりを計算する
        carry = (bit1 & bit2) | (carry & (bit1 ^ bit2))
        
        result = str(sum_bit) + result

    if carry != 0 :
        result = str(carry) + result

    return result
---

2つの関数はどちらも二進数を加算する機能を持ちますが、その内部の処理方法が異なります。

1. 数字を二進数の文字列に変換する部分：

   num1 = bin(num1)[2:][::-1]  # 第1の関数
   num1 = bin(num1)[2:]  # 第2の関数
   

   第1の関数では、二進数の文字列を逆順にしています。それに対して、第2の関数では、二進数の文字列をそのまま使用します。

2. 二進数の加算を行う部分：

   temp = int(num1[i]) + int(num2[i]) + carry  # 第1の関数
   result += str(temp % 2)
   carry = temp // 2
   
   bit1 = int(num1[i])  # 第2の関数
   bit2 = int(num2[i])
   sum_bit = bit1 ^ bit2 ^ carry
   carry = (bit1 & bit2) | (carry & (bit1 ^ bit2))
   result = str(sum_bit) + result
   

   第1の関数では、各桁を順番に加算し（int(num1[i]) + int(num2[i]) + carry）、その結果を2で割った余り（temp % 2）と商（temp // 2）を次の桁の計算に使用しています。これは、通常の十進数の加算と同様の方法です。

   一方、第2の関数では、XOR演算(^)とAND演算(&)を使用して各ビットの加算と桁上がりを計算しています。これは、ビットレベルでの二進数の加算に対応する方法です。具体的には、bit1 ^ bit2 ^ carryはビットの加算を行い、bit1 & bit2とcarry & (bit1 ^ bit2)は桁上がりを計算します。

3. 関数が返す結果の形式：

   return result[::-1]  # 第1の関数
   return result  # 第2の関数
   

   第1の関数では、計算結果の文字列を逆順に戻してから返しています。これは、最初に二進数の文字列を逆順にしたためです。一方、第2の関数では、計算結果の文字列をそのまま返しています。

これらの違いは、主に二進数の加算の方法と結果の形式に関連しています。第1の関数は、通常の十進数の加算と同様の方法を使用していますが、逆順に処理しているため最後に結果を逆順に戻す必要があります。一方、第2の関数は、ビットレベルでの二進数の加算を行い、結果をそのまま返しています。

%%ai vioras
ビットの加算について詳しく

ビットの加算は、一般的な数値の加算と同じように、桁上がりを考慮しながら各ビットを1つずつ加算します。ただし、ビットの加算では2進数を扱うため、各ビットは0または1のみを取ります。

以下に、2ビットの二進数の加算の全ての可能なケースを示します：

• $0 + 0 = 0$

• $0 + 1 = 1$ または $1 + 0 = 1$

• $1 + 1 = 10$（2進数で10は十進数での2に相当）

ここで重要なのは、$1 + 1$の結果が$10$になることです。これは、2ビットの加算で桁上がりが発生する唯一のケースで、最下位ビット（右端）が0で、次の桁に1が繰り上がることを示しています。

ビットの加算では、通常の加算と同様に桁上がりを管理する必要があります。各ステップで、現在のビットの加算結果と前のステップからの桁上がりを加算し、新しい桁上がりを計算します。

ビットの加算は、論理回路設計やコンピュータアーキテクチャ、プログラミングなど、多くの分野で使用されます。特に、コンピュータ内部ではすべての計算がビットレベルで行われるため、ビットの加算は非常に基本的な操作です。

%%ai vioras
XORでビットの加算が処理できるのは何故？

XOR（排他的論理和）演算は、二進数の加算における「加算」部分を表現するのに適しています。これは、XOR演算が2つのビットが異なる場合に1を、同じ場合に0を返すという特性によるものです。これは、ビットの加算とまったく同じ振る舞いです。以下に、XOR演算の真理値表を示します：

| A | B | A XOR B | |—|—|———| | 0 | 0 | 0 | | 0 | 1 | 1 | | 1 | 0 | 1 | | 1 | 1 | 0 |

そして、ビットの加算の結果を見てみると：

• $0 + 0 = 0$

• $0 + 1 = 1$ または $1 + 0 = 1$

• $1 + 1 = 0$（桁上がりを無視した場合）

これは完全にXOR演算の真理値表と一致します。つまり、XOR演算はビットの加算における「加算」部分を正確に表現します。ただし、桁上がりは別途計算する必要があります。それは通常、AND演算とシフト演算を使用して計算します。

%%ai vioras
桁上がり（繰り上がり）処理について詳しく

ビットの加算における桁上がり（または繰り上がり）は、二進数の加算において特定のビットでの加算結果が2（つまり10）以上になったときに発生します。つまり、2つのビットが共に1のときにのみ桁上がりが発生します。

ビットの加算を行う際には、各ビット位置での加算結果と桁上がりを同時に計算する必要があります。そして、それぞれのビット位置での桁上がりは次のビット位置の加算に影響を与えます。

具体的には、以下のような手順でビットの加算と桁上がりを計算します：

1. 各ビット位置での加算（XOR）を行います：$sum = A \oplus B$

2. 各ビット位置での桁上がり（AND）を計算します：$carry = A & B$

3. 次のビット位置に桁上がりを適用します：$A = sum$、$B = carry << 1$

4. 全てのビットで加算が完了するまでステップ1から3を繰り返します。

この方法を用いると、ビットレベルでの加算と桁上がりを正確に計算することができます。この計算は、コンピュータハードウェアの加算器で使われる方法と基本的に同じです。

Note

分かりにくいので、Leibnizの紹介の際に改めて解説します