このようなサイトを見つけた。ビットの立ってる数をループも無しで求める方法があるらしく軽く衝撃を受けた。
検証しようと思ったけど、
ビットを数えるアルゴリズム: ふらふら日記にて既に書かれていたので参考にさせてもらった。巧妙すぎる。
まあこれを使ってみようと思って解いた問題がこれ。
いつものようにビットで組み合わせ。
#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までしかカウントできないはず。