Bitwise operations and Logical operations using XOR

XOR

^ - bitwise exclusive OR - bitwise XOR

Properties

A XOR B COR A = B

Thus, if any value is added an even number of times to XOR operations, then this value is removed from the result.

Explanation using bits

e.g.

1 XOR 2

1. 1 is represented as 01 in binary.
2. 2 is represented as 10 in binary.

So, 1 XOR 2 is 01 XOR 10. This results in 11 - which equals decimal 3.

1. If we do XOR with this result and 1, 11 XOR 01 = 10, which is decimal 2.
2. If we do XOR with this result and 2, 11 XOR 10 = 01, which is decimal 1.

Given an array of integers where every element appears twice except for one, find that single number.

Based on the explanation above, we can just run a loop on the array, and all the elements that appear twice in the array will be removed from the end result of the XOR.

By the end, the only remaining result will be the bit values for the element that appears in the array only once.

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

The result of XOR of first n natural numbers with the XOR of all the array elements will be the missing number. To do so, calculate XOR of first n natural numbers and XOR of all the array arr[] elements, and then our result will be the XOR of both the resultant values.

Swapping numbers using bitwise operations

The beauty of this method is, we do not have to worry about the datatype of the input variables. Or, their limits. We don’t have to worry about overflows. This will work in any language, including the ones that do not support overflows.

public static ImmutablePair swapUsingBitwiseManipulation(ImmutablePair pair) {
    int a = (int) pair.left;
    int b = (int) pair.right;

    a = a ^ b;
    b = a ^ b; // actually (a ^ b) ^ b, which would give us a -> assign this value to b.
    a = a ^ b; // which is, (a ^ b) -((a ^ b) ^ b) = (a ^ b) ^ a = b -> assign this value to a.

    return new ImmutablePair(a, b);
  }

Find two numbers from their sum and XOR

TODO

1. https://www.geeksforgeeks.org/dsa/find-two-numbers-sum-xor/
2. https://stackoverflow.com/questions/36477623/given-an-xor-and-sum-of-two-numbers-how-to-find-the-number-of-pairs-that-satisf

Easy/Beginner:

1. Single Number:

Given an array of integers where every element appears twice except for one, find that single number.

1. Missing Number:

Given an array containing n distinct numbers taken from 0, 1, 2, …, n, find the one that is missing from the array.

1. Two Sum - XOR Version:

TODO

Given an array of integers and a target value, find two numbers in the array that add up to the target (using XOR to potentially optimize).

Intermediate:

1. Maximum XOR of Two Numbers in an Array:

Given an array of integers, find the maximum result of XOR between any two numbers in the array.

https://www.codeproject.com/Tips/890442/Maximizing-XOR-Challenge-Sample#:~:text=Background,avoid%20giving%20away%20potential%20solutions.

1. Subarray XOR Queries:

Given an array of integers and a list of queries, each query containing a start and end index, return the XOR of the elements in the subarray.

https://www.codechef.com/practice/course/1-star-difficulty-problems/DIFF1200/problems/MINMXOR

1. The Great XOR:

Find the number of integers less than a given integer ‘x’ that have a bitwise XOR with ‘x’ resulting in a value greater than ‘x’.

https://www.hackerrank.com/challenges/the-great-xor/problem#:~:text=Function%20Description,the%20following%20parameter(s):

1. Interesting XOR:

Given an integer C, find the maximum product of A and B where A XOR B = C and A, B are less than 2d, where 2d is the smallest power of 2 greater than C.

https://www.codechef.com/practice/course/2-star-difficulty-problems/DIFF1500/problems/IRSTXOR

Advanced:

1. Communication Complexity of XOR Function:

Analyze the communication complexity of the XOR function in different communication models.

https://www.numberanalytics.com/blog/ultimate-guide-xor-function-communication-complexity#:~:text=The%20XOR%20function%20has%20significant,complexity%20of%20at%20least%20n.

1. XOR Basis:

Find a minimal set of vectors that can generate all other vectors in a given set using XOR as the operation.

https://codeforces.com/blog/entry/68953#:~:text=In%20view%20of%20this%20plane,xor%20of%202%20and%203.

Tips for solving XOR problems

XOR’s Properties

Remember that A XOR A = 0, and A XOR 0 = A. Also, XOR is commutative and associative.

https://accu.org/journals/overload/20/109/lewin_1915/#:~:text=Important%20properties%20of%20XOR&text=This%20means%20that%20XOR%20operations,try%20drawing%20the%20truth%20tables.&text=This%20means%20that%20any%20value,with%20zero%20is%20left%20unchanged.&text=This%20means%20that%20any%20value%20XOR'd%20with%20itself%20gives%20zero.

Bit Manipulation

XOR is often used for bit manipulation tasks, such as toggling bits or checking if a bit is set.

https://learn.microsoft.com/en-us/dotnet/visual-basic/language-reference/operators/xor-operator#:~:text=For%20example%2C%205%20Xor%203,of%20the%20decimal%20number%206.

https://brainly.com/question/35127628#:~:text=The%20bitwise%20XOR%20of%2011110000%20and%2010101010%20is%2001011010.

Look for Patterns

Many XOR problems involve finding a unique element in a set where all other elements are paired.

https://dev.to/oliverjumpertz/xor-bitwise-xor-and-using-it-to-solve-an-algorithm-challenge-14oa#:~:text=It%20goes%20as%20follows:,returns%20null%20null%20%2D%3E%20returns%20null

https://emre.me/coding-patterns/bitwise-xor/

Think in Binary

Converting numbers to their binary representation can help visualize the XOR operation.

https://learn.microsoft.com/en-us/dotnet/visual-basic/language-reference/operators/xor-operator#:~:text=For%20example%2C%205%20Xor%203,of%20the%20decimal%20number%206.

Don’t be afraid to experiment with XOR on small examples

It can help you discover patterns that might not be obvious.

https://stackoverflow.com/questions/77624738/xor-operator-problems-in-c#:~:text=There's%20no%20difference%20between%20A,interpreted%20from%20right%20to%20left.