Hugh

V1

2022/05/21阅读:30主题:橙心

Java—异或运算^的使用详解

技术公众号:后端技术解忧铺 关注微信公众号:CodingTechWork,一起学习进步。

引言

  在代码中,我们经常看到一个运算符^,这个运算符叫做异或,相比较于与&和或|这些运算符更不容易记住,下面我们一起学习这个运算符的用法。

介绍

概念

  异或也叫半加运算,不带进位的二进制加法。我们知道,在二进制中1表示真,0表示假。异或的运算法则即为:相同为0,不同为1。一般用或者^来表示异或运算符,我们在代码中还是习惯用^

运算

同为0

0 ^ 0 = 0
1 ^ 1 = 0

异为1

1 ^ 0 = 1
0 ^ 1 = 1

特性

  1. 一个数与本身异或,结果总是为 0 a ^ a = 0
  2. 一个数与0异或,结果总是其自身 a ^ 0 = a
  3. 交换性 a ^ b = b ^ a
  4. 结合性 (a ^ b) ^ c = a ^ (b ^ c)

应用

压缩算法

  在压缩算法中应用异或去除冗余相同的数据。

加密算法

假设key为密钥,clear_text为明文,使用异或得到密文ciphertext

ciphertext = clear_text ^ key

若要解密,也可通过异或去啊哦做

clear_text = ciphertext ^ key
# 推导:
clear_text = ciphertext ^ key
                = clear_text ^ key ^ key
                = clear_text ^ (key ^ key)     #结合性、自身异或为0特性
                = clear_text ^ 0               #和0异或特性
                = clear_text

备份文件

假设有file_1file_2两个文件需要备份,可以通过异或进行备份。

back_file = file_1 ^ file_2

源文件只要不同时损坏,都可以还原。

# 还原file_1
file_1 = back_file ^ file_2
          = file_1 ^ file_2 ^ file_2
          = file_1 ^ (file_2 ^ file_2)       #结合性、自身异或为0特性
          = file_1 ^ 0                       #和0异或特性
          = file_1 
          
# 还原file_2
file_2 = back_file ^ file_1
         = file_1 ^ file_2 ^ file_1
         = file_1 ^ file_1 ^ file_2    #交换性、自身异或为0特性
         = 0 ^ file_2                  #和0异或特性
         = file_2

判断数据异同

# a和b相同
(a ^ b) == 0

# a和b不同
(a ^ b) != 0

  现在想想给你两个几乎一摸一样的找茬茬点状图(密集恐惧症的那种),怎么找茬?就可以使用异或进行去重,剩下的就是不一样的数据。

交换数

原本需要临时变量的交换数代码

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

使用异或无需临时变量的交换数代码

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

是不是有点绕?我们推导一下

//假设arr[i] = a, arr[j]=b
1. arr[i] = arr[i] ^ arr[j]
       = a ^ b
此时arr[i] = a ^ b, 而arr[j] = b不变。
2. arr[j] = arr[i] ^ arr[j]
          = a ^ b ^ b
          = a ^ (b ^ b)
          = a ^ 0
          = a
此时arr[i] = a ^ b不变,而arr[j] = a。
3. arr[i] = arr[i] ^ arr[j]
          = a ^ b ^ a
          = a ^ a ^ b
          = 0 ^ b
          = b
此时arr[i] = b, arr[j] = a,交换了位置

算法应用:136. 只出现一次的数字

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

说明:

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:

输入: [2,2,1]
输出: 1
示例 2:

输入: [4,1,2,1,2]
输出: 4

这种题目,我们就可以使用异或的如下两个特性进行求解:

  1. 一个数与本身异或,结果总是为 0
  2. 一个数与0异或,结果总是其自身
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++) {
            //使用异或^运算
            //1. 一个数与本身异或,结果总是为0
            //2. 一个数与0异或,结果总是其自身
            ans = ans ^ nums[i];
        }

        return ans;
    }

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

}

算法应用:389. 找不同

package com.test.selfcoding.algorithm;

/**
 * @ClassNAME FindTheDifference
 * @Description TODO
 * @Author Andya
 * @Date 2022/5/21 17:25
 * @Version 1.0
 *
 */

public class FindTheDifference {
    /**
     * 使用异或
     * @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);
        }
        // 此时ans将s字符串中的所有字符拼接起来了
        for (int j = 0; j < t.length(); j++) {
            ans ^=  t.charAt(j);
        }

        return (char)ans;
    }

    /**
     * 使用位计数法
     * @param s
     * @param t
     * @return
     */

    public static char findTheDifferenceWithCount(String s, String t) {
        // 26个字母大小的数组
        int[] letter = new int[26];

        for (int i = 0; i < s.length(); i++) {
            char sChar = s.charAt(i);
            //对应字符位置的数值+1
            letter[sChar - 'a']++;
        }

        for (int j = 0; j < t.length(); j++) {
            char tChar = t.charAt(j);
            //对应字符位置的数值-1
            letter[tChar - 'a']--;
            //找到负数的则为不同
            if (letter[tChar - 'a'] < 0) {
                return tChar;
            }
        }

        return ' ';
    }

    /**
     * 使用ASCII码计算
     * @param s
     * @param t
     * @return
     */

    public static char findTheDifferenceWithASCII(String s, String t) {
        //将字符串s和t中每个字符的ASCII码的值求和,得到asciiS和asciiT
        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)); //结果:g
    }

}

总结

  这个运算符之前没有注意到,也是在一个视频中无意看到,于是便学习总结出来,发现这个小小的运算符应用广泛且有趣。

参考 leetcode官网 百度百科

分类:

后端

标签:

Java

作者介绍

Hugh
V1