パスカルの三角形をビットシフトで

パスカルの三角形の値を2で割った余りで表示したもの。
別名があったと思うけど、思い出せない.....。

パスカルの三角形

1     1
2    1 1
3   1 2 1
4  1 3 3 1
5 1 4 6 4 1

パスカルの三角形を2で割った余り

1     1
2    1 1
3   1 0 1
4  1 1 1 1
5 1 0 0 0 1

5層目が欲しいなら、4層目をビットシフトしたものと、4層目をXORすると手に入る。

1111 << 1
  -> 11110

1111 xor 11110
  -> 10001

コード

def bit_tri(n):
    bit = 1
    for i in xrange(n-1):
        bit_shift = bit << 1
        bit = bit^bit_shift

    return format(bit, 'b')

print bit_tri(5)