Java - detailed explanation of the use of XOR ^


Follow the wechat official account: CodingTechWork to learn and make progress together.

introduction

It's easier to remember the usage of this operator than the one we don't see in the following code.

introduce

concept

XOR is also called semi addition, binary addition without carry. We know that in binary, 1 means true and 0 means false. The XOR algorithm is: the same is 0 and the difference is 1. We usually use ⊕ or ^ to represent the XOR operator. We are still used to using ^ in our code.

operation

Same as 0

0 ^ 0 = 0
1 ^ 1 = 0

Difference is 1

1 ^ 0 = 1
0 ^ 1 = 1

characteristic

  1. A number is XOR with itself, and the result is always 0
    a ^ a = 0
  2. If a number is exclusive or with 0, the result is always itself
    a ^ 0 = a
  3. Exchangeability
    a ^ b = b ^ a
  4. Associativity
    (a ^ b) ^ c = a ^ (b ^ c)

application

compression algorithm

   apply XOR in the compression algorithm to remove redundant data.

encryption algorithm

Suppose key is the key, clear_text is clear text, and ciphertext ciphertext is obtained by XOR.

ciphertext = clear_text ^ key

To decrypt, you can also do it through XOR

clear_text = ciphertext ^ key
# deduction:
clear_text = ciphertext ^ key
                = clear_text ^ key ^ key
                = clear_text ^ (key ^ key)     #Associativity, self exclusive or is 0
                = clear_text ^ 0               #And 0 XOR properties
                = clear_text

Backup files

Suppose there is a file_1 and file_2 two files need to be backed up, which can be backed up through XOR.

back_file = file_1 ^ file_2

As long as the source file is not damaged at the same time, it can be restored.

# Restore file_ one
file_1 = back_file ^ file_2
          = file_1 ^ file_2 ^ file_2
          = file_1 ^ (file_2 ^ file_2)       #Associativity, self exclusive or is 0
          = file_1 ^ 0                       #And 0 XOR properties
          = file_1 
          
# Restore file_ two
file_2 = back_file ^ file_1
         = file_1 ^ file_2 ^ file_1
         = file_1 ^ file_1 ^ file_2    #Commutativity, self exclusive or is 0
         = 0 ^ file_2                  #And 0 XOR properties
         = file_2

Judge data similarities and differences

# a and b are the same
(a ^ b) == 0

# a and b are different
(a ^ b) != 0

  now think about giving you two almost identical fault finding dot charts (the one with dense phobia). How to find fault? You can use XOR for de duplication, and the rest is different data.

Exchange number

Exchange number code of temporary variable originally required

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

