비트방정식

 
#include 

int main() {
	// x|y = x+y 가 성립하는 k번째 y값은? 

	//int x = 18;	// 10010
	
	// 00001 -> ok
	// 00010 -> no
	// 00011 -> no
	// 00100 -> ok

	// x|y = x+y 가 성립되는 조건은 2진수로 변환하면 서로 겹치는 부분이 없음.
	
	unsigned long long int x;
	unsigned long long int k;

	scanf_s("%llu", &x);
	scanf_s("%llu", &k);

	int count = 0;
	unsigned long long int y =0;		// y가 비교할 값

	/* 이렇게 작성하면 순차적으로 돌기 때문에 알고리즘 성능이 좋지 않다.
	while (1) {
		if (count == k) break;
		y++;		// 이 부분을 어떻게 효율적으로 올릴 수 있을까?
		if ((y&(x^y)) == y) count++;	// 여기는 비교 부분
		// x^y 연산을 통해 겹치는 부분을 찾고, 마스킹을 통해 원본과 비교
		// x와 y가 겹치는 부분이 있다면 xor 연산 때문에 원본과 달라진다.
	}
	*/

	/*
	여기서부터는 새로운 방법으로..
	사실 공책으로 풀면 굉장히 쉬운 것 같다. 여기서 말로 설명하기는 어렵지만
	다시 입력으로 18, 5가 들어온 경우를 생각해본다.

	(x) 18은 2진수로 10010
	(k) 5는 2진수로 101

	참고로 조건 : x|y = x+y 가 성립되는 조건은 2진수로 변환하면 서로 겹치는 부분이 없음.
	위의 식을 만족하는 k번째 작은 수는 k의 비트 갯수만큼 위의 조건을 만족하며 진행해나가면 된다.

	1. 18의 마지막 비트는 10010 에서 0이기 때문에 값을 넣을 수 있다.
	2. k의 마지막 비트는 101 에서 1이기 때문에 1을 18의 마지막 비트로 채워준다. (정답은 00001)
	3. 18의 다음 0인 비트는 10(0)10 에서 괄호친 부분이다. 
	4. k의 2번째 비트는 1(0)1 에서 0이기 때문에 18의 괄호친 부분은 넘어간다.
	5. 18의 다음 0인 비트는 1(0)010이다.
	6. k의 3번째 비트는 (1)00 이기 때문에 값을 넣을 수 있다. 5번에서 괄호친 부분에 1을 채워준다. (정답은 01001 -> 9)

	인풋 조건의 값이 크기 때문에 형식 잘 계산하자... 몹시 화가난다.
	*/

	unsigned long long int zeroCheckIndex_x = 0;
	unsigned long long result = 0;

	while (k != 0) {
		if (((x >> zeroCheckIndex_x) & 1) == 0) {	// 만약 x의 0인 부분을 찾았다면
			if (k & 1) {	// k 또한 넣어야 할 자리인가? 검사
				result = result | ((unsigned long long int)1 << zeroCheckIndex_x);	// 넣어도 된다면 1을 채워놓고
			}
			// k가 0이라 넣으면 안되는 자리라면
			zeroCheckIndex_x++;	// 검사할 x 값 다음으로
			k = k >> 1;			// k 또한 다음으로
		}
		else {
			zeroCheckIndex_x++;
		}
	}
	
	printf("%llu\n", result);

	system("pause");
}

양의 정수 X와 K가 주어졌을 때, 다음의 방정식을 만족하는 임의의 양의 정수 Y 중에서 K번째로 작은 숫자를 찾는 프로그램을 작성하라.

 

X + Y = X | Y

 

여기서 '|'는 OR연산을 뜻한다. OR연산은 두 개의 정수를 2진수로 바꾼 다음에 2진수로 이뤄진 숫자의 동일한 위치에 대해서 둘 다 0일 경우 0, 둘 중에 하나라도 1일 경우 1을 취하는 연산자다.

 

예를 들어 X가 3이고, Y가 6일 경우 X | Y는 다음과 같다. 011 OR 110 = 111, 111을 10진수로 바꾸면 7이므로, 3 | 6 = 7이 된다.