Official

A - Bitwise Exclusive Or Editorial by kyopro_friends


プログラミングの学習を始めたばかりで何から手をつけるべきかわからない方は、まずは practice contest の問題A「Welcome to AtCoder」をお試しください。言語ごとに解答例が掲載されています。


XOR の性質を使う解法

もしこの問題が XOR ではなく足し算だった場合、つまり「\(A+C=B\) となる \(C\) を求めよ」であれば、両辺から \(A\) を引くことで \(C=B-A\) として求めることができます。
足し算の場合に「両辺から \(A\) を引く」にあたる操作は、XORの場合には何になるでしょうか?

実は、任意の非負整数 \(A\) に対して、\(A \ XOR \ A=0\) が成り立ちます。したがって両辺に \(A\) を XOR することで左辺の \(A\) は相殺され、\(C=B\ XOR \ A\) として \(C\) を求めることができました。

XOR の計算には ^ の演算子が割り当てられている言語が多いです。

実装例(C)

#include<stdio.h>

int main(){
  int a,b;
  scanf("%d%d",&a,&b);
  printf("%d\n",a^b);
}

実装例(Python)

A,B = map(int, input().split())
print(A^B)

全探索する解法

答えは\(0\) 以上 \(255\) 以下の \(256\) 個の整数であることがわかっています。\(256\) 個全ての場合について、等式を満たすかどうか調べることでもこの問題を解くことができます。

実装の際は演算子の優先順位に注意が必要な場合があります。

実装例(C)

#include<stdio.h>

int main(){
  int a,b;
  scanf("%d%d",&a,&b);
  for(int c=0;c<=255;c++){
    if((a^c)==b){
      printf("%d\n",c);
      return 0;
    }
  }
}

実装例(Python)

A,B=map(int,input().split())
for C in range(256):
  if (A^C)==B:
    print(C)
    exit()

posted:
last update: