C++で2進表現がすべて1になる数の個数をカウントする方法

正の整数 N が与えられたとき、N 以下の整数のうち、2進表現がすべて「1」で構成されている数の個数を求めるのが本記事の目的です。

たとえば、1 は「1」、3 は「11」、7 は「111」、15 は「1111」といった具合に、これらの数はすべて 2ⁱ − 1 の形で表されます（i は 1 から始まります）。したがって、N 以下に該当する数を調べるには、「2ⁱ − 1 ≤ N」が成り立つかどうかを順番に判定し、条件を満たすたびにカウントを増やしていけばよいのです。

入出力例

入力：N = 15
出力：2進表現がすべて1の数 : 4
説明：該当する数は 1, 3, 7, 15 の4つです。

入力：N = 50
出力：2進表現がすべて1の数 : 5
説明：該当する数は 1, 3, 7, 15, 31 の5つです。

プログラムで使用しているアプローチ

• 正の整数 N を入力として受け取ります。
• 関数 allOnes(int n) は n を引数にとり、2進表現がすべて1となる数の個数を返します。
• カウント用の変数 count を 0 で初期化します。
• for ループを使って i = 1 から i ≤ n まで繰り返します。
• 各 i について、pow(2, i) − 1 が n 以下であれば count をインクリメントします。
• ループ終了後、count を結果として返します。

コード例

#include <bits/stdc++.h>
using namespace std;
int allOnes(int n){
    int count = 0;
    for(int i=1;i<=n;i++){
        if(n>=pow(2,i)-1){
            count++;
            //cout<<" "<<pow(2,i)-1;
        }
    }
    return count;
}
int main(){
    int N=23;
    cout <<endl<< "Number having all 1's in binary : "<<allOnes(N);
    return 0;
}

出力結果

上記のコードを実行すると、次のような出力が得られます。

Number having all 1's in binary : 4

補足：より効率的な実装のポイント

pow() 関数は浮動小数点演算を行うため、大きな数を扱う際に誤差が発生する可能性があります。代わりにビットシフト演算子を使えば、整数演算だけで正確かつ高速に判定できます。具体的には、pow(2, i) − 1 の部分を ((1LL << i) - 1) に置き換えることで、オーバーフローにも配慮しながら安全に計算できます。また、N の上限が分かっている場合は、ループ回数を log₂(N) 程度に抑えることで計算量をさらに削減できます。