C++で除算を使わずに2つの数値の平均を高速に求める方法

この記事では、2つの数値 A と B が与えられたとき、除算（割り算）を使わずに平均値を高速に計算するプログラムを C++ で実装する方法を解説します。

問題の例

入力： A = 34、B = 54

出力： 44

解法のアプローチ

通常、2つの数値の平均は「合計を2で割る」ことで求めます。つまり (A + B) / 2 という式になります。しかし、この問題では除算演算子を使用せずに平均を求める必要があります。

そこで活躍するのが右シフト演算子 >> です。数値を1ビット右にシフトすると、2で割った結果と同じ値になります。これは、2進数表現において右シフトが桁を1つ下げる操作に相当するためです。

つまり、(A + B) >> 1 と書くことで、除算を使わずに (A + B) / 2 と同じ結果を得ることができます。シフト演算はCPUレベルで非常に高速に処理されるため、パフォーマンス面でも有利です。

C++での実装例

以下のコードは、右シフト演算子を使って平均を計算する関数の実装例です。

#include <iostream>
using namespace std;

int calcAvgWODiv(int A, int B) {
    // 右シフト演算子で2による除算を代替
    int average = (A + B) >> 1;
    return average;
}

int main() {
    int A = 123, B = 653;
    cout << "2つの数値の平均は " << calcAvgWODiv(A, B);
    return 0;
}

出力結果

2つの数値の平均は 388

コードの解説

calcAvgWODiv 関数では、まず A と B の合計を計算し、その結果に対して >> 1 で1ビット右シフトを行っています。これにより、2で割り算した場合と同一の結果が得られます。

上記の例では、123 + 653 = 776 となり、776 を1ビット右シフトすると 388 が得られます。これは 776 ÷ 2 = 388 と一致しますね。

注意点

この手法にはいくつか注意すべき点があります。負の数を扱う場合、右シフトの挙動は処理系によって異なる場合があります（算術シフトか論理シフトか）。また、A + B の合計が int 型の最大値を超えるとオーバーフローが発生するため、大きな数値を扱う場合は long long などのより大きな型を使用することをおすすめします。