先頭ゼロを含まないN桁のB進数の個数を求める方法

本記事では、次のような問題を扱います。整数Nと基数Bが与えられたとき、先頭（最上位桁）が0ではないN桁のB進数が何通りあるかを数えます。例えば、N=2、B=2の場合、2桁の2進数は「00」「01」「10」「11」の4通り存在しますが、このうち先頭が0でない有効な数は「10」と「11」の2つだけです。

考え方

基数がBである場合、使用できる数字は0からB−1までのB種類です。したがって、先頭ゼロを含む場合、N桁の数は全部でB^N通り生成できます。そのうち、先頭の桁が0になるものは、残りのN−1桁だけで決まるためB^N−1通りあります。よって、先頭ゼロを含まないN桁のB進数の総数は、次の式で求められます。

B^N − B^N−1

アルゴリズム

countNDigitNum(N, B)

Begin
   total := BN
   with_zero := BN-1
   return total - with_zero
End

C++による実装例

#include <iostream>
#include <cmath>
using namespace std;

int countNDigitNum(int N, int B) {
   int total = pow(B, N);
   int with_zero = pow(B, N - 1);
   return total - with_zero;
}

int main() {
   int N = 5;
   int B = 8;
   cout << "Number of values: " << countNDigitNum(N, B);
}

実行結果

Number of values: 28672

N=5、B=8の場合、8⁵ = 32768、8⁴ = 4096 となるため、32768 − 4096 = 28672 という結果が得られます。このように、べき乗の差を計算するだけで、先頭ゼロを含まないN桁のB進数の個数を簡単に求められます。