ハッシュ – 剰余を使った例

2019-08-15 / tau / コメントする

考え方

以下のように考える。

文字列を文字コード化し、眺めのバッファーに先頭から収めていく
バッファーが余った場合は、終わりまで0x00で埋める
バッファー全体を一つの整数として、特定の値で割った余りを求める
余りの下位で適当なバイト数の値を取り出し、ハッシュ値とする

コード全体

上記の考え方を、クラスに実装してみる。テスト用なので、引数やオーバーフローなどのチェックはしていない。

class Hash1():
    """簡単なハッシュを生成するクラス"""

    def __init__(self, st):
        """
        コンストラクター
        引数
        - st：ハッシュ生成対象文字列
        内容
        - 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定
        - 文字列の各文字の文字コードをバッファーの背等から格納

        """
        self.buf = 0
        self.buf_length = 16  # バッファーは16バイト
        self.hash_length = 8  # ハッシュ値は8バイト

        # 文字列中の文字のコードをバッファーに加えていく
        for c in st:
            self.buf <<= 8
            self.buf += ord(c)

        # 文字コードを埋めた後のバッファーのバイト数
        nbytes = self.get_nbytes()

        # バッファーの残り領域を0で埋める
        for n in range(0, self.buf_length - nbytes):
            self.buf = (self.buf << 8) + 0x00

    def __str__(self):
        """インスタンスの文字列化メソッド"""
        return format(self.buf, '0x')

    def get_hash(self, mod_key):
        """
        ハッシュを生成するメソッド
        引数
        - 剰余計算の被除数
        内容
        - バッファーの内容を整数とみなして剰余を計算
        戻り値
        - 16進表示の文字列によるハッシュ値(バイト数を調整)
        """
        hash_value = (self.buf % mod_key)
        return format(hash_value, '0'+str(self.hash_length)+'X')

    def get_nbytes(self):
        """現在のバッファーのバイト数を返すメソッド"""
        bf = self.buf
        nbytes = 0
        while bf != 0:
            nbytes += 1
            bf >>= 8
        return nbytes

class Hash1():

"""簡単なハッシュを生成するクラス"""

def __init__(self, st):

"""

コンストラクター

引数

- st：ハッシュ生成対象文字列

内容

- 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定

- 文字列の各文字の文字コードをバッファーの背等から格納

"""

self.buf = 0

self.buf_length = 16 # バッファーは16バイト

self.hash_length = 8 # ハッシュ値は8バイト

# 文字列中の文字のコードをバッファーに加えていく

for c in st:

self.buf <<= 8

self.buf += ord(c)

# 文字コードを埋めた後のバッファーのバイト数

nbytes = self.get_nbytes()

# バッファーの残り領域を0で埋める

for n in range(0, self.buf_length - nbytes):

self.buf = (self.buf << 8) + 0x00

def __str__(self):

"""インスタンスの文字列化メソッド"""

return format(self.buf, '0x')

def get_hash(self, mod_key):

"""

ハッシュを生成するメソッド

引数

- 剰余計算の被除数

内容

- バッファーの内容を整数とみなして剰余を計算

戻り値

- 16進表示の文字列によるハッシュ値(バイト数を調整)

"""

hash_value = (self.buf % mod_key)

return format(hash_value, '0'+str(self.hash_length)+'X')

def get_nbytes(self):

"""現在のバッファーのバイト数を返すメソッド"""

bf = self.buf

nbytes = 0

while bf != 0:

nbytes += 1

bf >>= 8

return nbytes

この実装例では、バッファーの長さを16バイト、ハッシュのバイト数は下位8バイトとし、余りを計算するための除数は実行時に引数として与えるようにしている。

実行結果

除数で変わる結果

これに適当な文字列と除数を与えてみる。

h = Hash1("My fair lady")
print(h)
print(h.get_hash(0xfedcba98))

# 4d792066616972206c61647900000000
# 723C2FC8

h = Hash1("My fair lady")

print(h)

print(h.get_hash(0xfedcba98))

# 4d792066616972206c61647900000000

# 723C2FC8

1文字だけ変えると、値が大きく変わり、なんとか使えそう。

h = Hash1("my fair lady")
print(h)
print(h.get_hash(0xfedcba98))

# 6d792066616972206c61647900000000
# 5E674DF0

h = Hash1("my fair lady")

print(h)

print(h.get_hash(0xfedcba98))

# 6d792066616972206c61647900000000

# 5E674DF0

簡単な文字列で除数を変えて試してみると、除数を「ややこしそうな値」にするとハッシュはばらつくが、除数の設定によっては入力文字列そのままの値が出たりする。

除数→	0xfedcba98	0xffffffff
A	9ED40708	41000000
AA	24FECD68	41410000
AB	B81E0A58	41420000
AC	4C608CB0	41430000
BA	EB7C9820	42410000
BB	7FBF1A78	42420000
BC	14019CD0	42430000

除数の影響

被除数の値によって、なぜハッシュ値が単純になるのか。

たとえば10進数で以下の様な例を考える。

$\begin{array}{rcrcrcr} 0000 & = & 99 & \times & 0 & + & 0 \\ 0100 & = & 99 & \times & 10 & + & 10 \\ 0200 & = & 99 & \times & 20 & + & 20 \\ & \vdots \\ 9000 & = & 99 & \times & 90 & + & 90 \\ 9100 & = & 99 & \times & 91 & + & 91 \\ & \vdots \\ 9800 & = & 99 & \times & 98 & + & 98 \\ 9900 & = & 99 & \times & 100 & + & 0 \\ \end{array}$

除数未満の値が余りに出ているが、上位桁のパターンがそのまま順番に現れており、先の2進数と同じ結果となっている。

そこで、より簡単な例を考えてみる。

