비밀번호 @kancho

문제

#include< iostream >
using namespace std;
/*
	2016-06-01
	옥상, 비밀번호:: 시간초과
*/
int binari(int n, int check)
{
	int cnt = 0;
	while (n)
	{
		if (check != 0 && check < cnt) return -404;
		if (n & 1 == 1) cnt++;
		n = n >> 1;
	}
	return cnt;
}
int down(int n, int bin)
{
	for (int i = n - 1; i > 0; --i)
	{
		if (binari(i, bin) == bin) return i;
		else continue;
	}
	return 0;
}
int up(int n, int bin)
{
	for (int i = n + 1;; ++i)
	{
		if (binari(i, bin) == bin) return i;
		else continue;
	}
}
int main()
{
	int A;
	int bin;

	cin >> A;
	bin = binari(A, 0);
	cout << down(A, bin) << " " << up(A, bin);

	return 0;
}

계속 시간초과 되는 코드만 짜다가

저런 비트연산만으로는 안된다는 걸 깨닫고

구글링을 통해 혁신적인 방법을 알아내었습니다

[아래 참고자료 참조]

A의 Next Higher Number를 구하는 함수는 bitOper라고 할 때

Next Lower Number는 구하는 동작은 같으므로 반대로 해주면 됩니다

~bitOper(~A).

하지만 여기서 더이상 1, 3, 5, 7, 15처럼 최대 비트수에서 이미 1로 채워진 수는 구할 수 없습니다.

그런 Number는 -1이 나옵니다.

#include < iostream > 
using namespace std;
typedef long long BIG;
BIG A, B;
BIG bitOper(BIG num)
{
	BIG a = num&-num,
		b = a + num,
		c = ((num^b) >> 2) / a;
	
	return B = (b | c);
}
int main()
{
	BIG down, up;
	cin >> A;
	
	if (~bitOper(~A) == -1) down = 0;
	else down = ~B;
	up = bitOper(A);

	cout << down << " " << up;
	return 0;
}

참고자료

같은 1 비트를 같는 다음의 수

Next higher number with same number of binary bits set from GowriKumar Chandramouli

추가

비트연산, 쉬프트 연산 http://selfc.tistory.com/10

1의 보수, 2의 보수 http://zapiro.tistory.com/entry/컴퓨터의-음수-표현법보수법