[백준]#1322 X와 K

문제

두 자연수 X와 K가 주어진다. 그러면, 다음 식을 만족하는 K번째로 작은 자연수 Y를 찾아야 한다.

X + Y = X | Y

|는 비트 연산 OR이다.

입력

첫째 줄에 X와 K가 주어진다. X와 K는 2,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 X + Y = X | Y를 만족하는 K번째 작은 Y를 출력한다. 정답은 int 범위를 넘어갈 수 있다.

예제 입력 1

5 1

예제 출력 1

2

풀이

이 문제는 수학적인 풀이가 필요한 문제였다.

우선 X+Y = X|Y 이려면 이진수로 나타냈을 때 X의 자릿수가 1이면 무조건 Y의 해당 자리수는 0이어야 한다.

나머지 자리수는 K만큼 1을 더해주면 정답을 구할수 있다.

예제의 X=5를 예로들면 이진수로 바꾸면 X = 101 이다. 그러면 Y = ???...0?0 로 나타낼 수 있다.

K=1 00010

K=2 01000

K=3 01010
.
.

0으로 고정된 부분을 제외하고 보면

K=1 001 -> 1

K=2 010 -> 2

K=3 011 -> 3

한마디로 X의 자리수중 1인 자리수는 0으로 고정하고 나머지 빈 부분에 K를 이진수로 표현한 자리수를 넣어주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        long X = Long.parseLong(input[0]);
        long K = Long.parseLong(input[1]);

        System.out.println(sol(X, K));
    }

    static long sol(long X, long K) {
        String strX = Long.toBinaryString(X);
        String strK = Long.toBinaryString(K);
        StringBuilder sb = new StringBuilder();
        int idx = strK.length()-1;

        for(int i=strX.length()-1; i>=0; i--) {
            char c = strX.charAt(i);

            if(c=='1') {
                sb.insert(0, 0);
            }

            else {
                if(idx==-1) continue;   //K의 자리수를 모두 넣어줬을 

                sb.insert(0, strK.charAt(idx));
                idx--;
            }
        }

        while(idx>=0) {     //K의 자리수 남았을 때
            sb.insert(0, strK.charAt(idx));
            idx--;
        }

        return Long.parseLong(sb.toString(), 2);
    }
}