ビット数えるアルゴリズム + AOJ 0030

ビットを数える・探すアルゴリズム

このようなサイトを見つけた。ビットの立ってる数をループも無しで求める方法があるらしく軽く衝撃を受けた。

検証しようと思ったけど、

ビットを数えるアルゴリズム: ふらふら日記にて既に書かれていたので参考にさせてもらった。巧妙すぎる。

まあこれを使ってみようと思って解いた問題がこれ。

404 Not Found

いつものようにビットで組み合わせ。

#include <iostream>
using namespace std;

int numofbits5(long bits) {
  bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
  bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
  bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
  bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
  return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int main(){
	int n,s,ret,sum;
	while(cin >> n >> s && n || s){
		ret = 0;
		for(int i=0;i < (1<<10);i++){
			sum = 0;
			if(numofbits5(i) != n)continue;
			for(int j=0;j<10;j++){
				if( (1<<j) & i )sum += j;
			}
			if(sum == s)ret++;
		}
		cout << ret << endl;
	}
}

まあ二進数の本数カウントなんて普通にリニアサーチしてもたかが知れてるんだけど。

ちなみに、ここで紹介してる関数の処理内容だと32bitまでしかカウントできないはず。