같은 갯수의 0과 1을 가지는 바로 더 크고 작은 수를 구하자.

10010

>> 다음 숫자 : 10100

     앞 숫자 : 10001

풀이 : 오른쪽에 1이 있는 첫 0과 그 1을 스왑하면 (반대로 얘기하면 바로 옆이 비어있는 첫 1) 다음 숫자이다.

***

오른쪽이 비어있는 첫 1을 그 오른쪽으로 밀면 바로 작은값

왼쪽이 비어있는 첫 1을 그 왼쪽으로 밀면 바로 큰값

01 >> 큰값

10 >> 작은값

pair<int,int> (int n){

// base cases

if(n==0) return pair<int,int>(0,1);

if(n==-1) return pair<int,int>(-2,0);

int m = 1;

int bigger = 0;

int smaller = 0;

int preflag = m&n;

m = m<<1;

for(int i = 1 ; i < 32 ; i++){

if(preflag!=0&&n&m==0){

// bigger found

bigger = n^(m^(m>>1));

}

if(preflag==0&&n&m!=0){

// smaller found

smaller = n^(m^(m>>1));

}

if(smaller!=0&&bigger!=0) break;

}

return pair<int,int>(smaller,bigger);

}

음수

1101 : -3

1110 : -2(큰값)

1011 : -5(작은값) 

성립한다 !!!

완벽한 알고리즘 ..

time complexity O(logN)