в прочем обычные фишки, вроде, x ^ x = 0, или же XOR отрезка от 1 до N в О(1)

Fan fact — XOR linked list

$$$a \oplus b \lt 2n \text{ for }a,b \le n$$$

XOR can be represented using OR and AND

$$$a \oplus b = (a \text{ OR } b) - (a \text{ AND } b)$$$

XOR is self-inverse:

$$$a \oplus b = c \Longleftrightarrow a=c \oplus b$$$

Problems related to XOR often can be solved bitwise (for all of the bits independently)

XOR is in fact addition in $$${Z}_{2}^{d}$$$ space, so many facts from linear algebra can be used in XOR related stuff (XOR basis is a good example)

surprised this never got mentioned.

a^=b b^=a a^=b

is a valid way to swap a and b if a and b are integer types.

Haven't solved much harder problems. But ig I used these +(observation) mostly.

1. a+b = a^b +2(a&b) probably the most used formula :)
2. a^b<=2*max(a,b)
3. xor sum form 0 to n vector<long long> _p = {n, 1, n + 1, 0}; return _p[n % 4];
4. swap using xor a^=b,b^=a,a^=b

$$$1\oplus2\oplus3\oplus\dots\oplus(4n-1)=0$$$ for all $$$n\in\mathbb Z^+.$$$

$$$a-b \le a\oplus b \le a+b$$$

Ask Coffee_zzz, who stands for the GCD-XOR-MEX group.

Idk if it's obvious or not but,

If addition of a and b is a odd number then their XOR will also be an odd number, And if addition is even then XOR will be even too.

(Yeah that 1st bit is all what it is)

deleted

a+b=a⊕b+2⋅(a&b)

Luogu P10857.

given a edge-weighted tree, after calculating xor[v]=xor of weights on path from root to v, xor[u]^xor[v]= xor of weights on path from u to v

XOR is an addition and subtraction without carryovers!

0 , 1 , 2 , 3 forms the Klein four group under the binary operator XOR which is an abelion group.

1^0 = 1
2^0 = 2
3^0 = 3
1^2^3 = 0
1^2 = 3
2^3 = 1
1^3 = 2
1^1 = 2^2 = 3^3 = 0

XOR is the opposite of if and only if

XOR is a kind of addition without carry

Thats why a+b = a^b means a&b=0

You can find this logic used in multiple CF Div. 2 C/D bitwise questions (✿◠‿◠)

use xor to solve Nim.

let $$$a_1, \dots a_n \gt = k$$$ and $$$n$$$ be even.

Then either:

$$$a_1 \oplus a_2 \oplus \dots \oplus a_n \gt = k$$$

or

$$$\exists j$$$ such that $$$a_1 \oplus a_2 \oplus \dots a_{j-1} \oplus a_{j+1} \oplus \dots \oplus a_n \gt = k$$$

A boolean can be toggled by XORing with true.

Also if an integer is either 0 or x (x is another integer) it can be toggled between 0 and x by XORing with x.

most of the task with xor can be solved independently for each bit

This is a meaningful problem because i have met many problems using these knowledge,though i haven't understand it

A pretty fun fact that I have heard of but never actually been able to learn: xor is also known as Nimber addition. There's also something called Nimber multiplication, which also has commutativity property, associativity property, and distributive property with xor. Together, they form a complete field, also known as the Nimber field.

There are some pretty cool problems that could be solved with these operations, but it seems too advanced for me to understand =))))

Let $$$a = [a_1, a_2, \ldots, a_n]$$$ be non-decreasing array of integers, then $$$\min_{i \neq j}(a_i \oplus a_j) = \min_{1 \leq i \lt n}(a_i \oplus a_{i + 1})$$$

It seems that any even number which greater than 2 can be decomposed into the XOR of two prime numbers.

Can anyone prove it? It looks like the XOR version of Goldbach's Conjecture.

Xor of n-bit numbers acts like addition of n-dimensional vectors over $$$\mathbb Z/2\mathbb Z$$$, which means you can use various linear algebra properties with it. Such as finding a "basis", i.e. for a collection of numbers, you can a minimal set of numbers out of a set that generate all the others with xor's.