SRM416 DIV2
久しぶりのtopcoder
NextNumber
The binary weight of a positive integer is the number of 1's in its binary representation. For example, the decimal number 1 has a binary weight of 1, and the decimal number 1717 (which is 11010110101 in binary) has a binary weight of 7.
Given a positive integer N, return the smallest integer greater than N that has the same binary weight as N.
Notes
The result is guaranteed to fit in a signed 32-bit integer.
Constraints
N will be between 1 and 1,000,000,000, inclusive.
0)
1717
Returns: 1718
1)
4
Returns: 8
2)
7
Returns: 11
3)
12
Returns: 17
4)
555555
Returns: 555557
同じ1ビットの数の値で、Nより大きい最小の値を求める。
ビット演算で一発で出せそうで出せなかったorz
1ビットが連続で続く判定にループを使ってしまう。
class NextNumber { public: int getNextNumber(int); }; int NextNumber::getNextNumber(int N) { int x=N&-N; int cnt=1; for(int y=x<<1;y&N;y<<=1)cnt<<=1; return (N+x)|(cnt-1); }
N&-Nは値Nの一番右の1ビットを求める演算。
1100のように一番右の1ビットから左へ1ビットが連続してる場合を除き、
一番右の1ビットは0ビットに変わる。
1ビットが連続してない場合は値(N&-N)を足せば良い。
1ビットが連続してる場合は、足して繰り上がった回数だけ右側に1ビットをセットする。
繰り上がる回数は連続してる1ビットの数に等しい。
どうでもいい追記
ループなし(一見)ver書いてみた。
#include <stdio.h> #include <math.h> main() { int N; scanf("%d",&N); int x=N&-N; int y=N|(N-1); int d=log2((~y&-~y)/x)-1; int a=(N+x)|((1<<d)-1); printf("ans:%d\n",a); }