読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

XOR

競技プログラミング

排他的論理和(XOR)についての性質のメモ

A^B = (A&!B)|(!A&B)
    = (A|B)&(!A|!B)
    = (A|B)&(!(A&B))
  • A^B = B^A(交換則)
  • A^A = 0
  • A^B = 0 ならば A = B

a, b, c…が0か1のとき、

a^b^…^c = 1 (1が奇数個)
           0 (1が偶数個)