ビットシフトでべき乗表現したら、変な事になった
JavaScriptで大きな数を扱っているときに不可解な現象に悩まされた。
その現象とは、Number型の変数で2の31乗が正しく出力されないというものである。
ビットシフトによる「2の31乗」
for(let bit=0; bit<32; bit++) {
const n_bit = 1<<bit
console.log(`${bit}: n_bit=${n_bit}`)
}
これの出力は以下：
0: n_bit=1
1: n_bit=2
2: n_bit=4
3: n_bit=8
4: n_bit=16
..
30: n_bit=1073741824
31: n_bit=-2147483648 // !?
2の31乗=2147483648であるはずなのに、なぜかそうならず。
ちなみに、Number型で表せられる最大値1は2の53乗-1であるため、まだ優に余裕はあるはずである。
exponentiation operatorによる「2の31乗」
そこで、べき乗の表現方法を変えて再度確認した：
for(let bit=0; bit<32; bit++) {
const n_exp = 2**bit
console.log(`${bit}: n_exp=${n_exp}`)
}
これの出力は以下：
0: n_exp=1
1: n_exp=2
2: n_exp=4
3: n_exp=8
4: n_exp=16
..
30: n_exp=1073741824
31: n_exp=2147483648 // 正しく出力されている
Math.pow()や直接指定による「2の31乗」
また、その他の表現でも確認：
const n_pow = Math.pow(2,31)
console.log(n_pow)// output:2147483648
const n = 2147483648
console.log(n) // output:2147483648
以上より、2の31乗自体は問題なく出力されるため、1<<bitに何か問題がありそうである。
さらに大きな数を確認してみる
シフトする桁数を倍にしてみた。
for(let bit=0; bit<64; bit++) {
const n_bit = 1<<bit
console.log(`${bit}: n_bit=${n_bit}`)
}
出てきたのがこちら：
0: n_bit=1
1: n_bit=2
2: n_bit=4
3: n_bit=8
4: n_bit=16
..
30: n_bit=1073741824
31: n_bit=-2147483648
32: n_bit=1
33: n_bit=2
34: n_bit=4
35: n_bit=8
36: n_bit=16
..
62: n_bit=1073741824
63: n_bit=-2147483648
32ビット以降は、シフトの結果が繰り返しになっていることがわかる。
シフト演算子が32ビットまでしか対応していない感じか？
調査の結果、、
この辺りに記述があった。
シフト演算で対象となるオペランドに32-bit integerな数があると、演算結果も32-bit integerになるというのである。
また、例え計算結果が符号付き32ビットに収まるべきはずであっても、演算対象にそれ以上の数が含まれる場合の演算にも注意が必要である。
すなわち：
// 元の数が signed integer の 32bit 最大値を超えていると、直感に反する結果に..
const n = 2**31
console.log(n) // output: 2147483648
console.log(n >> 2) // output: -536870912, not 536870912
// 32 bit に収めると、意図した結果になる
const n = 2**31-1
console.log(n) // output: 2147483647
console.log(n >> 2) // output: 536870911
bitwise operator
これに類似した例として、「bitwise operatorを介した演算において、そのうちの一つが32-bit integerの場合は、計算結果も32-bit integerとなる」 というものである。
bitwise operatorに関してはこちら。
使い所の一つして、|(ビット論理和)を用いて以下のように少数を含む数の小数以下の切り捨てを行うことができるアレである。
const a_float = 12.345
const a_integer = a_float | 0
console.log(a_integer)// output:12
また、ここで注意したいのが、変換された後のintegerはsignedであるということである。
すなわち、符号付き32-bit integer の最大値を超える数に対してbitwise operatorによる演算を行うと、期待通りの結果は出ない。
const signedIntMax = 2**31-1 // 2147483647
const signedIntMax_plus1 = signedIntMax + 1
console.log(signedIntMax | 0) // output: 2147483647
console.log(signedIntMax_plus1 | 0) // output:-2147483648
// これはOK
console.log(signedIntMax_plus1) // output:2147483648
これは、signedIntMaxに+1することで符号付き32-bit integerの範囲を超えてしまい、その最小値になってしまったためである。
お分かりいただけただろうか？
そもそもビットシフトで1<<32とかやることはそうそうないと思われるが、今回たまたま遭遇したので書かせてもらった。特に、bitwise operatorによる小数切り捨てなどは裏で何が行われているのかを理解した上で使用したいものだ。