Arvi Fox website

XOR

Wiki

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:

int x=5, y=7;
x=x^y; //x==2
y=x^y; //y==5
x=x^y; //x==7

or

y^=(x^=y);
x^=y;

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

v ^= val1 ^ val2;

Crypto

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

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

XORShift

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;
	}
}

XOR is used to nil variable

XOR linked list

Bit Twiddling Hacks

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

 

Leave a Reply

 

Close Menu