CodeIQ：2進化10進数の1の数

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「2進化10進数の1の数」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
コンピュータにおける数値の表現方式の一つに2進化10進数(BCD)があります。
これは、10進数の各桁をそのまま2進数に置き換えたものです。

例えば、42の場合、十の位の「4」を2進数で表して「0100」、一の位の「2」を2進数で表して「0010」なので、「0100 0010」となります。
（ここでは符号は考えないものとします。）

Nが与えられる時、N桁の整数を「2進数で表した時」と「2進化10進数で表した時」に、ビット列に含まれる「1」の数が等しいものがいくつあるかを求めてください。

例)
42は2進数では「101010」で3個、2進化10進数では「0100 0010」で2個なので対象外、
52は2進数では「110100」で3個、2進化10進数では「0101 0010」で3個なので対象です。

【入出力サンプル】
Input
2

Output
20

私のプログラム

C言語で解答しています。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

const int BIN_BITS[] = {
	0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
	4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

const int BCD_BITS[] = {0,1,1,2,1,2,2,3,1,2};

int bin_bits(int n)
{
	int ret  = 0;

	for (int i=0 ; i<sizeof(n) ; i++ ) {
		ret += BIN_BITS[((unsigned char*)&n)[i]];
	}

	return ret;
}

int bcd_bits(int n){
	int ret = 0;

	while(n > 0){
		int m = n % 10;
		n /= 10;
		ret += BCD_BITS[m];
	}

	return ret;
}

int solve(int n){
	int st = (n == 1 ? 0 : pow(10, n-1));
	int ed = pow(10, n) - 1;
	int ret = 0;
	int i = 0;

	for(i=st; i<=ed; i++){
		if(bin_bits(i) == bcd_bits(i)){ ret += 1; }
	}

	return ret;
}

int main(void){
	char line[128] = {0};
	int n = 0;

	while( fgets(line, sizeof(line), stdin) != NULL ){
		sscanf(line, "%d", &n);
		int ret = solve(n);
		printf("%d\n", ret);
	}
}

解説

単純に総当たりです。
Rubyだと微妙に時間が足りなかったのでC言語です。

考え方

指定された桁数の数全てに対して普通の数値表現の場合と二進化十進の場合で同じ数1が含まれるかを調べています。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(n)

stは最初の数で10n-1、1桁の時だけは0からです。
edは10n-1です。
retは題意を満たす数の数（＝答え）です。
iはループカウンタです。

st〜edまでそれぞれの表現で1になるビット数が同じものを調べ、同じならretを加算します。

int bin_bits(int n)

普通の数値表現の1のビット数を求めます。
8ビットずつシフトしながら、8ビットの数（0〜255）に含まれるビットの数を求めます。
BIN_BITS[]は8ビットの数に含まれる1のビット数の表です。

bcd_bits(int n)

10進数で1桁ずつ、各桁に含まれる1のビット数を求めます。
BCD_BITS[]は0〜9に含まれる1のビット数の表です。

雑感

総当たりよりもうまい方法ってあるんでしょうね、多分。
ちなみに、ビット数を数える方法にはビット演算を使った有名な方法がありますが、表引きの方が速いので表引きを採用しました。