読者です 読者をやめる 読者になる 読者になる

SRM416 Div1Easy NextNumber

問題
与えられた 整数 N(32-signed integer. 1<=N<=1000000000) をビット化したときの 1 の数と同じ 1 の数を持つ値で N より大きい最小の値を求めよ。

解法
ビット化して辞書順で次に現れるビット列を持つ数字が答え。editorial解。

反省
はじめビットの小さい桁から見て 1 と 0 とを一度入れ替える、みたいなことして解こうとしていた。next_permutation() を一回行うという発想が無かった。

#include <bits/stdc++.h>
  
using namespace std;

class NextNumber {
public:
  int getNextNumber(int N) {
    int b[32];
    for(int i=0; i<32; i++)
      b[31-i] = ( N & (1<<i) ) ? 1 : 0;
    
    next_permutation(b, b+32);
    int ans = 0;
    for(int i=0; i<32; i++)
      ans += b[31-i]<<i;
    
    return ans;
  }
};