SRM 416 DIV1 Easy - NextNumber (復習○)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=8576&rd=13507

・整数Nが与えられる。
・整数Nを2進数にしたときの1の数が同じで、かつNより大きい最小の数を求める。

解き方


法則が少し複雑。
サンプルを見てみると、以下のことがわかる。
①右から走査し、最初に1が存在したらそこから次に0が出る箇所が1になる。
②1にした箇所より右を、それまで残っている1の分だけ右から詰める。

ビット列走査により以下のように求められる。

最初に1が存在する箇所:N & -N(=x)
0から1にする箇所  :~(N+x=y)&N(=z)

1にした箇所から左部分:y(=N+x)
1にした箇所より右部分:z/x>>1

コード


class NextNumber {

public: int getNextNumber(int N) {
int x=N&(-N);
int y=N+x;
int z=N&(~y);

return y|(z/x>>1);
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class NextNumber {

public: int getNextNumber(int N) {
int pos=0;
while( (N&(1<<pos))==0)pos++;
N-=(1<<pos);

int cnt=0;
while(N&(1<<(pos+1))){
pos++;
cnt++;
N-=(1<<pos);
}

N+=(1<<(pos+1));
FORE(i,0,cnt)N+=(1<<i);
return N;
}

};
このエントリーをはてなブックマークに追加