以下の表は、左の列が被除数で、それらに対して最上段の除数で割ったときの余りを示している。被除数の1/2の桁の除数では、7あたりが最も結果がばらつき、その他の値では単純な余りの値が繰り返される。

$\begin{array}{r|ccccccccc} & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 10 & 1 & 2 & 3 & 4 & 0 & 2 & 1 & 0 & 0 \\ 20 & 2 & 4 & 6 & 2 & 0 & 0 & 2 & 0 & 0 \\ 30 & 3 & 6 & 2 & 0 & 0 & 2 & 0 & 0 & 0 \\ 40 & 4 & 0 & 5 & 4 & 0 & 0 & 1 & 0 & 0 \\ 50 & 5 & 2 & 1 & 2 & 0 & 2 & 2 & 0 & 0 \\ 60 & 6 & 4 & 4 & 0 & 0 & 0 & 0 & 0 & 0 \\ 70 & 7 & 6 & 0 & 4 & 0 & 2 & 1 & 0 & 0 \\ 80 & 8 & 0 & 3 & 2 & 0 & 0 & 2 & 0 & 0 \\ 90 & 0 & 2 & 6 & 0 & 0 & 2 & 0 & 0 & 0 \\ \end{array}$

これを細分化すると、余りの値の繰り返しはより顕著であることがわかる。

$\begin{array}{r|ccccccccc} & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 \\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 \\ 2 & 2 & 2 & 2 & 2 & 2 & 2 & 2 & 0 & 0 \\ 3 & 3 & 3 & 3 & 3 & 3 & 3 & 0 & 1 & 0 \\ 4 & 4 & 4 & 4 & 4 & 4 & 0 & 1 & 0 & 0 \\ 5 & 5 & 5 & 5 & 5 & 0 & 1 & 2 & 1 & 0 \\ 6 & 6 & 6 & 6 & 0 & 1 & 2 & 0 & 0 & 0 \\ 7 & 7 & 7 & 0 & 1 & 2 & 3 & 1 & 1 & 0 \\ 8 & 8 & 0 & 1 & 2 & 3 & 0 & 2 & 0 & 0 \\ 9 & 0 & 1 & 2 & 3 & 4 & 1 & 0 & 1 & 0 \\ \end{array}$

先のコードは、上記の例で言えば除数を9に設定した場合に、その結果がきれいにもとの値と同じとなることに相当する。

衝突状況のチェック

除数を変化させて、アルファベット大文字１～４文字の文字列でハッシュ値の衝突が出るか確認してみた。各文字数に対するバリエーションの数は以下の通り。

１文字→26通り
２文字→26*26=676通り
３文字→26*26*26=17,576通り
４文字→26*26*26*26=456,976通り
合計、475,254通り

import string

.....

hash_dict = {}

al = string.ascii_uppercase
modkey = 0xffffffff

for c1 in al:
    h1 = Hash1(c1).get_hash(modkey)
    if not(h1 in hash_dict): hash_dict[h1] = []
    hash_dict[h1].append(c1)
    for c2 in al:
        s2 = c1 + c2
        h2 = Hash1(s2).get_hash(modkey)
        if not(h2 in hash_dict): hash_dict[h2] = []
        hash_dict[h2].append(s2)
        for c3 in al:
            s3 = c1 + c2 + c3
            h3 = Hash1(s3).get_hash(modkey)
            if not(h3 in hash_dict): hash_dict[h3] = []
            hash_dict[h3].append(s3)
            for c4 in al:
                s4 = c1 + c2 + c3 + c4
                h4 = Hash1(s4).get_hash(modkey)
                if not(h4 in hash_dict): hash_dict[h4] = []
                hash_dict[h4].append(s4)

for itm in list(hash_dict.items()):
    if len(itm[1]) > 1:
        print('{} : {}'.format(itm[0], itm[1]))

import string

.....

hash_dict = {}

al = string.ascii_uppercase

modkey = 0xffffffff

for c1 in al:

h1 = Hash1(c1).get_hash(modkey)

if not(h1 in hash_dict): hash_dict[h1] = []

hash_dict[h1].append(c1)

for c2 in al:

s2 = c1 + c2

h2 = Hash1(s2).get_hash(modkey)

if not(h2 in hash_dict): hash_dict[h2] = []

hash_dict[h2].append(s2)

for c3 in al:

s3 = c1 + c2 + c3

h3 = Hash1(s3).get_hash(modkey)

if not(h3 in hash_dict): hash_dict[h3] = []

hash_dict[h3].append(s3)

for c4 in al:

s4 = c1 + c2 + c3 + c4

h4 = Hash1(s4).get_hash(modkey)

if not(h4 in hash_dict): hash_dict[h4] = []

hash_dict[h4].append(s4)

for itm in list(hash_dict.items()):

if len(itm[1]) > 1:

print('{} : {}'.format(itm[0], itm[1]))

その結果は次の通り。

0xFEDCBA98
アルファベット１～４文字で衝突なし。

0xFEDCBA9
まだ衝突なし。

0xFEDCBA
衝突が多数発生。みな2つの文字列で衝突。たとえば
0071BB5E : [‘SZQA’, ‘ZRZW’]
003C0D52 : [‘SZQB’, ‘ZRZX’]
00065F46 : [‘SZQC’, ‘ZRZY’]
00CF8DF4 : [‘SZQD’, ‘ZRZZ’]
除数の10進値は16,702,650と文字列のバリエーションより大きいが、衝突が出始めた。

0xFFFFFFFF
意外にも衝突なし。

0xFFFFFFF
衝突が多数発生。これも2つの文字列で重複。たとえば
05A5CA5A : [‘JZZX’, ‘ZZZW’]
05A5DA5A : [‘JZZY’, ‘ZZZX’]
05A5EA5A : [‘JZZZ’, ‘ZZZY’]
除数の10進値は268,435,455とかなり大きいが、単純なパターンの値ほど衝突が起こりやすいのかもしれない。

