C++で数値が3の倍数かどうかを効率的に判定する方法｜ビットカウントを活用した実装

概要

本記事では、与えられた整数が3の倍数であるかどうかを判定するC++プログラムの作成方法を解説します。

一般的な解法とその課題

最もよく知られている方法は、各桁の数字をすべて足し合わせるというものです。桁の合計が3の倍数であれば元の数も3の倍数であり、そうでなければ3の倍数ではありません。この方法は正しく動作しますが、桁ごとの分解と加算が必要なため、必ずしも最も効率的とは言えません。

効率的な解法：2進数のビットカウントを利用する

より効率的なアプローチは、数値の2進表現におけるセットビット（1になっているビット）の数を利用する方法です。

「奇数番目の位置にあるセットビットの数」と「偶数番目の位置にあるセットビットの数」の差が3の倍数であれば、その数は3の倍数である

これは、2のべき乗を3で割った余りが、指数の偶奇に応じて交互に 1 と 2（すなわち +1 と −1）になる性質から導かれます。したがって、各位置のビットに符号を付けて合計すれば、元の数を3で割った余りと一致するのです。

具体的には、ループでビットを2つずつ右シフトしながら、奇数位置と偶数位置それぞれのセットビット数をカウントし、最後にその差が3の倍数かどうかを再帰的に判定して結果を返します。

実行例

入力

n = 24

出力

24 は 3 の倍数です

解説

2進表現 = 11000
奇数位置のセットビット数 = 1、偶数位置のセットビット数 = 1
差 = 0 → 3で割り切れる

C++での実装

上記の考え方を実装したプログラムが以下です。

#include <bits/stdc++.h>
using namespace std;

// n が 3 の倍数なら 1 を、そうでなければ 0 を返す
int isDivisibleBy3(int n) {
    int oddBitCount = 0;   // 奇数位置のセットビット数
    int evenBitCount = 0;  // 偶数位置のセットビット数
    if (n < 0)
        n = -n;            // 負の数は絶対値で判定
    if (n == 0)
        return 1;          // 0 は 3 の倍数
    if (n == 1)
        return 0;          // 1 は 3 の倍数ではない
    while (n) {
        if (n & 1)
            oddBitCount++;   // 最下位ビット（奇数位置）
        if (n & 2)
            evenBitCount++;  // 下から2番目のビット（偶数位置）
        n = n >> 2;          // 2ビットずつ右シフト
    }
    // ビット数の差について再帰的に判定
    return isDivisibleBy3(oddBitCount - evenBitCount);
}

int main() {
    int n = 1241;
    cout << "数値 " << n;
    if (isDivisibleBy3(n))
        cout << " は 3 の倍数です";
    else
        cout << " は 3 の倍数ではありません";
    return 0;
}

出力

数値 1241 は 3 の倍数ではありません

計算量

このアルゴリズムは、1回のループで2ビットずつ処理を進めるため、時間計算量は O(log n) となります。また、再帰呼び出しの引数はビット数の差であるため急速に小さくなり、再帰の深さも非常に浅く抑えられます。桁和を求める従来の方法と比べ、除算や剰余演算を使わずにシフトとビット演算だけで処理できる点が大きな特徴です。

まとめ

3の倍数判定は、2進表現における奇数位置・偶数位置のセットビット数の差を利用することで効率的に実装できます。ビット演算のみで構成されているため、剰余演算のコストが高い組み込みシステムなどの環境でも有用なテクニックと言えるでしょう。