Pythonで学ぶアルゴリズム 第3弾：基数変換

#Pythonで学ぶアルゴリズム< 基数変換 >#

##はじめに
基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める．
その第3弾として基数変換を扱う．ついでに，ビット演算についても触れる．

##基数変換
10進数を2進数に変えたり，その逆であったりと基数(扱う数字の数)を変換すること．
それらについて実装し，基数変換の復習を行う．

##基数変換 ver.1
まずは，原理に基づいて非常に簡単に10進数を2進数に変換するプログラムを実装する．
コードは次に示す．
#####コード

radix_conversion1.py

"""
2020/12/16
@Yuya Shimizu

基数変換 ver.1
10進数 → 2進数
"""
a = 18
result = ' '

# 10進数 → 2進数
while a > 0:
    result = str(a%2) + result
    a //= 2

print(result)

#####出力

10010 

2進数への変換は10進数で表された数字を2で割っていき，商が0となるまで繰り返した後，その余りを後ろから並べることで，完了する．上記のプログラムでは，while a>0:で繰り返しを表現，文字の合成については後ろから並べられるように，str(a%2)を前にして合成を行っている．
ほかの進数への変換も同様に行うことができるので，ver.2では関数にまとめて，ほかの進数にも変換してみた．ただし，単純なつくりでしかないため，10進数までのものしか表現できない．

##基数変換 ver.2
関数にまとめて，10進数をほかの進数にも変換するプログラムを実装する．
コードは次に示す．
#####コード

radix_conversion2.py

"""
2020/12/16
@Yuya Shimizu

基数変換 ver.2
10進数 → n進数
"""

# 簡単な関数
def convert(n, base):
    result = ' '

    # 10進数 → n進数
    while n > 0:
        result = str(n%base) + result
        n //= base

    print(result)


n = 18
convert(n, 2)
convert(n, 4)
convert(n, 8)

# 用意されている10進数と2進数に関する関数
print(bin(n))

#####出力

10010 
102 
22 
0b10010

関数の中のプログラムはver.1とほぼ変わらない．ただ，2進数への変換はすでに用意された関数でより簡単に変換することができる．bin()である．出力の上端・下端を見れば，確かに2進数に変換されていることが分かる．0bについては後述する．つづいて，ver.3では，2進数を10進数に戻すプログラムを示す．

##基数変換 ver.3
2進数を10進数に戻すプログラムを実装する．
コードは次に示す．
#####コード

radix_conversion3.py

"""
2020/12/16
@Yuya Shimizu

基数変換 ver.3
2進数 → 10進数
"""

# 簡単な関数
def Re_convert(n):
    result = 0
    # 2進数 → 10進数
    for i in range(len(n)):
        result += int(n[i]) * (2**(len(n) - i - 1))

    print(result)


n = '10010'
Re_convert(n)

# 用意されている関数(引数が文字型)
print(int(n, 2))    

# 別の方法
a = 0b10010 #0bをつけることで整数型として扱われる←結果は上と同じ
print(a)

#####出力

18
18
18

すべて同じ結果が得られることが分かる．先ほど同様，用意されている関数int()を使うことができる．第一引数を文字型で表した数字，第二引数が第一引数が2進数であることを示す．そしてint(整数)型として10進数に変換される．
また別の方法もあり，0bをつけることで，整数型として扱われることになる．先ほど，文字型で指定していたが，0bの後ろに2進数を表すと，先ほどの処理を挟まずして，printしたときに10進数を示してくれる．

##ビット演算
論理回路でよく用いられる演算だが，これらについての処理も同様な関数を用いて行うことができるので，ついでに見ておく．ここでは，論理積，論理和，排他的論理和，左シフト，右シフトを扱う．
コードは次に示す．
#####コード

bit_Operation.py

"""
2020/12/16
@Yuya Shimizu

ビット演算
"""
a = 0b10010
b = 0b11001

#ビット反転
print(bin(~a), bin(~b))

#論理積(AND)
print(bin(a & b))

#論理和(OR)
print(bin(a | b))

#排他的論理和(XOR)
print(bin(a ^ b))

#左シフト
print(bin(a << 1))

#右シフト
print(bin(b >> 2))

#####出力

-0b10011 -0b11010
0b10000
0b11011
0b1011
0b100100
0b110

出力は0bを除いてみれば，正しく演算されていることが分かる．

##感想
pythonでビット演算はしたことがなかったので，ビット演算の扱い方が知れたことはよかった．
また，今まで整数変換でしか使っていなかったintが基数変換に使えること，ほかにもbinという関数を知ることもできた．基数変換自体の仕組みについては今までも知っていたが，ここで改めて再確認するよい機会であったと思う．

##参考文献
Pythonで始めるアルゴリズム入門　伝統的なアルゴリズムで学ぶ定石と計算量
　　　　　　　　　　　　　　　　　　　　　　　　 増井 敏克　著　　翔泳社