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
- A number is XOR with itself, and the result is always 0
a ^ a = 0 - If a number is exclusive or with 0, the result is always itself
a ^ 0 = a - Exchangeability
a ^ b = b ^ a - 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:
- A number is XOR with itself, and the result is always 0
- 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