2の累乗判定 n & (n – 1) != 0 の意味を図を使って分かりやすく解説!
この記事はこんな人にオススメです
  • 2の累乗を判別するコードを書きたい人
  • その意味をしっかりと理解したい人
  • プログラミングが好きな人

こんにちは.
今日は,FFT処理などでよくデータ個数の確認(2の累乗)を行うときによく見かけるプログラムの解説をしておきます.
(コードはPythonですが,Cなどでも良く見かけます)

これですね!
このプログラムで各行がどういう処理をしているか,いかに簡単に書きます.

  1. 2の累乗判定関数のjudge_pow2にデータxを渡す
  2. len( )を使って,データ個数を二進数nに変換
  3. n&(n-1)!=0の時,データ長が2の累乗ではないので,以下の処理をする
  4. log2(n)を計算した結果に対し,小数点を切り上げ整数にする
  5. データが足りない(2の累乗に満たない)分を,n_addで,計算する
  6. 足りないデータ分をhstackによって,元データxに埋め込む. 埋め込みは,あらかじめ計算していたxの平均値x_m
  7. 埋め込んだら,xを返す.

ペンのすけ

ちょっと丁寧に書いてみたよ!


さて,ここで疑問が出るのは,3行目の「n&(n-1)!=0の時,データ長が2の累乗ではない」ですよね.
今日は,この累乗判定のコードについて説明していきます.

n&n-1

n&n-1の「&」は2進数表示された各bitに対してAnd演算を行うものです.

And演算とは,検討する二つの値うち,どちらも「真(1)」と「真(1)」の場合に「1」を返します.
つまり,演算する二つの数字が1と1なら,And演算の結果は「1」です.

それ以外の場合,例えば,演算する二つの値が1と0や,0と0と言った場合には「0」を返します.

ペンのすけ

なるほど!そういうことだったのか!

具体的な数字で考えていきましょう!

3つのケースを以下で考えていきます.

  • n=6
  • n=11
  • n=16(2の累乗)

この三つのケースに関してAnd演算を行うとします.

n=6やn=11の場合は,And演算が1になります.
(2進数表記で書いたときに,二つの数のどこかのbitが「1」と「1」の場合があるためです.)

しかし,n=16の場合は,n-1=15とAnd演算をしても,二つの数のどこにも,同じbitの位置で「1」と「1」がありません.
つまり,And演算をすると「0」が返ってきます.

「n&n-1==0」と「n&n-1!=0」の意味

よって,以上のことからわかるように,「n&n-1 == 0」は,2の累乗となります!

一方で「n&n-1 != 0」は,2の累乗以外の数字の場合です.

 

今回のプログラムコードは,Pythonですが他の言語でも理論は全て一緒なので,理解しておくと良いです.

ペンのすけ

プログラミングLife満喫しましょー!

応用先など

高速フーリエ変換(FFT)などを行う場合は,データ数を2の累乗に揃えないといけないので活躍します.