コード詳細

コンストラクタinit()

インスタンス生成時にハッシュを生成する文字列を受け取り、空のバッファーを準備
バッファーの長さを16バイト、ハッシュ値の長さを8バイトに設定
引数で与えられた文字列から1文字ずつ取り出し、文字コードを追加
バッファー長までの余った部分に0を追加

    def __init__(self, st):
        """
        コンストラクター
        引数
        - st：ハッシュ生成対象文字列
        内容
        - 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定
        - 文字列の各文字の文字コードをバッファーの背等から格納

        """
        self.buf = 0
        self.buf_length = 16  # バッファーは16バイト
        self.hash_length = 8  # ハッシュ値は8バイト

        # 文字列中の文字のコードをバッファーに加えていく
        for c in st:
            self.buf <<= 8
            self.buf += ord(c)

        # 文字コードを埋めた後のバッファーのバイト数
        nbytes = self.get_nbytes()

        # バッファーの残り領域を0で埋める
        for n in range(0, self.buf_length - nbytes):
            self.buf = (self.buf << 8) + 0x00

def __init__(self, st):

"""

コンストラクター

引数

- st：ハッシュ生成対象文字列

内容

- 作業用のバッファーを準備しバッファーとハッシュ値の長さ(バイト数)を設定

- 文字列の各文字の文字コードをバッファーの背等から格納

"""

self.buf = 0

self.buf_length = 16 # バッファーは16バイト

self.hash_length = 8 # ハッシュ値は8バイト

# 文字列中の文字のコードをバッファーに加えていく

for c in st:

self.buf <<= 8

self.buf += ord(c)

# 文字コードを埋めた後のバッファーのバイト数

nbytes = self.get_nbytes()

# バッファーの残り領域を0で埋める

for n in range(0, self.buf_length - nbytes):

self.buf = (self.buf << 8) + 0x00

内部用メソッドget_nbytes()

文字コードを追加し終わったときのバッファー長を計算する処理を独立させたメソッド。

    def get_nbytes(self):
        """現在のバッファーのバイト数を返すメソッド"""
        bf = self.buf
        nbytes = 0
        while bf != 0:
            nbytes += 1
            bf >>= 8
        return nbytes

def get_nbytes(self):

"""現在のバッファーのバイト数を返すメソッド"""

bf = self.buf

nbytes = 0

while bf != 0:

nbytes += 1

bf >>= 8

return nbytes

ハッシュ値計算get_hash()

バッファーの内容を整数として、引数で与えられた除数から剰余を計算する
計算結果の下位バイトを取り出して、ハッシュ値として返す

    def get_hash(self, mod_key):
        """
        ハッシュを生成するメソッド
        引数
        - 剰余計算の被除数
        内容
        - バッファーの内容を整数とみなして剰余を計算
        戻り値
        - 16進表示の文字列によるハッシュ値(バイト数を調整)
        """
        hash_value = (self.buf % mod_key)
        return format(hash_value, '0'+str(self.hash_length)+'X')

def get_hash(self, mod_key):

"""

ハッシュを生成するメソッド

引数

- 剰余計算の被除数

内容

- バッファーの内容を整数とみなして剰余を計算

戻り値

- 16進表示の文字列によるハッシュ値(バイト数を調整)

"""

hash_value = (self.buf % mod_key)

return format(hash_value, '0'+str(self.hash_length)+'X')

文字列化メソッドstr()

インスタンスの文字列化メソッド。

    def __str__(self):
        """インスタンスの文字列化メソッド"""
        return format(self.buf, '0x')

def __str__(self):

"""インスタンスの文字列化メソッド"""

return format(self.buf, '0x')

ハッシュ – 簡単すぎる例

2019-08-15 / tau / コメントする

ハッシュ関数のイメージを掴むために、簡単な例を考えてみる。

まず、任意の文字列が与えられたとき、文字列中の全ての文字コードを加えた値を返す関数を考える。

# hash_0.py
# 任意の文字列のhashを返す関数。
# 文字列中の文字コードを単純に足し込んでいく
def make_hash(str):
    buffer = 0
    char_list = list(str)

    # すべての文字のコードを加える
    for c in char_list:
        buffer += ord(c)

    # 加えた結果を16進文字列にして返す
    return(format(buffer, 'X'))

# hash_0.py

# 任意の文字列のhashを返す関数。

# 文字列中の文字コードを単純に足し込んでいく

def make_hash(str):

buffer = 0

char_list = list(str)

# すべての文字のコードを加える

for c in char_list:

buffer += ord(c)

# 加えた結果を16進文字列にして返す

return(format(buffer, 'X'))

この関数を以下のような文字列で実行すると、1文字加えたり入れ替えただけで結果が違ってくるのがわかる。

print(make_hash("America"))  # 2B2
print(make_hash("American")) # 320
print(make_hash("america"))  # 2D2

print(make_hash("America")) # 2B2

print(make_hash("American")) # 320

print(make_hash("america")) # 2D2

長い文字列で試してみると、1文字入れ替えると値が変わってくるが、1文字分の足し込むコードが変わるだけなので、大きな変化は期待できない。

print(make_hash("The rain in Spain stays mainly in the plain.")) # FB5
print(make_hash("The rain in spain stays mainly in the plain.")) # FD5

1 2	print(make_hash("The rain in Spain stays mainly in the plain.")) # FB5 print(make_hash("The rain in spain stays mainly in the plain.")) # FD5

この方法で致命的なのは、同種の文字を順序違いで並べても結果が同じになる点。

print(make_hash("AB")) # 83
print(make_hash("BA")) # 83

1 2	print(make_hash("AB")) # 83 print(make_hash("BA")) # 83

このやり方は、あまりに単純すぎて使えない。

Python3 – 文字列とリストの相互変換

