ichirin2501's diary

いっちりーん。

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);
}