7
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

intが2のべき乗か求める方法。そしてUnityのバグ

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のべき乗でない0int.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;
}

0int.MinValuetrueを返すので、正しいメソッドではありません。

正しくは、次のようにする必要があります。

bool IsPowerOfTwo(int num)
{
    if(num <= 0) {
        return false;
    } else {
        return (num & (num - 1)) == 0;
    }
}

Unityでのバグ

Unityには、Mathf.IsPowerOfTwoという引数にとったintが2のべき乗かどうか調べるメソッドがあります。

残念ながらこのメソッドは、2のべき乗でない0int.MinValueでもtrueを返してしまいます。
このMathf.IsPowerOfTwoメソッドは外部で実装されていて、IL Viewerでその実装を確認することはできないのですが、本投稿で示した次のような実装がされている可能性があります。
そのため、このような正しくなっていない挙動となっている可能性があります。

bool IsPowerOfTwo(int num)
{
    return (num & (num - 1)) == 0;
}

IsPowerOfTwoメソッドを使う機会があり、0を引数に渡すことがある場合は、特に注意が必要ですね。

参考

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
7
Help us understand the problem. What are the problem?