XOR
I am dedicating XOR its own page because it comes up a lot in Competitive Programming and is pretty different from the other bitwise operators?
XOR is really great for Parity Check.
Really cool, Negating every bit of a number is equivalent to XOR every bit with 1, i.e., with a number of equal size where all bits are 1.
a ^ 1 is NOT same thing as -a, you need like a ^ 111111…1
A way to think about XOR
“XOR is just addition with carry”
- I realized this after reading the editorial to problem C2
this tells you that a ^ b <= a + b
You also have
- “xor is like subtraction without borrowing.”
This tells you that a ^ b >= a - b
Approaching XOR Problems
When you see XOR problems, you generally approach it from a bit by bit basis. For example, this 1700 problem https://codeforces.com/problemset/problem/1879/D
- https://www.youtube.com/watch?v=tODo9BSLSmM explanation by Geothermal
Maximum XOR Subarray
Saw through this problem 1847C.
- Another way you could have realized you simply need to find the subarray, is realize that xor is just addition without carry (see note above). So XOR will never exceed the values by a contiguous subarray.
How do you compute the maximum XOR subarray? There’s this implementation https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/, which can use a Trie. However, there should be other better methods.
in the codeforces problem, since each a[i] is bounded by , you can just store all possible xor values. And then treat that as a constant factor.
More Problems
Given x, Count the number of integers y such that x ^ y is divisible by either x, y or both, for up to a very large number ()