2019-08-12 / tau / コメントする

文字列からリストへの変換

s = 'string'
lst = list(s)
print(lst) # ['s', 't', 'r', 'i', 'n', 'g']

s = 'string'

lst = list(s)

print(lst) # ['s', 't', 'r', 'i', 'n', 'g']

リストから文字列への変換

lst = ['s', 't', 'r', 'i', 'n', 'g']
print("".join(lst)) # string

1 2	lst = ['s', 't', 'r', 'i', 'n', 'g'] print("".join(lst)) # string

リストから文字列に変換するときに、区切り文字を指定できる。

lst = ['s', 't', 'r', 'i', 'n', 'g']
print("-".join(lst)) # s-t-r-i-n-g

1 2	lst = ['s', 't', 'r', 'i', 'n', 'g'] print("-".join(lst)) # s-t-r-i-n-g

区切りは2文字以上でもok。

lst = ['s', 't', 'r', 'i', 'n', 'g']
print(", ".join(lst)) # s, t, r, i, n, g

1 2	lst = ['s', 't', 'r', 'i', 'n', 'g'] print(", ".join(lst)) # s, t, r, i, n, g

Python3 – 文字を順に取り出す

2019-08-11 / tau / コメントする

数字やアルファベットの文字を順に取り出して使いたい時、stringモジュールを使うと便利。

import string

print(string.digits)
print(string.octdigits)
print(string.hexdigits)
print(string.ascii_uppercase)
print(string.ascii_lowercase)
print(string.ascii_letters)
print(string.punctuation)

# 0123456789
# 01234567
# 0123456789abcdefABCDEF
# ABCDEFGHIJKLMNOPQRSTUVWXYZ
# abcdefghijklmnopqrstuvwxyz
# abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
# !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

import string

print(string.digits)

print(string.octdigits)

print(string.hexdigits)

print(string.ascii_uppercase)

print(string.ascii_lowercase)

print(string.ascii_letters)

print(string.punctuation)

# 0123456789

# 01234567

# 0123456789abcdefABCDEF

# ABCDEFGHIJKLMNOPQRSTUVWXYZ

# abcdefghijklmnopqrstuvwxyz

# abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ

# !"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

2の補数

2019-07-28 / tau / コメントする

簡単なケース

正の数の表現

桁数が固定された2進数の加算を考える。たとえば4桁(4 bits)の場合に1ずつ加える。

$\begin{array}{cc} 0000 + 0001 = 0001 & (1)\\ 0001 + 0001 = 0010 & (2)\\ 0010 + 0001 = 0011 & (3)\\ 0011 + 0001 = 0100 & (4)\\ 0100 + 0001 = 0101 & (5)\\ 0101 + 0001 = 0110 & (6)\\ 0110 + 0001 = 0111 & (7) \end{array}$

負の数の表現

一方、-1は0から1を引いた値として計算される。最初の計算だけ、上位桁から1を借りてこられるとして、以下の様な計算になる。

$\begin{array}{cc} 0000 - 0001 = 1111 & (-1)\\ 1111 - 0001 = 1110 & (-2)\\ 1110 - 0001 = 1101 & (-3)\\ 1101 - 0001 = 1100 & (-4)\\ 1100 - 0001 = 1011 & (-5)\\ 1011 - 0001 = 1010 & (-6)\\ 1010 - 0001 = 1001 & (-7)\\ 1001 - 0001 = 1000 & (-8) \end{array}$

上の足し算の結果と下の引き算の結果をを見ると、以下のことがわかる。

正の数(0～7)と負の数(-8～-1)の合計15個で、4ビットの全てのパターンが網羅されている
正の数の最上位ビットは0、負の数の最上位ビットは1

引き算と補数の足し算

たとえば上の例で、正の数と負の数を加えてみる。

$\begin{array}{cl} 0101 + 1110 = 0011 & (5-2=3) \\ 0011 + 1001 = 1100 & (3-7=-4) \\ 1111 + 1100 = 1011 & (-1-4=-5) \end{array}$

2の補数を計算したときに0からその数を減じているので、当然の結果ではある。いずれにしても、負数を2の補数で表現することで、減算を加算で代えることができる。

2の補数を得る方法

2の補数を得るのに、いちいち0から引かなくても、以下の方法で可能。

整数のビットパターンを反転
1を加える

4ビットの例では以下のとおり。

$\begin{array}{cc} 0001 \rightarrow 1110 \rightarrow 1111 & (-1)\\ 0010 \rightarrow1101 \rightarrow 1110 & (-2)\\ 0011 \rightarrow1100 \rightarrow 1101 & (-3)\\ 0100 \rightarrow1011 \rightarrow 1100 & (-4)\\ 0101 \rightarrow1010 \rightarrow 1011 & (-5)\\ 0110 \rightarrow1001 \rightarrow 1010 & (-6)\\ 0111 \rightarrow1000 \rightarrow 1001 & (-7)\\ 1000 \rightarrow0111 \rightarrow 1000 & (-8)\\ \end{array}$

すなわち、固定長の整数の場合、ビット反転と加算機能があれば、減算を実現できる。

典型的なビット数の整数範囲

8ビット

byte型でよく見る値。

$\begin{array}{lllr} 0111\:1111 = &2^7 - 1 &=& 127 \\ 1000\:0000 = &-2^7 &=& -128 \end{array}$

16ビット

short型でよく見る値。

$\begin{array}{lllr} 0111\:1111\:1111\:1111 = &2^{15} - 1 &= &32767 \\ 1000\:0000\:0000\:0000 = &-2^{15} &= &-32768 \end{array}$

32ビット

一般的なint型で絶対値が約21億。

$\begin{array}{llr} 2^{31} - 1 &=& ‭2,147,483,647 \\ -2^{31} &=& -‭2,147,483,648‬ \end{array}$

64ビット

