[정올 2468] 비밀번호

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1729&sca=99&sfl=wr_hit&stx=2468 

JUNGOL

#include <stdio.h>

typedef unsigned long long u64;
u64 A, little, big;

/*
-큰 수 찾기
낮은 자리 비트에서 높은 자리로 이동하며 01인 경우를 찾고
01을 10으로 바꾼 후에,
바꾼 10보다 낮은 자리에 있는 1인 비트를 가장 오른쪽으로 몰아서 배치한다.

예를 들어 8비트 정수 01011100이 주어진 경우
01을 찾으면 ->	01'01'1100
10으로 바꾸면 ->	01'10'1100 (숫자가 점점 커지면서 1의개수가 같아지려면 자리올림이 일어나야 함)
10보다 낮은 자리 비트를 오른쪽으로 몰아 넣으면	->	011000'11'
(자리올림이 일어나면, 모자란 나머지 1의 개수는 작은 자리부터 증가해야 하기 때문에 오른쪽으로 몰아 넣는다)

-작은 수 찾기
낮은 자리 비트에서 높은 자리로 이동하며 10인 경우를 찾고
10을 01로 바꾼 후에
01보다 낮은 자리에 있는 1인 비트를 01의 오른쪽에 몰아서 붙여 넣는다.

예를 들어 8비트 정수 01011100이 주어진 경우
10을 찾으면 ->	01011100	(숫자가 점점 작아지면서 1의 개수가 같아지려면 자리내림이 일어나야 함)
01로 바꾸면 ->
(자리내림이 일어나면, 모자란 나머지 1의 개수는 큰 자리부터 증가해야 하기 때문에 바꾼 01의 가장 왼쪽부터 몰아 넣는다)
*/

u64 getBig(u64 a, int b = 0) {
	for (int i = 0; i < 62; i++, a >>= 1) {
		if ((a & 3) == 1) { //01인 경우
			//a ^ 3은 나머지 비트는 건드리지 않고 마지막 1,2 비트를 toggle
			//이당시 a는 01이었던 비트가 0번째 비트부터 시작할 것이므로 자릿수 i만큼 이동
			//미리 개수를 세 놓았던 b만큼을 맨 우측부터 채운다
			//1LL << b는 1000같은 것이고 여기서 -1을 하면 111처럼 된다.
			return ((a ^ 3) << i) + (1LL << b) - 1;
		}
		b += a & 1; //1의 개수
	}
	return -1; //비트반전
}

u64 getLittle(u64 a, u64 b = 0) {
	if ((a & (a + 1)) == 0) return 0; //a가 전부 1인 경우
	for (int i = 0; i < 62; i++, a >>= 1) {
		if ((a & 3) == 2) { //10인 경우
			return ((a ^ 3) << i) + b;
		}
		if (a & 1) b += (1LL << 1); //끝자리가 1이면 맨 왼쪽에 1 붙이고
		else b <<= 1; //끝자리가 0이면 맨 오른쪽에 0 붙인다.
	}
	return 0;
}

//u64 bit(u64 a) {
//	u64 lsb = a & -a; //lsb=가장 먼저 1이 나오는 비트
//	a = a / lsb + 1; //lsb로 나눈 a를 구함
//	//다시 a를 복구한 뒤에, 사라진 나머지 뒷자리들은, 
//	//new a의 lsb를 2를 나누고 1을 더해주면 된다.
//	return a * lsb + (a & -a) / 2 + 1;
//}

int main(void) {
	scanf("%lld", &A);

	u64 big = getBig(A);
#if 1
	u64 little = ~getBig(~A);//뒤집어서 big으로 찾고 다시 뒤집으면 됨
#else
	u64 little = getLittle(A);
#endif

	printf("%lld %lld\n", little, big);

	return 0;
}