本当は怖いHPC

HPC屋の趣味&実益ブログ

ある整数が2のべき乗数であるかどうかを求めるには、!(n & (n-1))でよい

小ネタ。

ある整数が2のべき乗数であるかどうかの判定は、 !(n & (n-1)) で行けるらしい。しかも割合有名らしい。知らなかった。

なぜそうなるのか一瞬考えてしまったので、恥さらし。

(証明)
(i) 整数nが2のべき乗数の場合
nを2進数で表すと 1000...00 となり、最上位ビットのみが1であるので、n-1 は、 111...111 となる。よって、両者のビット論理積をとれば、必ず0になる。

 1000...00
  111...11
                    • -
0000...00

(ii) 整数nが2のべき乗数でない場合
nを2進数で表すと、最上位ビット以外に1であるビットが少なくとも1つ存在する。
よって、n-1 でも、最上位ビットは必ず残るから、nとn-1のビット論理積は必ず1以上。
(正確には、nを超えない最大の2のべき乗数以上、n未満)

以上より、!(n & (n-1)) の演算は、nが2のべき乗数であるかどうかの真偽値(1/0)をあらわす。

(証明オワタ)

【広告】