SRM 711 : ConsecutiveOnes

問題概要：
整数nとkが与えられる
次の条件を満たすような最小の整数mを求めよ：
1. m は n 以上である
2. m を２進数表記にしたとき、1が少なくともk個連続する箇所が存在する

制約 :
1 <= n <= 2^50 - 1
1 <= k <= 50

解法：
mの中で1がk個連続する箇所をループで決める
このとき、mがn以上ならそれを答えの候補にする
そうでないとき、mがn以上でなおかつそのような値の中で最小になるように調整し答えの候補に追加する
答えの候補の中の最小値を答えとして返す

mがn未満の場合にn以上でなおかつ最小になるように調整する 手順は次の通り
m = 0..01..10..0
1. n - mを求める
これをxとする
2. xとmの論理積 x & m が 0 なら、

m = x | m 

として調整終了
そうでないなら、

m = ( m | x ) & ~((1LL<<sp)-1LL)
m += (1LL<<(sp+k))

とする
このとき、
m = 0..01..10..0
の赤くなっている1の位置がsp

注意点：
オーバーフローしないように、ビットをシフトする際には

1<<k 

ではなく

1LL<<k

とすること

コード：

typedef long long ll;
class ConsecutiveOnes {
public:
  ll compute(int sp,ll n,int k) {
    ll v = 0LL;
    rep(i,k) v |= (1LL<<(sp+i));
    if( v >= n ) return v;
    ll need = n - v;
    if( ( v & need ) == 0LL ) {
      return v | need;
    }
    v = ( v | need ) & ~((1LL<<sp)-1LL);
    v += (1LL<<(sp+k));
    return v;
  }
  
  long long get(long long n, int k) {
    ll mini = LLONG_MAX;
    rep(i,100) {
      if( i + k >= 62 ) break;
      mini = min(mini,compute(i,n,k));
    }
    return mini;
  }
};