『Cプログラミングの落とし穴』(A.コーニグ, 1990)
[M1 Mac, Big Sur 11.6.8, clang 13.0.0, NO IDE]
本を読んでいるとシフト演算のことが思い浮かんだので寄り道します。
シフト演算が掛け算を工数の少ない足し算に変換できるため早く計算できるというのは一応理解できますが、どういった足し算が最良なのかを見出す工数が勘定されていません。
例えば10倍の場合は、2^3 = 8と2^1= 2なので8倍と2倍の和になります。これが10000倍だったら2のベキ乗数の組み合わせがどうなるのかすぐには分かりません(後述していますが組み合わせは簡単に分かります)。
とりあえず50倍にする場合の2のベキ乗数の組み合わせをC++のプログラムで算出してみました。
int main()
{
int x = 50;
int x2, x3;
int i2;
bool finished = false;
int i = 0;
vector<int> pow_list;
while(1){
int num1 = std::pow(2, i);
cout << "num1 " << num1 << endl;
if (num1 > x){
pow_list.push_back(i-1);
x2 = x - pow(2,i-1);
cout << "x2 " << x2 << endl;
while(1){
int num2 = std::pow(2, i2);
cout << "num2 " << num2 << endl;
if (num2 > x2){
pow_list.push_back(i2-1);
x3 = x2 - pow(2,i2-1);
cout << "x3 " << x3 << endl;
finished = true;
break;
} else {
i2 += 1;
}
}
} else {
i += 1;
}
if (finished) {
break;
}
}
cout << "i " << i << endl;
cout << "i2 " << i2 << endl;
}
--------------------------------------------------
出力
--------------------------------------------------
num1 1
num1 2
num1 4
num1 8
num1 16
num1 32
num1 64
x2 18
num2 1
num2 2
num2 4
num2 8
num2 16
num2 32
x3 2 // 50から2^5と2^4を引いた残り
i 6 // 2^6は64なので50から最初に引く数字は2^5=32
i2 5 // 次に50-32=18から2^4=16を引く
// したがって50の内訳は2^5+2^4+2^1プログラムにより50 = 2^5 + 2^4 + 2^1であることが分かります。
さらに大きい数字の場合はどうやって算出するのでしょうか。
ここまで書いて、50の2進数が110010だから一目瞭然だということに気が付きました。大きな数字であっても2進数を見れば分かります。もっと早く気付くべきでした。
今度は2進数への変換が演算としてどうなっているのか気になってきました。