AtCoder Beginner Contest 129：E - Sum Equals Xor
問題
解法
a + b == a XOR b となるためには，a と b で任意の bit の桁が 1 と 1 になってはいけない．1 XOR 1 は 0 となるが，1 + 1 は 10 と繰り上がりが発生し a + b != a XOR b となってしまう．
L の中で bit が立っている桁それぞれについて（k bit 目とおく），a + b の k bit 目より大きい桁が L と一致し，k bit 目を 0 にし，k bit 目より小さい桁を 0 か 1 とするときの通り数を考える．k bit 目より小さい桁は「a も b も 0」，「a か b の一方が 1」の 3 通りそれぞれある．また，k bit 目より大きい桁は「a か b の一方が 1」の 2 通りそれぞれある．この 2 つを掛け合わせたものをを全て足しせば L の中で bit が立っている桁のうち最低 1 つを 0 にするときの場合の数が求まる．そこに，L == a + b となる通り数 2^(L の中で bit が立っている個数) を足す必要がある．O(|L|)．
解答
