私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「２進数で左右反転しても同じ？」（CodeIQ）を参照してください。
問題を引用します。
例えば、10進数の「20」が与えられた時、まずはこれを2進数に変換します。
すると、「10100」が得られます。さらに、これを左右反転すると、「00101」が得られます。
これを10進数に戻すと、「5」になります。
標準入力から2つの数字が10進数で与えられた時、この2つの数字に挟まれる数について、上記の処理を行ってください。
このとき、処理前後の値が同じになるものの数を数え、その個数を出力してください。
（標準入力で与えられた2つの数は含まないものとします。）
C言語で解答しています。
#include <stdio.h>
// 1が立っているビットの数を返す
int count64bit(unsigned long long v) {
unsigned long long count = (v & 0x5555555555555555) + ((v >> 1) & 0x5555555555555555);
count = (count & 0x3333333333333333) + ((count >> 2) & 0x3333333333333333);
count = (count & 0x0f0f0f0f0f0f0f0f) + ((count >> 4) & 0x0f0f0f0f0f0f0f0f);
count = (count & 0x00ff00ff00ff00ff) + ((count >> 8) & 0x00ff00ff00ff00ff);
count = (count & 0x0000ffff0000ffff) + ((count >> 16) & 0x0000ffff0000ffff);
return (int)((count & 0x00000000ffffffff) + ((count >> 32) & 0x00000000ffffffff));
}
// 1が立っている先頭ビット位置を返す
int MSB64bit(unsigned long long v) {
if (v == 0) return -1;
v |= (v >> 1);
v |= (v >> 2);
v |= (v >> 4);
v |= (v >> 8);
v |= (v >> 16);
v |= (v >> 32);
return count64bit(v) - 1;
}
// デバッグ用出力
void printb(unsigned long long val){
int i=0;
unsigned long long MASK = 0x8000000000000000;
for(i=0; i<64; i++){
unsigned long long lb = (val << i) & MASK;
if(MASK == lb){
putc('1', stdout);
}
else{
putc('0', stdout);
}
}
putc('\n', stdout);
return ;
}
// ビットを反転する
unsigned long long reverseBit(unsigned long long v){
unsigned long long r = 0;
int i=0;
for(i=0; i<=MSB64bit(v); i++){
r = r << 1; // 1ビット左にシフト
r |= (v >> i) & 0x01; // 最下位ビットを付け加える
}
return r;
}
int main(int argc, char* argv[]){
char str[1024] = {0};
while( fgets(str, sizeof(str), stdin) != NULL ){
long long st = 0; // 開始
long long ed = 0; // 終了
int unsigned long long i=0;
unsigned long count = 0;
sscanf(str, "%lld,%lld", &st, &ed);
for(i=st+1; i<ed; i++){
if(i == reverseBit(i)){
count += 1;
}
}
printf("%lu", count);
}
return 0;
}
この問題は素直に範囲内の値に関してすべての値をチェックして数を数えています。
私はこの問題を解く方法として2通りの方法を検討しました。
一つは実際のプログラムでやっているようにすべての値に対してビットを左右反転して比較する方法。もう一つは2進数表記で左右対象になる値だけを順次作り出して範囲内に収まる値を数えるという方法です。
おそらく後者の方が高速ですが当時はうまいやり方を思いつけなかったので単純な前者の手法をとりました（今は鍛えられたので後者の方法でもできます）。
ビットの左右反転は結構難しいのです。例えば13は2進数で10011ですが、これを左右反転すると11001にしなければなりません。入力値の上限がわからないのでとりあえず64bit整数を使いますが、何も考えずに64bitの整数で左右反転すると1100100000000000000000000000000000000000000000000000000000000000になってしまい比較できません。比較できるように右側が0の間右シフトすれば良いように思えますが12のように偶数の場合は左右反転すると再会ビットが0になるので単純にはいきません。その上非常に効率が悪いのです。
そこで、チェック対象のビット長を知る必要があります。13なら5ビットであることがわかればその範囲内で反転すれば良いので直接比較できる形に反転できる上、効率も高くなります。
元の値のビット長はその値のビットのうち1が立っている最上位ビットの位置と同じことなのでそれをMSB64bit()で調べています。
この関数とその中で使っているcount64bit()は自分で考えた関数では無く、調べて発見したものを使っています。ロジックもよくわかっていないので説明できません(^^;;。
あとは範囲内の値について順次ビットを左右反転した値と比較し、一致した数を数えるだけです。
この問題はビット操作ができるかどうかに主眼があったようであまり広い範囲がテストパターンになかったのでこのプログラムでもパスしました。1から64bit整数の最大値までとかのテストパターンがあったら時間切は確実だったと思います。
この場合は私が選択しなかった方法をとる必要がありますが、こちらのアリゴリズムは組み合わせ列挙になるので課題であるビット操作から外れるということでしょう。ちなみに、こちらの方法はビット長の短い値からメモを使って作って行くとできます。