비트 연산자 OR 의 기본적인 특징에 대해 생각해 볼 수 있는 문제 였다.
제출코드
import sys
input = sys.stdin.readline
x, k = map(int, input().split())
bin_x = bin(x)[2:]
bin_k = bin(k)[2:]
k_idx = len(bin_k) -1
x_idx = len(bin_x) -1
target = ""
while k_idx != -1 and x_idx != -1:
if bin_x[x_idx] == "0":
target = bin_k[k_idx] + target
k_idx -= 1
else:
target = bin_x[x_idx] + target
x_idx -= 1
if k_idx != -1:
target = bin_k[:k_idx+1] + target
if x_idx != -1:
target = bin_x[:x_idx+1] + target
target = int("0b"+target, 2)
print(target - x)접근방법
문제에서 요구하는건 x+y = x|y 를 만족하는 값 중에 k 번째로 작은 y값이었다.
x 와 k 의 최대값이 2,000,000,000 이었기 때문에 브루트포스로는 풀 수 없었다. (시간제한 2초)
그럼 OR 연산자의 특성에 대해 생각해 봐야 한다.
0101 | 0000 == 0101 이고
1111 | 1000 == 1111 이다.
즉 s번째 자리수가 1인 이진수를 임의의 이진수 t와 OR 연산을 하면 t값이 무었이든지 s번째 자리수는 1이된다.
x 값은 처음에 주어진다. 즉 x를 2진수 값에서 자리수가 "1"인 부분은 y 값에 상관없이 "1"이 유지된다.
자, 그럼 x+y = x|y 를 만족한는 y를 어떻게 구할 수 있을까?
결론부터 말하자면 x의 이진수 값에서 s번째 자리수가 "1" 일때 y의 이진수 값의 s번째 자리수가 0이면 된다.
이 조건만 만족한다면 x+y = x|y 를 만족한다.
OR 연산에서는 덧셈연산에서 올림 계산이 없기 때문에 s번째 자리수가 둘다 1이 온다면 덧셈값보다 무조건 작아지게 되어있다.
그래서 x의 이진수 값에서 자리수가 0인 부분을 0 <-> 1 을 조정하며 k번째 값을 찾을 수 있다.
물론 20억번째 까지 찾아야될 수도 있기때문에 일일이 0 <-> 1 을 조정할 수는 없다.
단지 주어진 k를 이진수로 바꿔서 x의 2진수값의 0인 부분에 채워 넣으면 된다.
예를 들어 x = 7, k = 9 라고 하자.
각각의 이진수값은
bin_x = 0111
bin_k = 1001 이다.
bin_x 의 "111" 이부분은 OR 연산에서 고정된 값으로 나오기 때문에 "0" 인부분에 단지 k를 채워 넣으면된다.
예시에서는 bin_x = 0000111 으로도 나타낼수 있기에 bin_k값을 순서대로 붙인
1001111 이 나오게 된다.
단, 이값은 x+y 값이므로 x값을 빼서 y값을 찾아줘야 한다.
