ビット演算って

どういった時に使用するのか、よく分からなかったビット演算。MACアドレスが正しいフォーマットか調べる必要があって、ここのコードを参考にしていた時に、こういう使い方があるのかと思ったのでメモ。

def _mac2int(addr, sep=_MACsep):
     # convert a MAC str to an int
    h = addr.split(sep)
    if len(h) > 4:
        i = 0
        for b in h:
            b = int(b, 16)
            if 0 <= b < (1<<8):
                i = (i << 8) | b
            else:
                break
        else:
            if 0 < i < (1<<48):
                return i
    raise ValueError('invalid MAC address: %r' % (addr,))

MACアドレスの文字列を int に変換している関数で、失敗すると ValueError になるようになっています。 その中でビット演算が使用されているのですが、分かりやすくするために'FF:FF'を変換するとした場合、まず左側の'FF'を int に変換します。

>>> int('FF', 16)
255
>>> bin(255)
'0b11111111'  <= 2進数にするとこうなる

次に、最初に変換した部分を 8bit 左にずらして、同様に次の'FF'を int に変換し、ビットOR をとる。

>>> 255 << 8
65280
>>> bin(65280)
'0b1111111100000000'
>>> bin(255)
'0b11111111'
>>> 65280 | 255
65535
>>> bin(65535)
'0b1111111111111111'
>>> bin(0xFFFF)
'0b1111111111111111'

結果、0xFFFF を int に変換したのと同じになります。MACアドレスは ６オクテットなので、これを６回繰り返すとMACアドレスを int に変換できるんですね。勉強になりました。

ヒープソート

C言語のアルゴリズム本を見ながら、Pythonにて書き換えてみる。
ヒープソートはこんな感じ。

def downheap(buff, parent, bottom):
    tmp = buff[parent]

    while True:
        cl = parent * 2 + 1
        cr = cl + 1

        if cl >= bottom:
            break
        if cr < bottom and buff[cl] < buff[cr]:
            cl += 1
        if tmp > buff[cl]:
            break

        buff[parent] = buff[cl]
        parent = cl
    buff[parent] = tmp


def heapsort(buff):
    size = len(buff)
    for i in range(size / 2 - 1, -1, -1):
        downheap(buff, i, size)

    for j in range(size - 1, 0, -1):
        tmp = buff[j]
        buff[j] = buff[0]
        buff[0] = tmp

        downheap(buff, 0, j)

if __name__ == '__main__':
    data = [2, 4, 6, 8, 10, 1, 3, 5, 7, 9]
    heapsort(data)
    print data

書き換えながら、ループを抜ける判定条件に悩む。どうして'A >= B'になるのか理解できなかったけれど（AとBがイコールになることはあるの？）、デバッガの助けを借りて解決。デバッガ便利ですね。

$ pdb heap.py 
> /tmp/heap.py(4)()
-> def downheap(buff, parent, bottom):
(Pdb) b 12, cl == bottom
Breakpoint 1 at /tmp/heap.py:12
(Pdb) r
> /tmp/heap.py(12)downheap()
-> break
(Pdb) p parent, cl, bottom
(3, 7, 7)
(Pdb) c
> /tmp/heap.py(12)downheap()
-> break
(Pdb) p parent, cl, bottom
(0, 1, 1)