long型、絶対値が約920京（！）

$\begin{array}{llr} 2^{63} - 1 &=& ‭9,223,372,036,854,775,807 \\ -2^{63} &=& -‭9,223,372,036,854,775,808‬ \end{array}$

Python3 – 数値と文字列の相互変換

2019-07-28 / tau / コメントする

数値から文字列への変換

10進数(str関数)

str関数で引数の数値を文字列化。

整数の場合、桁数が多くてもそのまま文字列化される。

>>> str(1234)
'1234'
>>> str(12345678901234567890)
'12345678901234567890'

>>> str(1234)

'1234'

>>> str(12345678901234567890)

'12345678901234567890'

実数の場合は有効数値で丸められる。

>>> str(123.45678901234567890)
'123.45678901234568'

1 2	>>> str(123.45678901234567890) '123.45678901234568'

浮動小数点で与えると、桁数が収まる範囲で固定少数表示の文字列になる。

>>> str(1e3)
'1000.0'
>>> str(1e15)
'1000000000000000.0'
>>> str(1e16)
'1e+16'

>>> str(1e3)

'1000.0'

>>> str(1e15)

'1000000000000000.0'

>>> str(1e16)

'1e+16'

2進数、8進数、16進数

組み込み関数を使う方法

bin、oct、hex関数を使った場合、プレフィックス’0b’、’0o’、’0x’がついた文字列になる。

>>> bin(31)
'0b11111'
>>> oct(4095)
'0o7777'
>>> hex(65535)
'0xffff'

>>> bin(31)

'0b11111'

>>> oct(4095)

'0o7777'

>>> hex(65535)

'0xffff'

format関数を使う方法

format関数の第2引数に基数に対応した文字を指定する。

>>> format(255, 'b')
'11111111'
>>> format(255, 'o')
'377'
>>> format(255, 'x')
'ff'
>>> format(255, 'X')
'FF'

>>> format(255, 'b')

'11111111'

>>> format(255, 'o')

'377'

>>> format(255, 'x')

'ff'

>>> format(255, 'X')

'FF'

第2引数で、桁数を指定して空いた上位桁を0で埋めることができる。

>>> format(15, '08b')
'00001111'
>>> format(15, '04o')
'0017'
>>> format(15, '02x')
'0f'

>>> format(15, '08b')

'00001111'

>>> format(15, '04o')

'0017'

>>> format(15, '02x')

'0f'

書式文字列を使う方法

書式文字列と％演算子を使っても、数値を文字列化できるが、2進数には対応していない。

>>> '%#o' % 255, '%o' % 255
('0o377', '377')
>>> '%#x' % 255, '%x' % 255
('0xff', 'ff')
>>> '%#X' % 255, '%X' % 255
('0XFF', 'FF')

>>> '%#o' % 255, '%o' % 255

('0o377', '377')

>>> '%#x' % 255, '%x' % 255

('0xff', 'ff')

>>> '%#X' % 255, '%X' % 255

('0XFF', 'FF')

文字列から数値への変換

10進数

整数(int関数)

int関数は整数の文字列を数値化するが、実数形式の文字列を与えるとエラーになる。

>>> int('1234')
1234
>>> int('1.')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: invalid literal for int() with base 10: '1.'

>>> int('1234')

1234

>>> int('1.')

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ValueError: invalid literal for int() with base 10: '1.'

実数(float関数)

float関数は実数の文字列を数値化する。固定小数点/浮動小数点のどちらの表現でもかまわない。

>>> float('1234')
1234.0
>>> float('1.234')
1.234
>>> float('1e15')
1000000000000000.0
>>> float('1e16')
1e+16

>>> float('1234')

1234.0

>>> float('1.234')

1.234

>>> float('1e15')

1000000000000000.0

>>> float('1e16')

1e+16

2進数、8進数、16進数

int関数の第2引数で基数を指定する。

>>> int('1111', 2)
15
>>> int('7777', 8)
4095
>>> int('FFFF', 16)
65535

>>> int('1111', 2)

>>> int('7777', 8)

4095

>>> int('FFFF', 16)

65535

第2引数には2～36まで指定可能で、0～9とA～Zまで使った36進法まで変換可能。