Interchange number code using XOR without temporary variables

    private static void swap(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

Is it a little windy? Let's deduce

//Suppose arr[i] = a, arr[j]=b
1. arr[i] = arr[i] ^ arr[j]
       = a ^ b
 here arr[i] = a ^ b, and arr[j] = b unchanged.
2. arr[j] = arr[i] ^ arr[j]
          = a ^ b ^ b
          = a ^ (b ^ b)
          = a ^ 0
          = a
 here arr[i] = a ^ b Unchanged, and arr[j] = a. 
3. arr[i] = arr[i] ^ arr[j]
          = a ^ b ^ a
          = a ^ a ^ b
          = 0 ^ b
          = b
 here arr[i] = b, arr[j] = a,Swapped positions

Algorithm application: 136. Figures that appear only once

Given a non empty array of integers, each element appears twice except that one element appears only once. Find the element that appears only once.

explain:

Your algorithm should have linear time complexity. Can you do it without using extra space?

Example 1:

input: [2,2,1]
output: 1
 Example 2:

input: [4,1,2,1,2]
output: 4

For this problem, we can use the following two features of XOR to solve it:

  1. A number is XOR with itself, and the result is always 0
  2. If a number is exclusive or with 0, the result is always itself
package com.test.selfcoding.algorithm;

/**
 * @ClassNAME SingleNumber
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 17:01
 * @Version 1.0
 */
public class SingleNumber {

    public static int singleNumber(int[] nums) {
        int ans = nums[0];
        for (int i = 1; i < nums.length; i++) {
            //Use XOR ^ operation
            //1. A number is XOR with itself, and the result is always 0
            //2. If a number is exclusive or with 0, the result is always itself
            ans = ans ^ nums[i];
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] nums = {4,1,2,1,2};
        System.out.println(singleNumber(nums));   //Result: 4
    }

}

Algorithm application: 389. Find a different

package com.test.selfcoding.algorithm;

/**
 * @ClassNAME FindTheDifference
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 17:25
 * @Version 1.0
 *
 */
public class FindTheDifference {
    /**
     * Use XOR
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifferenceWithXOR(String s, String t) {
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            ans ^= s.charAt(i);
        }
        // At this point, ans splices all the characters in the s string
        for (int j = 0; j < t.length(); j++) {
            ans ^=  t.charAt(j);
        }

        return (char)ans;
    }

    /**
     * Using bit counting
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifferenceWithCount(String s, String t) {
        // 26 letter size array
        int[] letter = new int[26];

        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            //Value corresponding to character position + 1
            letter[sChar - 'a']++;
        }

        for (int j = 0; j < t.length(); j++) {
            char tChar = t.charAt(j);
            //Value corresponding to character position - 1
            letter[tChar - 'a']--;
            //If a negative number is found, it is different
            if (letter[tChar - 'a'] < 0) {
                return tChar;
            }
        }

        return ' ';
    }

    /**
     * Calculation using ASCII code
     * @param s
     * @param t
     * @return
     */
    public static char findTheDifferenceWithASCII(String s, String t) {
        //Sum the ASCII code values of each character in the strings s and t to obtain ASCII and ASCII
        int asciiS = 0, asciiT = 0;
        for (int i = 0; i < s.length(); i++) {
            asciiS += s.charAt(i);
        }

        for (int j = 0; j < t.length(); j++) {
            asciiT += t.charAt(j);
        }
        return (char) (asciiT - asciiS);
    }

    public static void main(String[] args) {
        String s = "abcdef";
        String t = "abcdfeg";
        System.out.println(findTheDifferenceWithXOR(s, t));
        System.out.println(findTheDifferenceWithCount(s, t));
        System.out.println(findTheDifferenceWithASCII(s, t)); //Result: g
    }

}

Algorithm application: find two odd numbers

package com.test.selfcoding.algorithm;

import java.util.Arrays;

/**
 * @ClassNAME Find2OddNumbers
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 21:51
 * @Version 1.0
 */
public class Find2OddNumbers {

    //Find only two odd numbers in an array. Suppose a,b,c,c,d,d, then a and b are the results to be found
    public static int[] find2OddNumbers(int[] arr) {
        //eor = a ^ b
        int eor = 0;
        for (int cur : arr) {
            eor ^= cur;
        }
        //If res1 = b, res2 = eor ^ res1
        //Find the rightmost 1 of binary, take non, add 1, and then compare with itself
        // eor =   111010010
        // ~eor =  000101101
        //~eor+1 = 000101110
        //eor & (~eor+1) = 000000010
        int right = eor & (~eor + 1);
        int onlyOne = 0;
        for (int cur : arr) {
            //Take half. If the binary bit is 0 or 1, it is half
            if ((cur & right) == 1) {
                onlyOne ^= cur;
            }
        }

        return new int[] {onlyOne, eor ^ onlyOne} ;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {1, 2, 3, 4, 2, 1, 3, 5, 4, 6, 7, 7};
        System.out.println(Arrays.toString(find2OddNumbers(arr))); //Results: [5,6]
    }

}

summary

   I didn't notice this operator before, and I saw it in a video, so I learned and summarized it and found that this small operator is widely used and interesting.

reference resources
leetcode official website
Baidu Encyclopedia

Tags: Java programming language

Posted by kcarroll on Sun, 22 May 2022 02:20:39 +0300