XOR, bit twiddling

Wiki

Манипуляции с битами. Игра в истину [https://nuancesprog.ru/p/4597]

A	B	A xor B
0	0	0
0	1	1
1	0	1
1	1	0

a xor 0 = a

a xor 1 = not a

a xor a = 0

a xor b = b xor a

(a xor b) xor c = a xor (b xor c)

How to swap 2 variables:

[code language="java"]
int x=5, y=7;
x=x^y; //x==2
y=x^y; //y==5
x=x^y; //x==7
[/code]

or

[code language="java"]
y^=(x^=y);
x^=y;
[/code]

or, change value of variable if it is only these two values:

[code language="java"]
v ^= val1 ^ val2;
[/code]

Crypto

(a xor k) xor k = a, where k is key

[code language="java"]
public static byte[] encode(String pText, String pKey) {
		byte[] txt = pText.getBytes();
		byte[] key = pKey.getBytes();
		byte[] res = new byte[pText.length()];

		for (int i = 0; i < txt.length; i++) {
			res[i] = (byte) (txt[i] ^ key[i % key.length]);
		}

		return res;
	}
[/code]

[code language="java"]
public static String decode(byte[] pText, String pKey) {
		byte[] res = new byte[pText.length];
		byte[] key = pKey.getBytes();

		for (int i = 0; i < pText.length; i++) {
			res[i] = (byte) (pText[i] ^ key[i % key.length]);
		}

		return new String(res);
	}
[/code]

XORShift

[code language="java"]
class XORShift {

	private long rnd;

	public XORShift(long rnd) {
		this.rnd = rnd;
	}

	public long getRandom() {
		this.rnd ^= (this.rnd << 21); this.rnd ^= (this.rnd >>> 35);
		this.rnd ^= (this.rnd << 4);
		return this.rnd;
	}
}
[/code]

XOR is used to nil variable

XOR linked list

Bit Twiddling Hacks

K * 2^N [https://telegra.ph/UniLecs-129-Pobitovaya-arifmetika-09-23]

[https://telegra.ph/Anons-129-Pobitovaya-arifmetika-09-23]

Problem:

there is an array of natural numbers from 1 to n. Size is 2n-1. All numbers have a pair, except one. Find the one.

Solution: just xor all items in the array. Also sum of first N natural numbers is n*(n+1)/2