数が2の累乗かどうか調べる方法

アラインメントサイズ指定してメモリを確保する関数の処理を書く機会があった。 引数として渡されるアラインメントサイズとして、2ⁿ しか渡ってこない前提のコードになっていたので なんらかのアサーションくらいは入れてみたい。

ということで、軽く調べてみたメモ。

"power of 2 bitwise" などでググれば出てくる。

ここに10通りの方法が出ている。→ Ten Ways to Check if an Integer Is a Power Of Two in C - Exploring Binary

ほとんどは数合わせのしょうもないものなのでスルーするとして、 "9. Decrement and Compare" がシンプルで良さそう。 glibc の malloc.c でも使っているらしい。

コードはこんな感じ

int isPowerOfTwo (unsigned int x)
{
  return ((x != 0) && !(x & (x - 1)));
}

肝は 'x & (x - 1)' の部分だが、x が 0 の場合に累乗判定しないように前半部分がある。

今回の場合はアラインメントサイズが 0 というのはそもそもおかしいので別アサートにして以下のような感じにした。

assert(alignmentSize!=0);
assert((alignmentSize&(alignmentSize-1))==0); // check power of 2

---

ちなみに、上記記事の "10. Complement and Compare" はこんな感じ。

int isPowerOfTwo (unsigned int x)
{
  return ((x != 0) && ((x & (~x + 1)) == x));
}

9番の方法よりほんの少し速かったようだが、 シンプルさでは劣るように感じたのでこちらは採用せず。