[백준 1322] X와 K (Java)

문제 링크: https://www.acmicpc.net/problem/1322

1322번: X와 K

1. 주의할 점

- 출력 결과를 Long 타입으로 출력한다

- 계산하는 과정에서 Int타입을 벗어날 수 있다

 

2. 구현

- X+A = X|A 를 만족하려면, X를 비트로 바꿨을 때, 0에 해당하는 부분을 1로 채워주면 된다

- 이 과정에서 위의 식이 성립하는 K번째로 작은 수를 구하기 위해 K도 비트로 바꾼다

- 왼쪽부터 시작해서 X의 0에 해당하는 부분이 현재 K를 비트로 바꿨을때 1이라면 해당하는 만큼의 수를 더하고 0이라면 더하지 않는다

(아래 TC 참조)

#1
X = 10 -> 1010
K = 5 -> 101

X =        1010
K = 	  1 0 1
Result = 2^0 + 2^4 = 17

#2
X = 11 -> 1011
k = 5 -> 101

X = 	1011
K =   10 1
Result = 2^2 + 2^5 = 36

 

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine();
	    StringTokenizer st = new StringTokenizer(str);
	    int x = Integer.parseInt(st.nextToken());
	    int k = Integer.parseInt(st.nextToken());
	    
	    String sx = Integer.toBinaryString(x);
	    String sk = Integer.toBinaryString(k);
	    int klen = sk.length();
	    int xlen = sx.length();
	    int idx = klen-1;
	    long result=0;
	    char c;
	    
	    for(int i=0;idx>=0;i++){
	        if(i<xlen)  c = sx.charAt(xlen-1-i);
	        else c = '0';
	        if(c=='0'){
	            if(sk.charAt(idx)=='1'){
	               long vv = (long)Math.pow(2,i); 
	               result+=vv;
	            }
	            idx--;
	        }
	    }
	    System.out.println(result);
	}
}