#1322 X와 K(Mathematics)

이번 문제는 Gold IV 난이도 문제이지만, 수학적인 원리를 알고 있으면 아주 쉽게 풀 수 있습니다.

 

주어진 X에 대하여 다음을 만족하는 Y를 구하는데, K번째 Y를 구하는 문제입니다.

\[ X + Y = X | Y \]

여기서 | 연산자는 Bitwise OR 로 비트합을 계산합니다.  비트합은 각 비트끼리 논리합(Logical OR)을 합니다.

이를 만족하는 Y 는 X의 비트 중, 1인 부분은 반드시 0이어야 하고, 0인 부분은 1이든 0이든 상관이 없습니다.

 

만약, X의 비트 중 1인 부분에 같은 위치의 Y의 비트가 1이라고 한다면, 비트합에서는 1이 되지만, 덧셈에서는 0이 됩니다.  어떻게 잘 조합하면 될 것이라고 생각할 수 있지만, 그럴 수 없습니다.  X의 비트와 Y의 비트중 같은 위치에 1이 있다면, 그 중 가장 오른쪽에 비트를 고릅니다.

덧셈에서는 1+1 = 2가 되므로, 실제 비트로는 0이 됩니다.  이것을 1로 바꾸려고 하려면, 자리올림인 캐리(Carry)가 발생해야 하는데, 0+0, 0+1, 1+0 으로는 자리올림이 발생하지 않습니다.  그래서 결국 1로 바꿀 수가 없죠.

 

주어진 X에 대해서 K번째로 작은 수는 K를 1씩 증가하면서 겹치는 비트가 있는지 검사할 수 있습니다.  하지만 이 방법은 X의 비트에 1이 많다고 하면 꽤 많은 반복을 해야 합니다.

 

제가 생각한 방법은 아주 단순합니다.  X의 비트를 나열해놓고, K를 X의 비트중 0인 자리에 맞추어 다시 쓰는 것이죠.

X = 46 이고, K = 13 이라고 한다면, 이를 2진 수로 표현하면 다음과 같습니다.

 

0

0

1

0

1

1

1

0

 

13는 2진수로 \(1101_2\)입니다.  이것을 0이 써진 곳에 맞추어 쓰면,

 

1

1

0

0

0

0

0

1

 

이 됩니다.  그래서 13번째 Y는 \(11000001_2 = 193\)을 얻게 됩니다.

 

이것을 이용하면, 반복해서 맞추어보지 않아도 K번째 수를 알아낼 수 있습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//--------------------------------------------------------------------
//  baekjoon #1322 X and K
//    - by Aubrey Choi
//    - created at 2019-08-17
//--------------------------------------------------------------------
#include <stdio.h>

int main()
{
  long long x, k, s = 0;
  scanf("%lld%lld",&x,&k);
  for(int i=0, j=0; k>>j; i++)
  {
    if((x>>i)&1) continue;
    s |= ((k>>j)&1)<<i;
    j++;
  }
  printf("%lld\n", s);
}