[白俊]#1322 XとK

質問する

2つの自然数XとKを与えた.では,次の式を満たすK番目の小さな自然数Yを見つける.
X + Y = X | Y
|はビット演算ORです.

入力

最初の行はXとKを与える.XおよびKは、20000000以下の自然数である.

しゅつりょく

1行目の出力はX+Y=X|Yを満たすK小Yである.答えはintの範囲を超えてもいいです.

入力例1

5 1

サンプル出力1

2

に答える

この問題には数学の解答が必要だ.
まず、X+Y=X|Yが2進数であれば、Xのビット数が1であれば、Yの対応するビット数は0でなければならない.
残りの桁数はKプラス1で正解が得られます.
例えば、例中のX=5であり、バイナリ数をX=101とする.ではY=???0?ゼロと表示できます.
K=1 00010
K=2 01000
K=3 01010
.
.
ゼロに固定されている部分を除いて
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);
    }
}