Nogaybica's blog

By Nogaybica, history, 20 months ago, In English

I often come across problems on this fascinating topic and would like to learn about various strategies and clever tricks related to XOR

  • Vote: I like it
  • +24
  • Vote: I do not like it

| Write comment?
»
20 months ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

Fan fact — XOR linked list

»
20 months ago, hide # |
← Rev. 2  
Vote: I like it +33 Vote: I do not like it

$$$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)

»
20 months ago, hide # |
 
Vote: I like it +24 Vote: I do not like it

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.

»
20 months ago, hide # |
← Rev. 2  
Vote: I like it +10 Vote: I do not like it

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
»
20 months ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

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

»
20 months ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

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

»
19 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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)

»
19 months ago, hide # |
← Rev. 2  
Vote: I like it -24 Vote: I do not like it

deleted

»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Luogu P10857.

»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

XOR is an addition and subtraction without carryovers!

»
19 months ago, hide # |
 
Vote: I like it +7 Vote: I do not like it

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

»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

XOR is the opposite of if and only if

  • »
    »
    19 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    care to explain wdym ser?

    • »
      »
      »
      19 months ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it

      So for an if and only if statement to work, if one thing is true, the other thing has to be true, and if the other thing is true, the first thing has to be true. Conversely, if one thing is false, the other thing has to be false, and vice versa. So if we let our things be bits, we get $$$1 \iff 1 = 1$$$ and $$$0 \iff 0 = 1$$$. This also means that $$$1 \iff 0 = 0$$$ and $$$0 \iff 1 = 0$$$, because they both violate the conditions. Thus, the if and only if operator returns the opposite of what xor would return.

»
19 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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 (✿◠‿◠)

»
19 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

use xor to solve Nim.

»
11 months ago, hide # |
← Rev. 2  
Vote: I like it +2 Vote: I do not like it

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$$$

  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Proof for this?

    • »
      »
      »
      11 months ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      If the xor of all values is greater that $$$k$$$ we are done.

      Let $$$t$$$ be the first active bit in $$$a$$$ such that is not in $$$k$$$. If we choose that value, from $$$a_i \ge k$$$ we get that all bits more significant that $$$t$$$ in $$$k$$$ are also active in $$$a_i$$$. From parity and the fact that the xor of all values is less than $$$k$$$ we get that the number of values in $$$a$$$ with this bit on is even. So if we choose this value, this bit will become active in the xor of all remaining numbers and so the more significant bits in $$$k$$$.

      If $$$t$$$ does not exists, it means that $$$a_i = k$$$ for all $$$i$$$ and you can subtract any value.

»
11 months ago, hide # |
 
Vote: I like it -14 Vote: I do not like it

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.

»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

»
11 months ago, hide # |
 
Vote: I like it +6 Vote: I do not like 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 =))))

»
11 months ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

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})$$$

»
11 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    11 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Any source for where this comes from?

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Just wrote C++ and confirmed this is true when $$$n\le10^9$$$.

  • »
    »
    10 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Well, unless someone manage to prove this, I believe you are in a similar situation as in the original conjecture, it hasn't been proven but it is likely true.

    Assume that primes are randomly distributed, given a pair of numbers such that their xor (or their sum) is $$$n$$$, the probability of both being primes is $$$O(1/log^2(n))$$$, there are $$$O(n)$$$ pairs that sum $$$n$$$. If you discard small values with a bruteforce, the probability that the conjecture is true quickly tends to 1.

»
10 months ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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.