Python
numpy

Numpy boolean & Python integer with 1<<62

Finding very unique setup in Python motivates me to write in Qiita.
非常に独特なPythonの仕様を見つけたので、初めてQiitaに投稿します。

  • Note this article is open under Creative Commons BY: Akito D. Kawamura (@aDAVISk)
    注:この投稿はAkito D. Kawamura (@aDAVISk) の名前で、クリエイティブコモンズBYで公開しています。

Problem 問題

The critical code (Python 3.6) is the following:
これが問題のコード(Python 3.6)です:

bitshiftMagic.py
import numpy as np
cc = np.array([True])
vv = 1 << 62
for ii in range(3):
    vv = vv << 1 | cc[0]
    print(bin(vv))

then I get the error message as
すると以下のようなエラーメッセージ出てきます。

Output1
0b1000000000000000000000000000000000000000000000000000000000000001
Traceback (most recent call last):
 File "bitshiftMagic.py", line 5 in <module>
   vv = vv << 1 | cc[0]
TypeError: ufunc 'left_shift' not supported for the input types, and the inputs could not be safely coerced to any supported types according to the casting rule ''safe''

Note the first line is a correct. It fails at the second time in the for loop.
注: 1行目は正しい出力です。forループの2度目の実行でこけてます。

Some trials いくつかの試行

If I set cc = [True] instead of line 1 then everything is fine.
1行目をcc = [True]とすると何ら問題なく動きます。

Output2
0b1000000000000000000000000000000000000000000000000000000000000001
0b10000000000000000000000000000000000000000000000000000000000000011
0b100000000000000000000000000000000000000000000000000000000000000111

If I set vv = 1 << 61 at line 3 then bit overflow is happening.
3行目をvv = 1 << 61とすると、ビットがオーバーフローします。

Output3
0b100000000000000000000000000000000000000000000000000000000000001
-0b111111111111111111111111111111111111111111111111111111111111101
0b111

The problem can be solved with vv = 1 << 63 at line 3.
この問題は、3行目をvv = 1 << 63とすれば回避できます。

Output4
0b10000000000000000000000000000000000000000000000000000000000000001
0b100000000000000000000000000000000000000000000000000000000000000011
0b1000000000000000000000000000000000000000000000000000000000000000111

Solution 解決策

Here I give a sample code to store arbitrary length of random numpy boolean array into a stream of bits or an integer.
以下に任意の長さのランダムなブーリアンの配列をビットストリーム(整数型)に格納するサンプルコードをのせておきます。

bitshiftMagic2.py
import numpy as np
nn = 3 # try with a different number e.g. 70
arr = np.random.rand(nn) >= 0.5
vv = 1 << 63
for cc in arr:
    vv = vv << 1 | cc
vv = vv & 2**nn-1
print(bin(vv))

Personal view 個人的見解

I think this problem is related to the type setting of Python, but I also confused in some detail. vv is set to 'int' at line 3 of bitshiftMagic.py with the highest number bit (for 2^62) 1, then left-shifted. Thus, the set bit is going to the sign bit, but it still gives a large positive number back (I'm confused here). The error is triggered at the second left-shift; I understand this time the bit is overflowed. But how about the other cases?

In case of vv = 1 << 61, vv is definitely a 64bit integer, and a bit-overflow is observed and then gives a small positive number. This is a textbook example of bit-overflow.

In case of vv = 1 << 63, vv is an integer of unlimited length. Hence, I can make numberless left-shift until RAM eaten up.

Overall, the key is the magic number 62, where the integer is at a tip to overflow and will be left-shifted. Watch out at this border!

この問題の根幹はPythonの型設定にあるような気がしてますが、一部まだ理解できていない部分があります。bitshiftMagic.pyの3行目でvvは'int'で、その最も大きなビット(2の62乗のビット)に1が入ってます。そしてleft-shiftしますが、この時まだ大きな正の整数を返してきます(ここの理由がわからない)。2度目のleft-shiftでエラーが返りますが、これはbitがオーバーフローするのでまあ解ります。その他のケースも見てみます

vv = 1 << 61とした場合は、vvは明らかに64ビットの整数型です。ビットがオーバーフローして、そして小さな正の整数を返します。教科書通りのビットのオーバーフローです。

vv = 1 << 63とした場合は、vvは無限長の整数型になってます。よって、RAMを食い尽くすまでleft-shiftが出来ます。

まとめると、全ての問題は62というマジックナンバーにあるようです。整数型があふれんばかりになっていて、それをleft-shiftすると壊れると。この境界で作業される際にはご注意を!

See more もっと詳しく

Please check my BitGraphics library at Git.
Gitの私のBitGraphicsライブラリーを参考にしてください。
https://github.com/aDAVISk/PythonForSpaceWeather/tree/master/BitGraphics