【移植#41】「+」なしで整数を足す — ビット演算を境界値まで検証する¶

今回の原典は「演算子を縛る」¶

投稿日順で次に当たる2010年1月30日の記事は、足し算記号の+を使わずに3 + 5を計算するプログラミングパズルでした。

元記事「『+』を使わずに足し算する術。」を読む

原典は、XOR・AND・左シフトを組み合わせた再帰関数で整数を足し、同じ考え方を乗算へ広げています。ただし、最後に出てくるのは「スーパーソレノイド理論」のような大げさな名前を付けた、実体は単純な掛け算という例です。

狙いはビット演算の自慢ではありません。難しそうな関数名や回りくどい処理でロジックを隠されても、見た目だけで価値を判断しないようにしよう、というコードレビューの話です。

今回はパズル部分をMQL5へ移しつつ、原典では扱っていなかった負数、64bit整数、オーバーフロー、独立検証まで追加します。

XORは桁上がりを除いた和になる¶

2進数の1桁だけを見ると、XORは桁上がりを無視した足し算と同じ表になります。

両方が1の位置はa & bで取り出せます。その桁上がりは1つ上の桁へ移るため、左へ1ビットずらします。

carryが0になるまで、この2つを新しいaとbとして繰り返します。配布版の中心は次の反復処理です。

while(right_bits != 0)
{
   const ulong carry_bits = (left_bits & right_bits) << 1;
   left_bits ^= right_bits;
   right_bits = carry_bits;
}

加算を再帰で書くこともできますが、入力によって呼び出し段数が変わります。今回は最大64回で終了することが見える反復式にしました。

3と5はcarryを移しながら8になる¶

3は2進数で0011、5は0101です。

最後にcarryが0となり、結果は8です。途中の値だけを見ると遠回りですが、CPUの加算器を考える入口としては面白い題材です。

MQL5公式リファレンスのBitwise Operationsでも、XOR、AND、OR、左右シフトは整数型へ適用する演算として定義されています。型幅以上のシフトは未定義になるため、配布版が一度に動かすのは常に1ビットだけです。

負数は64bitのビット列として扱う¶

配布版の入力型はlongです。MQL5公式リファレンスのInteger Typesによると、longは符号付き64bit、ulongは符号なし64bitです。

加算中は入力をulongへ変換し、64個のビット列としてXOR・AND・シフトを行います。最後にlongへ戻すことで、-2と-15も-17になります。

ただし、64bitの箱に入らない答えまで正しくなるわけではありません。配布版は計算前に次の範囲を検査し、はみ出す入力を拒否します。

• long最大値と1の加算
• long最小値と-1の加算
• long最大値と2の乗算
• long最小値と-1の乗算

ビット演算は、オーバーフローを魔法のように解消する方法ではありません。範囲外を黙って折り返すより、計算しないことを明示する方が安全です。

乗算はシフト加算法で組み立てる¶

乗数の下位ビットが1なら被乗数を結果へ加え、被乗数を左へ、乗数を右へ1ビットずつ動かします。

while(multiplier != 0)
{
   if((multiplier & 1) != 0)
      product_bits = AddUnsignedBits(product_bits, multiplicand, ignored_iterations);
   multiplicand <<= 1;
   multiplier >>= 1;
}

負数は絶対値に相当するビット列へ直してから計算し、符号が片方だけ負なら最後に2の補数へ戻します。乗算前には除算による範囲検査を行い、安全なlongへ収まる場合だけ処理します。

この方法は整数の仕組みを学ぶには役立ちますが、通常のEAやインジケーターでa * bの代わりに採用する理由にはなりません。標準演算子の方が短く、意図が伝わり、コンパイラの最適化も期待できます。

20ケースと4つの拒否を独立照合する¶

配布インジケーターは、入力値-2と-15についてビット演算版と通常演算版を比較します。さらに、符号と値幅を変えた加算10ケース、乗算10ケースを実行します。

診断用の12バッファは次の内容です。

1. 全体合格フラグ
2. ビット演算版の加算結果
3. 通常演算版の加算結果
4. ビット演算版の乗算結果
5. 通常演算版の乗算結果
6. 加算合格数
7. 乗算合格数
8. オーバーフロー拒否合格数
9. 加算の最大carry周回数
10. 入力値の乗算ステップ数
11. ターミナルのビルド番号
12. パネル用オブジェクト数

検証EAは12本をCopyBuffer()で1件ずつ読み、配布側とは別に期待値を照合しました。

ダウンロードと使い方¶

41_Bitwise_Integer_Arithmetic_Lab_v1_00.mq5 をダウンロード

MT5のIndicatorsへ保存してコンパイルし、任意のチャートへ適用してください。初期値は左が-2、右が-15です。

パネルには加算・乗算のビット演算版と通常版、20ケースの合格数、オーバーフロー拒否、carry周回数を表示します。入力がlongの範囲外となる計算では、結果を表示せず検証失敗として扱います。

使えないこと・注意点¶

• 浮動小数点数には対応しません。整数専用です。
• longの範囲外になる加算・乗算は拒否します。
• 標準の+や*より速いことを示すベンチマークではありません。
• 暗号、ハッシュ、セキュリティ用途の実装ではありません。
• ビット演算で難読化しても、ロジックや知的財産を安全に保護できるわけではありません。
• 読みにくいコードを「高度」と判断せず、入力、出力、境界値を独立に確認してください。
• 売買ロジックはなく、取引成績を評価するものではありません。

ロジック評価の結論¶

+を使わない足し算は、XORが桁上がりを除いた和、ANDと左シフトがcarryになることを目で追える教材です。負数と64bit境界まで広げると、単なるパズルから型とオーバーフローの実験になります。

ただし、実務で同じ計算をわざと複雑に書く理由はほとんどありません。コードが長く、名前が大げさで、処理が追いにくいほど価値が高いわけではないからです。

原典の一番大事な部分は、ビット演算の技ではなく「変なコードを書くプログラマーには用心しよう」という締めでした。現代なら、さらに一歩進めて、説明よりテスト、名前より入出力、雰囲気より境界値を確認するのがよさそうです。

前後の記事¶

前: 【移植#40】日本語変数名は今も使える？ — MQL5の仕様境界を実機で確かめる