>>> int('1000', 1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ValueError: int() base must be >= 2 and <= 36
>>> int('1000', 3)
27
>>> int('GGGG', 17)
83520
>>> int('ZZZZ', 36)
1679615

>>> int('1000', 1)

Traceback (most recent call last):

File "<stdin>", line 1, in <module>

ValueError: int() base must be >= 2 and <= 36

>>> int('1000', 3)

>>> int('GGGG', 17)

83520

>>> int('ZZZZ', 36)

1679615

‘0b’、’0o’、’0x’のプレフィックスを付けた文字列を変換するときは、第2引数を0にする。この場合、10進数も変換可能。

>>> int('0x1111', 0)
4369
>>> int('0x7777', 0)
30583
>>> int('0xFFFF', 0)
65535
>>> int('9999', 0)
9999

>>> int('0x1111', 0)

4369

>>> int('0x7777', 0)

30583

>>> int('0xFFFF', 0)

65535

>>> int('9999', 0)

9999

Python3 – 数値

2019-07-27 / tau / コメントする

int型

整数型はintで表される。

>>> print(type(1), 1)
<class 'int'> 1

1 2	>>> print(type(1), 1) <class 'int'> 1

桁数が多くなってもint型として扱われる。

>>> print(type(1000000000000000000000000000000), 1000000000000000000000000000000)
<class 'int'> 1000000000000000000000000000000

1 2	>>> print(type(1000000000000000000000000000000), 1000000000000000000000000000000) <class 'int'> 1000000000000000000000000000000

int型のチェック

>>> print(type(1)==int)
True

1 2	>>> print(type(1)==int) True

float型

数値リテラルに小数点を付けるとfloat型として扱われる。float型はCやFORTRANの倍精度の精度。

>>> print(type(1.), 1.)
<class 'float'> 1.0

1 2	>>> print(type(1.), 1.) <class 'float'> 1.0

‘/’による除算の結果は常にfloat型になる。

>>> print(type(6/3), 6/3)
<class 'float'> 2.0

1 2	>>> print(type(6/3), 6/3) <class 'float'> 2.0

‘//’による除算では商が整数化される(整数除算と剰余を参照)。

>>> print(type(8//3), 8//3)
<class 'int'> 2

1 2	>>> print(type(8//3), 8//3) <class 'int'> 2

Python3 – 書式設定～format

2019-07-27 / tau / コメントする

format関数

一つの数値・文字列の書式を設定する場合、format組み込み関数が使える。引数はリテラルでも変数でもよい。

print("Hexadecimal of 255 is " + format(255, '0x'))
print("1/7 is approximately " + format(1/7, 'e'))


# Hexadecimal of 255 is ff
# 1/7 is approximately 1.428571e-01

print("Hexadecimal of 255 is " + format(255, '0x'))

print("1/7 is approximately " + format(1/7, 'e'))

# Hexadecimal of 255 is ff

# 1/7 is approximately 1.428571e-01

formatメソッド

文字列に対するformatメソッドでも数値・文字列の書式を設定できる（書式設定の書き方は後述）。引数はリテラルでも変数でもよい。

print("Hexadecimal of 255 is {:0x}".format(255))
print("Hexadecimal of 255 is {:e}".format(1/7))

# Hexadecimal of 255 is ff
# Hexadecimal of 255 is 1.428571e-01

print("Hexadecimal of 255 is {:0x}".format(255))

print("Hexadecimal of 255 is {:e}".format(1/7))

# Hexadecimal of 255 is ff

# Hexadecimal of 255 is 1.428571e-01

formatメソッドは複数の数値・文字列を扱える。

print("My name is {} and my age is {}".format("Jane", 38))

# My name is Jane and my age is 38

print("My name is {} and my age is {}".format("Jane", 38))

# My name is Jane and my age is 38

位置引数として整数を指定し、繰り返して利用することが可能。

print("The suits of handed cards were {0}, {1}, {2}, {1}, {3}" \
    .format("Spade", "Club", "Diamond", "Heart".))

# The suits of handed cards were Spade, Club, Diamond, Club, Heart.

print("The suits of handed cards were {0}, {1}, {2}, {1}, {3}" \

.format("Spade", "Club", "Diamond", "Heart".))

# The suits of handed cards were Spade, Club, Diamond, Club, Heart.

キーワード引数として文字列を指定可能。

print("{name} is {age} years old.".format(name="Kark", age=25))

# Kark is 25 years old.

print("{name} is {age} years old.".format(name="Kark", age=25))

# Kark is 25 years old.

リストを引数にするときは整数の位置引数とリスト内の引数で指定する。複数のリストを指定するときは位置引数を0、1…と対応させていく。

result1 = ["Head", "Tail"]
result2 = ["Head", "Head"]
print("First result was {0[0]} and {0[1]}.\nSecond was {1[0]} and {1[1]}.".\
    format(result1, result2))

# First result was Head and Tail.
# Second was Head and Head.

result1 = ["Head", "Tail"]

result2 = ["Head", "Head"]

print("First result was {0[0]} and {0[1]}.\nSecond was {1[0]} and {1[1]}.".\

format(result1, result2))

# First result was Head and Tail.

# Second was Head and Head.

辞書を引数にするときは整数の位置引数とキーで指定する。キーはクォートで囲まない。

person1 = {'name': "John", 'age': 20}
person2 = {'name': "Kate", 'age': 32}
print("{0[name]} is {0[age]} years old) and {1[name]} is {1[age]} years old.".\
    format(person1, person2))

# John is 20 years old) and Kate is 32 years old.

person1 = {'name': "John", 'age': 20}

person2 = {'name': "Kate", 'age': 32}

print("{0[name]} is {0[age]} years old) and {1[name]} is {1[age]} years old.".\

format(person1, person2))

# John is 20 years old) and Kate is 32 years old.

書式設定する場合は、[位置引数]:[書式設定文字列]の形式にする。位置引数を指定しない場合でも':'は必要。

print("1/4 is {0:f} and 1/5 is {1:e}".format(1/4, 1/5))
print("1/4 is {:f} and 1/5 is {:e}".format(1/4, 1/5))

# 1/4 is 0.250000 and 1/5 is 2.000000e-01
# 1/4 is 0.250000 and 1/5 is 2.000000e-01

print("1/4 is {0:f} and 1/5 is {1:e}".format(1/4, 1/5))

print("1/4 is {:f} and 1/5 is {:e}".format(1/4, 1/5))

# 1/4 is 0.250000 and 1/5 is 2.000000e-01

書式設定文字列

formatメソッド

位置引数を省略して書式設定文字列を各場合{:[書式設定文字列]}のように':'を省略することができない。

文字列

{:[</^/>][width]}で左寄せ／中央ぞろえ／右寄せと、全体の幅widthを指定。

str = "Python"

print("left  :{:<10}".format(str))
print("center:{:^10}".format(str))
print("right :{:>10}".format(str))

# left  :Python
# center:  Python
# right :    Python

str = "Python"

print("left :{:<10}".format(str))

print("center:{:^10}".format(str))

print("right :{:>10}".format(str))

# left :Python

# center: Python

# right : Python

{:[char][</^/>][width]}で空白部分をcharの文字でパディング

print("left  :{:*<10}".format(str))
print("center:{:*^10}".format(str))
print("right :{:*>10}".format(str))

# left  :Python****
# center:**Python**
# right :****Python

print("left :{:*<10}".format(str))

print("center:{:*^10}".format(str))

print("right :{:*>10}".format(str))

# left :Python****

# center:**Python**

# right :****Python

整数

整数の書式は幅の値に'd'を続けて書く。

print("{:*<10d}".format(123))
print("{:*^10d}".format(123))
print("{:*>10d}".format(123))

# 123*******
# ***123****
# *******123

print("{:*<10d}".format(123))

print("{:*^10d}".format(123))

print("{:*>10d}".format(123))

# 123*******

# ***123****

# *******123

整数を2進数、8進数、16進数で表現できる。

print("{:d}".format(255))
print("{:b}".format(255))
print("{:o}".format(255))
print("{:x}".format(255))
print("{:X}".format(255))

# 255
# 11111111
# 377
# ff
# FF

print("{:d}".format(255))

print("{:b}".format(255))

print("{:o}".format(255))

print("{:x}".format(255))

print("{:X}".format(255))

# 255

# 11111111

# 377

# ff

# FF

基数を指定するとき、'#'を前置すると0b、0o、0xが前に付加される。以下の例では、同時に幅も指定している。2進数表現の場合は0bを付加すると設定幅を超えるので、そのまま表示されている。

print("{:#8b}".format(255))
print("{:#8o}".format(255))
print("{:#8x}".format(255))
print("{:#8X}".format(255))

# 0b11111111
#    0o377
#     0xff
#     0XFF

print("{:#8b}".format(255))

print("{:#8o}".format(255))

print("{:#8x}".format(255))

print("{:#8X}".format(255))

# 0b11111111

# 0o377

# 0xff

# 0XFF

浮動小数点

浮動小数点形式の実数の書式は、小数部の桁数だけ指定するときは".3f"のように、幅を設定するときは"10.3f"のように指定する。

print("{:*<10.3f}".format(12.3454))
print("{:*^10.3f}".format(12.3455))
print("{:*>10.3f}".format(12.3456))

# 12.345****
# **12.345**
# ****12.346

print("{:*<10.3f}".format(12.3454))

print("{:*^10.3f}".format(12.3455))

print("{:*>10.3f}".format(12.3456))

# 12.345****

# **12.345**

# ****12.346

固定小数点

固定小数点形式の実数の書式は、小数部の桁数だけ指定するときは".5e"のように、幅を指定するときは"15.5e"のように指定する。

# 固定小数点型
print("{:*<15.3e}".format(1.2344e-10))
print("{:*^15.3e}".format(1.2345e-10))
print("{:*>15.3e}".format(1.2346e-10))

# 1.234e-10******
# ***1.234e-10***
# ******1.235e-10

# 固定小数点型

print("{:*<15.3e}".format(1.2344e-10))

print("{:*^15.3e}".format(1.2345e-10))

print("{:*>15.3e}".format(1.2346e-10))

# 1.234e-10******

# ***1.234e-10***

# ******1.235e-10

符号の表示方法

正の数値に対して'+'を表示させるときは、数値書式の前に'+'をつけ、正の時にスペースを表示させるときには' 'をつける。

print("{:*>10d}".format(123))
print("{:*>10d}".format(-123))
print("{:*>+10d}".format(123))
print("{:*>+10d}".format(-123))
print("{:*> 10d}".format(123))
print("{:*> 10d}".format(-123))

# *******123
# ******-123
# ******+123
# ******-123
# ****** 123
# ******-123

print("{:*>10d}".format(123))

print("{:*>10d}".format(-123))

print("{:*>+10d}".format(123))

print("{:*>+10d}".format(-123))

print("{:*> 10d}".format(123))

print("{:*> 10d}".format(-123))

# *******123

# ******-123

# ******+123

# ******-123

# ****** 123

# ******-123

指定した幅の先頭に符号等を表示し、右寄せの数値との間をパディングする方法。

print("{:*=10.3f}".format(12.345))
print("{:*=10.3f}".format(-12.345))
print("{:*=+10.3f}".format(12.345))
print("{:*= 10.3f}".format(12.345))

# ****12.345
# -***12.345
# +***12.345
#  ***12.345

print("{:*=10.3f}".format(12.345))

print("{:*=10.3f}".format(-12.345))

print("{:*=+10.3f}".format(12.345))

print("{:*= 10.3f}".format(12.345))

# ****12.345

# -***12.345

# +***12.345

# ***12.345

format関数

基数表示

数値の基数を指定して、10進数、2進数、8進数、16進数を表示。16進数は英文字の大文字/小文字を選択可能。

print(format(255, 'd')) #255
print(format(255, 'b')) #11111111
print(format(255, 'o')) #377
print(format(255, 'x')) #ff
print(format(255, 'X')) #FF

print(format(255, 'd')) #255

print(format(255, 'b')) #11111111

print(format(255, 'o')) #377

print(format(255, 'x')) #ff

print(format(255, 'X')) #FF

位置揃え

文字列や数値を固定幅の中で左寄せ、センタリング、右寄せ（センタリングで左右幅が異なるときは、左に1桁寄せられる）。

print(format("Python", '<10s')) #Python
print(format("Python", '^10s')) #  Python
print(format("Python", '>10s')) #    Python

print(format(123, '<6d'))   #123
print(format(123, '^6d'))   # 123
print(format(123, '>6d'))   #   123

print(format("Python", '<10s')) #Python

print(format("Python", '^10s')) # Python

print(format("Python", '>10s')) # Python

print(format(123, '<6d')) #123

print(format(123, '^6d')) # 123

print(format(123, '>6d')) # 123

パディング

数値を固定幅で表示した場合のデフォルトは右寄せ。'[任意の文字]=’で空白をパディング。特にゼロで埋める場合は’=’を省略できる。

print(format(123, '6d'))    #   123
print(format(123, '*=6d'))  #***123
print(format(123, '0=6d'))  #000123
print(format(123, '06d'))   #000123

print(format(123, '6d')) # 123

print(format(123, '*=6d')) #***123

print(format(123, '0=6d')) #000123

print(format(123, '06d')) #000123

2、8、16の基数に対して固定幅で0でパディングする例。

print(format(15, '08b'))    #00001111
print(format(15, '04o'))    #0017
print(format(143, '04x'))   #008f
print(format(143, '04X'))   #008F

print(format(15, '08b')) #00001111

print(format(15, '04o')) #0017

print(format(143, '04x')) #008f

print(format(143, '04X')) #008F

+符号

‘+’を指定すると、正の値の時に+記号がつく。

print(format(456, '+6d'))   #  +456
print(format(-456, '+6d'))  #  -456
print(format(-456, '+06d')) #-00456
# '0+6d'はエラー

print(format(456, '+6d')) # +456

print(format(-456, '+6d')) # -456

print(format(-456, '+06d')) #-00456

# '0+6d'はエラー

カンマ区切り

3桁ごとのカンマ区切り指定。

print(format(123456789, ','))   #123,456,789
print(format(123456789, '15,')) #    123,456,789

1 2	print(format(123456789, ',')) #123,456,789 print(format(123456789, '15,')) # 123,456,789

固定小数点実数

固定小数点の小数部の桁数を’.[桁数]f’で指定する。

print(format(123.456789, '.3f'))  #123.457
print(format(123.456789, '.10f')) #123.4567890000

1 2	print(format(123.456789, '.3f')) #123.457 print(format(123.456789, '.10f')) #123.4567890000

浮動小数点実数

浮動小数点の小数部の桁数を’.[桁数]e’で指定する。

print(format(123.456, '.0e'))   #1.e+02
print(format(123.456, '.1e'))   #1.2e+02
print(format(123.456, '.2e'))   #1.23e+02
print(format(123.456, '.3e'))   #1.235e+02

print(format(123.456, '.0e')) #1.e+02

print(format(123.456, '.1e')) #1.2e+02

print(format(123.456, '.2e')) #1.23e+02

print(format(123.456, '.3e')) #1.235e+02

実数全体の桁数

小数部の桁数ではなく全体の桁数を’.[桁数]g’で指定する。全体の桁数が整数部の桁数以上のときは、固定小数点で表示される。

print(format(123.456, '.0g'))   #1e+02
print(format(123.456, '.1g'))   #1e+02
print(format(123.456, '.2g'))   #1.2e+02
print(format(123.456, '.3g'))   #123
print(format(123.456, '.4g'))   #123.5
print(format(123.456, '.5g'))   #123.46

print(format(123.456, '.0g')) #1e+02

print(format(123.456, '.1g')) #1e+02

print(format(123.456, '.2g')) #1.2e+02

print(format(123.456, '.3g')) #123

print(format(123.456, '.4g')) #123.5

print(format(123.456, '.5g')) #123.46

Python3 – 整数除算と剰余（//, %）

2019-07-22 / tau / 1件のコメント

//演算子

//演算子は、切り捨て除算と言われることが多いが、正確には小数部の切り捨てではなく、除算値を超えない最大の整数となる。これは実数の除算結果にfloorを適用した値と同じで、除算結果が負の時に注意を要する。

import math

print(8/3)
print(8//3)
print(math.floor(8/3))

# 2.6666666666666665
# 2
# 2

print(-7/3)
print(-7//3)
print(math.floor(-7/3))

# -2.3333333333333335
# -3
# -3

import math

print(8/3)

print(8//3)

print(math.floor(8/3))

# 2.6666666666666665

# 2

print(-7/3)

print(-7//3)

print(math.floor(-7/3))

# -2.3333333333333335

# -3

なお、被除数・除数の何れがマイナスかは問わず、計算結果がマイナスかどうかだけによる。

%演算子

%演算子は、引数の剰余(mod)を与える。除数の正負によって挙動が異なる点に注意。

print(13%3)     # 1
print(-13%3)    # 2
print(13%(-3))  # -2
print(-13%(-3)) # -1

print(13%3) # 1

print(-13%3) # 2

print(13%(-3)) # -2

print(-13%(-3)) # -1

除数が正のとき剰余は正となり、除数が負のときは剰余は負となる。

$\begin{array}{lcl} 13 \% 3 = 1 & \Rightarrow & 13 = 3 \times 4 + 1 \\ -13 \% 3 = 2 & \Rightarrow & -13 = 3 \times (-5) + 2 \\ 13 \% (-3) = -2 & \Rightarrow & 13 = -3 \times (-5) - 2 \\ -13 \% (-3) = -1 & \Rightarrow & -13 = -3 \times 4 -1 \end{array}$

Python3 – 組み込み関数

2019-07-21 / tau / コメントする

range関数

zip関数

map関数

考え方

コード全体

実行結果

除数で変わる結果

除数の影響

衝突状況のチェック

コード詳細

コンストラクタ__init__()

内部用メソッドget_nbytes()

ハッシュ値計算get_hash()

文字列化メソッド__str()__

簡単なケース

正の数の表現

負の数の表現

引き算と補数の足し算

2の補数を得る方法

典型的なビット数の整数範囲

8ビット

16ビット

32ビット

64ビット

数値から文字列への変換

10進数(str関数)

2進数、8進数、16進数

組み込み関数を使う方法

format関数を使う方法

書式文字列を使う方法

文字列から数値への変換

10進数

整数(int関数)

実数(float関数)

2進数、8進数、16進数

int型

float型

format関数

formatメソッド

書式設定文字列

formatメソッド

文字列

整数

浮動小数点

固定小数点

符号の表示方法

format関数

基数表示

位置揃え

パディング

+符号

カンマ区切り

固定小数点実数

浮動小数点実数

実数全体の桁数

//演算子

%演算子

コンストラクタinit()

文字列化メソッドstr()