Bitwise_XOR_Tutorial.txt

Bitwise XOR
============

- Introduction:
===============

    Bitwise XOR (exclusive OR) is a binary operation that operates on the individual bits of its operands. It is a fundamental
    operation in digital logic and computer science, commonly used in tasks like encryption, error detection, and data manipulation.

    - How Bitwise XOR Works:
    ------------------------

    Bitwise XOR compares corresponding bits of two numbers and returns a new number where each bit is set to 1 if the corresponding
    bits of the operands are different, and 0 if they are the same.

    Here's a bit-by-bit comparison for clarification:

        - 0 XOR 0 = 0
        - 0 XOR 1 = 1
        - 1 XOR 0 = 1
        - 1 XOR 1 = 0

    - Example Calculation:
    ----------------------

    Consider the bitwise XOR of the binary numbers `1010` and `1100`:

            1010
        XOR 1100
        ---------
            0110

    - The first bit: 1 XOR 1 = 0
    - The second bit: 0 XOR 1 = 1
    - The third bit: 1 XOR 0 = 1
    - The fourth bit: 0 XOR 0 = 0

    The result is `0110`.

    - Properties of Bitwise XOR:
    ----------------------------

        1. Commutative: `A XOR B = B XOR A`
        2. Associative: `(A XOR B) XOR C = A XOR (B XOR C)`
        3. Identity: `A XOR 0 = A`
        4. Self-inverse: `A XOR A = 0`

    - Applications:
    ---------------

        1. Swapping Values: XOR can be used to swap two values without using a temporary variable:

                a = a XOR b
                b = a XOR b
                a = a XOR b

        2. Encryption and Decryption: In some simple encryption algorithms, a key is XORed with the plaintext to produce
            ciphertext.
        3. Checksum and Error Detection: XOR is used in generating parity bits for error detection in data transmission.

    Bitwise XOR is a versatile and efficient operation widely used in low-level programming and computer science for its
    unique properties and simplicity.

    - Implementation:
    -----------------

    In Java, the bitwise XOR operator is represented by the caret symbol (`^`). It operates on the individual bits of
    its operands and returns a new integer whose bits are set according to the XOR logic.

        * Syntax

        result = operand1 ^ operand2;

        * Example Usage

        Here's an example demonstrating the use of the bitwise XOR operator in Java:

        public class BitwiseXORExample {
            public static void main(String[] args) {
                int a = 10; // in binary: 1010
                int b = 12; // in binary: 1100

                // Perform bitwise XOR
                int result = a ^ b;

                // Print the result
                System.out.println("a ^ b = " + result); // Outputs 6, which is 0110 in binary
            }
        }

        * Detailed Breakdown

        Let's break down the example:

        - `a = 10` which is `1010` in binary.
        - `b = 12` which is `1100` in binary.
        - Performing `a ^ b` (bitwise XOR):

          1010
        ^ 1100
        ------
          0110

        - The result is `6`, which is `0110` in binary.

        * Swapping Two Numbers Using XOR

        One of the classic uses of the XOR operator is swapping two numbers without using a temporary variable:

            public class XORSwapExample {
                public static void main(String[] args) {
                    int x = 5; // in binary: 0101
                    int y = 9; // in binary: 1001

                    // Display original values
                    System.out.println("Before swapping: x = " + x + ", y = " + y);

                    // Swap using XOR
                    x = x ^ y;
                    y = x ^ y;
                    x = x ^ y;

                    // Display swapped values
                    System.out.println("After swapping: x = " + x + ", y = " + y);
                }
            }

    - Practical Applications:
    -------------------------

        1. Toggle Bits: XOR can be used to toggle specific bits in a number.
        2. Checksum Calculation: XOR is used in algorithms to compute checksums for error detection.
        3. Encryption/Decryption: XOR is used in simple encryption algorithms where the same key is used to encrypt and
            decrypt data.

    - Conclusion:
    -------------

        The bitwise XOR operator in Java is a powerful tool for bit-level manipulation, enabling efficient and concise
            operations that are fundamental in many areas of programming and computer science.

- Bitwise XOR Example LeetCode Question: 1835. Find XOR Sum of All Pairs Bitwise AND
====================================================================================

    To solve the problem efficiently, let's break down the operations and utilize properties of the XOR and AND bitwise
    operations to reduce the computational complexity.

    * Problem Explanation:
    ----------------------

    Given two arrays `arr1` and `arr2`, we need to consider every possible pair `(i, j)` where `0 <= i < arr1.length`
    and `0 <= j < arr2.length`. For each pair, we calculate `arr1[i] AND arr2[j]`, and then we need to find the XOR sum
    of all these results.

    * Observations:
    ---------------

        1. AND and XOR properties:
           - XOR is both commutative and associative, which means the order of operations does not matter.
           - AND operation is distributive over XOR.

        2. Decomposing the problem:
           - Instead of calculating every `arr1[i] AND arr2[j]` and then taking the XOR, we can leverage the distributive
           property of the AND and XOR operations.

    * Efficient Calculation:
    ------------------------

    Let's consider how the bitwise operations interact:

    For any bit position ( k ):

        - For each number in `arr1`, determine how many numbers in `arr2` have the ( k )-th bit set and how many do not.
        - The XOR sum for a bit position ( k ) is determined by whether the number of set bits in `arr1` and `arr2` at
            position ( k ) are odd or even.

    If we denote:

        - `count1_k` as the number of elements in `arr1` where the ( k )-th bit is set.
        - `count2_k` as the number of elements in `arr2` where the ( k )-th bit is set.

    The contribution to the XOR sum from the \( k \)-th bit is significant only if `count1_k * count2_k` is odd.
    This is because an even number of `1` bits in a position will cancel out in XOR, whereas an odd number will result in a `1`.

    * Implementation:
    -----------------

    Let's implement this idea in Java:

        public class Solution {
            public int getXORSum(int[] arr1, int[] arr2) {
                int xor1 = 0, xor2 = 0;

                // Compute the XOR of all elements in arr1
                for (int num : arr1) {
                    xor1 ^= num;
                }

                // Compute the XOR of all elements in arr2
                for (int num : arr2) {
                    xor2 ^= num;
                }

                // The result is the AND of the two XORs
                return xor1 & xor2;
            }
        }

    * Explanation:
    --------------

        1. Compute `xor1`: This is the XOR of all elements in `arr1`.
        2. Compute `xor2`: This is the XOR of all elements in `arr2`.
        3. Result: The XOR sum of all `arr1[i] AND arr2[j]` pairs is equivalent to `(xor1 & xor2)`.

    This approach ensures that we compute the required XOR sum in O(n + m) time complexity, where ( n ) and ( m ) are the
    lengths of `arr1` and `arr2`, respectively. This is efficient and avoids the need to explicitly compute and store all
    possible pairs.