この記事はこんな人にオススメです
- 2の累乗を判別するコードを書きたい人
- その意味をしっかりと理解したい人
- プログラミングが好きな人
こんにちは．
今日は，FFT処理などでよくデータ個数の確認（2の累乗）を行うときによく見かけるプログラムの解説をしておきます．
（コードはPythonですが，Cなどでも良く見かけます）
1 2 3 4 5 6 7 8 | #(2の累乗判定) def judge_pow2(x, x_m): n = len(x) if((n&(n-1))!=0): e_a = np.ceil(np.log2(n)) n_add = int((2**e_a)-n) x = np.hstack((x, np.full(n_add, x_m))) return x |
これですね！
このプログラムで各行がどういう処理をしているか，いかに簡単に書きます．
- 2の累乗判定関数のjudge_pow2にデータxを渡す
- len( )を使って，データ個数を二進数nに変換
- n&(n-1)!=0の時，データ長が2の累乗ではないので，以下の処理をする
- log2(n)を計算した結果に対し，小数点を切り上げ整数にする
- データが足りない（2の累乗に満たない）分を，n_addで，計算する
- 足りないデータ分をhstackによって，元データxに埋め込む. 埋め込みは，あらかじめ計算していたxの平均値x_m
- 埋め込んだら，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の累乗に揃えないといけないので活躍します．
脳波解析などの時系列波形ではよく，時間周波数解析がされるのですが，今回は脳波の電位の周波数解析だけではなく，そ…
