2のべき乗をもとめるメソッドの挙動を追ってみよう
次のメソッドIsPowerOfTwoは2のべき乗を求めるためのメソッドなのですが、処理をすぐに頭で終えるでしょうか？
bool IsPowerOfTwo(int num)
{
return (num & (num - 1)) == 0;
}
&は、bitごとのAnd演算を行う演算子です。32bitの2の補数表現で表した二進数で上記の処理を考えてみましょう。
numが1のとき、
-
00000000000000000000000000000001<- 1 の4bitの2の補数表現 -
00000000000000000000000000000000<- 1 - 1 = 0 の32bitの2の補数表現 - 上記二つをビット演算でAndすると結果は
0 - 結果、IsPowerOfTwoは
trueとなる
numが4のとき、
-
00000000000000000000000000000100<- 4 の4bitの2の補数表現 -
00000000000000000000000000000011<- 4 - 1 = 3 の32bitの2の補数表現 - 上記二つをビット演算でAndすると結果は
0 - 結果、IsPowerOfTwoは
trueとなる
numが32のとき、
-
00000000000000000000000000100000<- 32 の4bitの2の補数表現 -
00000000000000000000000000011111<- 32 - 1 = 31 の32bitの2の補数表現 - 上記二つをビット演算でAndすると結果は
0 - 結果、IsPowerOfTwoは
trueとなる
numが31のとき、
-
00000000000000000000000000011111<- 31 の4bitの2の補数表現 -
00000000000000000000000000011110<- 31 - 1 = 30 の32bitの2の補数表現 - 上記二つをビット演算でAndすると結果は
1 - 結果、IsPowerOfTwoは
falseとなる
処理を追うことができたでしょうか？
このようにbitごとのAnd演算を活用して、IsPowerOfTwoメソッドはint型の数値が2のべき乗かどうか調べています。
さて、残念ながらIsPowerOfTwoでは、落とし穴があります。気づきましたか？
正しくないIsPowerOfTwo
IsPowerOfTwoの落とし穴は、2のべき乗でない0とint.MinValueでもtrueを返してしまうということです。
0は2のべき乗ではありませんね。
32bitの2の補数表現で、numが0の時を考えてみましょう。
numが0のとき、
-
00000000000000000000000000000000<- 0 の4bitの2の補数表現 -
11111111111111111111111111111111<- 0 - 1 = -1 の32bitの2の補数表現 - 上記二つをビット演算でAndすると結果は
0 - 結果、IsPowerOfTwoは
trueとなる
このように0は2のべき乗でないのに、trueを返してしまいます。
同様に、numがint.MinValue(=-2,147,483,648)のときを示します。
-
10000000000000000000000000000000<- int.MinValue(=-2,147,483,648) の4bitの2の補数表現 -
01111111111111111111111111111111<- オーバーフローが起きる、int.MinValue(=-2,147,483,648) - 1 = int.MaxValue(=2,147, 483,647) の32bitの2の補数表現 - 上記二つをビット演算でAndすると結果は
0 - 結果、IsPowerOfTwoは
trueとなる
このように2のべき乗を求める計算のつもりだった、次のコードは
bool IsPowerOfTwo(int num)
{
return (num & (num - 1)) == 0;
}
0とint.MinValueでtrueを返すので、正しいメソッドではありません。
正しくは、次のようにする必要があります。
bool IsPowerOfTwo(int num)
{
if(num <= 0) {
return false;
} else {
return (num & (num - 1)) == 0;
}
}
Unityでのバグ
Unityには、Mathf.IsPowerOfTwoという引数にとったintが2のべき乗かどうか調べるメソッドがあります。
残念ながらこのメソッドは、2のべき乗でない0とint.MinValueでもtrueを返してしまいます。
このMathf.IsPowerOfTwoメソッドは外部で実装されていて、IL Viewerでその実装を確認することはできないのですが、本投稿で示した次のような実装がされている可能性があります。
そのため、このような正しくなっていない挙動となっている可能性があります。
bool IsPowerOfTwo(int num)
{
return (num & (num - 1)) == 0;
}
IsPowerOfTwoメソッドを使う機会があり、0を引数に渡すことがある場合は、特に注意が必要ですね。