【算法讲解】杂项算法——异或哈希(xor-hashing)-程序员宅基地

前言

异或哈希是个很神奇的算法，利用了异或操作的特殊性和哈希降低冲突的原理，可以用于快速找到一个组合是否出现、序列中的数是否出现了k次

异或(xor)

异或是计算机语言中的一个运算符，代码中用^表示，数学符号用 $\oplus$ 表示，含义是对数字的二进制表示按位相加并对2取余，举个例子 $3\oplus5=(011)_2\oplus (101)_2=(110)_2=7$
异或运算符合交换律（类似加法交换律、乘法交换律），既 $A\oplus B = B \oplus A$
异或运算相比其他运算，有一个很重要的独有特性：
$A\oplus 0=A\\ A\oplus A=0$
根据上述这个特性，我们可以推演得到重要特性：当一个数进行偶数次异或运算后，其值为0，当一个数进行奇数次操作后，其结果为自身

我们可以根据这个特性快速解决这个题目 leetcode: 一个数组中除了一个元素外其他元素都出现了两次(偶数次)，找出这个元素

int xor = 0;
for (auto item: a) {
    
  xor ^= item;
}
cout << xor << endl;

哈希(hashing)

哈希（中文称之为散列）算法是一种用于快速定位资源的算法。
对于键值对（key，value），如果key是数字，我们可以直接通过数组的下标做key来定位数字所对应的value
但如果value是很大的数字(没办法开下那么大的数组)，或者是string类型，亦或是其他乱七八糟的类型的组合，我们就没办法用下标来定位了
这时候就需要用将key哈希成一个数字

在c++中，可以直接用 unordered_map 作为 hash 表，但是对于复杂的元素，需要重载 == 运算符以及 hash 函数才行。对于更复杂的数组，就不太适用了

应用

分别介绍完异或和哈希的背景后，我们来看看两者结合有哪些应用

组合问题

判断一个序列是否是另一个序列的排列组合

先来看一道题：

给一个长度为 $n$ 的数组 $a$ ，找到所有的连续子序列 $[l, r]$ 满足：正好包含 $1$ 到 $r - l + 1$ （既 $1$ 到 $r - l + 1$ 的排列组合）

最朴素的做法：

从 $1$ 到 $n$ 遍历 $l$ ，从 $i$ 到 $n$ 遍历 $r$ ，判断 $[l, r]$ 是否包含 $1$ 到 $r - l + 1$

这种做法的复杂度至少是 $O(n^3)$

问题抽象

上述算法中相对复杂的步骤为：判断 $[l, r]$ 是否包含 $1$ 到 $r - l + 1$
既判断 $[a_l, a_l+1,\cdots,a_r]$ 是否是 $[1,2,\cdots, r-l+1]$ 的排列组合
既问题转化成：判断两个数组的排列组合是否相同。

用异或求解

根据异或的交换律可知：一个数组的任何排列组合，它的异或结果都相同
既：
$\begin{aligned} 1\oplus 2&=2\oplus 1\\ 1\oplus 2\oplus 3&=1\oplus3\oplus2\\ &=2\oplus1\oplus3\\ &=2\oplus3\oplus1\\ &=3\oplus1\oplus2\\ &=3\oplus2\oplus1 \end{aligned}$
看起来好像可以根据这个来判断两个数组是否是同一个排列组合
其实有很多其他的组合异或后也是相同的结果，比如 $1\oplus2=5\oplus6$ ， $1\oplus2\oplus3=4\oplus8\oplus12$
本质原因是组合数一共有 $\frac{n\cdot(n-1)}{2}$ ，而异或的结果集 $\approx n$ （实际上是比 $n$ 大的最小 $2^k$ ），所以一定会发生冲突
有什么办法可以解决呢？

用哈希降低冲突

为了解决冲突我们可以利用哈希将异或的结果集扩大：将数字 $i$ 哈希成 64 位无符号整数
那么结果集就扩大为了 $2^{64}$ ，和 $\frac{n\cdot(n-1)}{2}$ 相比，冲突的概率就是 $\frac{n\cdot(n-1)}{2^{65}}$ ，微乎其微

代码

我们将 $i$ 哈希成 64 位无符号整数，记为 $code_i$ ，后续的异或操作就不是直接用 $i$ 来运算了，而是用 $code_i$ 代替
$code_1$ 到 $code_n$ 的异或结果记为 $XOR\_N_n$ ，可推得 $XOR\_N_n=XOR\_N_{n-1}\oplus code_n$
$code_{a_1}$ 到 $code_{a_n}$ 的异或结果记为 $XOR_n$ ，可推得 $XOR_n=XOR_{n-1}\oplus code_{a_n}$
连续子序列 $[l, r]$ 的结果就是 $XOR_r\oplus XOR_{l-1}$ ，如果他的结果等于 $XOR\_N_{r-l+1}$ ，那么就是符合条件的序列

mt19937_64 rnd(time(0));
typedef uint64_t hash_t;

const int MAXN = 3e5+1;
hash_t code[MAXN];
hash_t xorn[MAXN];
hash_t Xor[MAXN];
int a[MAXN];
int n;
void init() {
    
  for (int i = 1; i <= n; i ++) {
    
    code[i] = rnd();
    xorn[i] = xorn[i-1] ^ code[i];
  }
}
int solve() {
    
  init();
  for (int i = 1; i <= n; i ++) {
    
    xor[i] = xor[i - 1] ^ code[ a[i] ];
  }
  int res = 0;
  for (int l = 1; l <= n; l ++) {
    
    for (int r = l; r <= n; r ++) {
    
      if (xor[r] ^ xor[l - 1] = xorn[r - l + 1]) {
    
        res++;
      }
    }
  }
  return res;
}

自此，将算法的复杂度从 $O(n^3)$ 优化成了 $O(n^2)$ ，至于如何优化到 $O (n)$ ，不是本篇介绍的主要内容，大家可以自行思考

上面代码大家会看到一个很神奇的内容 mt19937_64 rnd(time(0))，这是 c++ 自带的梅森旋转（Mersenne Twister）伪随机数，可以随机生成 64 位整数，随机的内容直到 $2^{19937}$ 次调用后才会出现重复，具体的原理这里不过多介绍。把他当成一个工具使用就行。

思考

在用异或求解章节我们利用了异或的交换律特性，那是否用也符合交换律的加法运算也能达到相同的效果呢？
答案是：yes

异或的本质是对 2 进制每位进行不进位的加法
加法的本质是对 2 进制每位进行进位的加法

而c++的语言特性中，无符号整数对于溢出的部分会自动截断，所以效果是相同的
只是在求区间结果的时候需要将xor[r] ^ xor[l - 1]换成xor[r] - xor[l - 1]

那么乘法呢？
乘法其实也是类似的道理，但是转化为对 $2^{64}$ 去模除法，这个很麻烦，不利于模拟。而且虽然没有证明，但我觉得乘法的冲突概率要比异或高。所以不会建议使用乘法

而计算机对位运算的处理效率要比其他运算高很多，并且不用像加法一样额外考虑减法，所以这类题目我们都用异或来进行计算。

出现次数问题

判断一个序列内的元素是否出现偶数( $k$ 的倍数)次

在开篇我们提到一个用异或来解决的经典题目：快速找到一个数组中只出现1次（其他数都出现偶数次）的数
利用的就是 $A\oplus A=0$ 的特性，我们可以快速判断一个数组(区间)的元素是否都出现了偶数次
~~直接异或结果为0就行了~~
不对！！
因为 $4\oplus 8 \oplus 12$ 也等于0，所以我们需要将数字进行hash处理，降低冲突概率，再用异或操作

现在我们将问题升级一下：

给一个长度为 $n$ 的数组 $a$ ，找到所有的连续子序列 $[l, r]$ 满足：所有 $a_i, i\in[l,r]$ 出现的次数都是 3 次倍数

k 进制

之前提到，二进制的异或的本质是对每一位进行不进位的加法，也就是每一位相加对2取模，既：
$\begin{aligned} 0\oplus0&=(0+0)\%2&=0\\ 1\oplus0&=(1+0)\%2&=1\\ 0\oplus1&=(0+1)\%2&=1\\ 1\oplus1&=(1+1)\%2&=0\\ \end{aligned}$
假设有这么一个运算符 $\textcircled{3}$ ，可以让 $A\textcircled{3}A\textcircled{3}A=0$ ，那么问题就解决了，既：
$\begin{aligned} 0\textcircled{3}0&=(0+0)\%3&=0\\ 0\textcircled{3}1&=(0+1)\%3&=1\\ 0\textcircled{3}2&=(0+2)\%3&=2\\ 1\textcircled{3}2&=(1+2)\%3&=0\\ \end{aligned}$
这就是 $3$ 进制，也可以推演至 $k$ 进制。

// 特别注意，随机数 a,b 上限要取 uint64/k，避免溢出
// 只有2进制的溢出会自动处理，因为就少了一位，而 k 进制溢出就会出错
uint64_t xork(uint64_t a, uint64_t b, int k) {
    
  vector<int> vec;
  while (a || b) {
    
    vec.push_back((a + b) % k);
    a /= k;
    b /= k;
  }
  uint64_t res = 0;
  uint64_t p = 1;
  for (auto x: vec) {
    
    res += p * x;
    p *= k;
  }
  return res;
}

但很不幸， $k$ 进制虽然能解决问题，但是会额外增加 $log_3C$ 的常数 $\approx 40$ 。
上文有提到，加法配合减法可以达到异或类似的效果，所以我们对于这类问题可以取个巧，将第 $k$ 的倍数次出现的数字设置为 $k - 1$ 倍的负数 $-(k-1)\cdot a_i$ ，那么只要一个区间内出现的次数是 $k$ 的倍数，那么他们的和一定是0
对于 $k = 2$ ，设置为 $a_i$ ，对于 $k = 3$ ，设置为 $-2\cdot a_i$
所以我们只需要判断区间和为0，那么这个区间的数字出现的次数一定是 $k$ 的倍数
注意：为了降低冲突的概率，我们需要将元素映射为64位无符号整数

思考
这个做法我们只将复杂度从 $O(n^3)$ 降低为 $O(n^2)$ ，如何降低为 $O (n)$ 大家可以自行思考
如果要求区间出现的次数一定是 $k$ 次，而不是 $k$ 的倍数，又应该如何解呢？
对于这两个思考，可以在 CF 1418 G Three Occurrences 这道题中进行验证

$x^2$ 问题

判断一个序列的乘积是否是 $x^2$ ( $x$ 为某个整数)

通常题目不会直观让你判断次数是否偶数次，会进行一些伪装，而 $x^2$ 就是一个非常常见的伪装
我们将一个 $a_i$ 进行质因数分解可得 $p_1^{k_{i_1}}p_2^{k_{i_2}}\cdots p_m^{k_{i_m}}$ ，其中 $p_i$ 都是质数， $k_i$ 是对应的指数。
那么所有 $a_i$ 的乘积就为 $\prod_{i=1}^{n} a_i=p_1^{\sum_{i=1}^n k_{i_1}}p_2^{\sum_{i=1}^n k_{i_2}}\cdots p_m^{\sum_{i=1}^n k_{i_m}}$
(为了简化表达，我们将 $\sum_{i=1}^n k_{i_m}$ 记为 $K_m$ )
如果： $p_1^{K_1}p_2^{K_2}\cdots p_n^{K_n}=x^2$
那么： $(p_1^{\frac{K_1}{2}}p_2^{\frac{K_2}{2}}\cdots p_n^{\frac{K_n}{2}})^2=x^2$
可以推得：所有的 $K_i$ 都是偶数， $\prod_{i=1}^{n} a_i$ 才可能是某个整数的平方 $x^2$
所以问题就转化成了质因数的个数是否是偶数次
这就是上述已经解决的问题

练习

题目	说明
AtCoder: 250 E Prefix Equality	组合问题
CF: 1175 F The Number of Subpermutations	组合问题
CF: 869 E The Untended Antiquity	组合问题
洛谷: P3792 由乃与大母神原型和偶像崇拜	组合问题
CF: 1418 G Three Occurrences	出现次数问题
HackerRank: Number Game On A Tree	出现次数问题
CF: 1622 F Quadratic Set	$x^2$ 问题
CF: 895 C Square Subsets	$x^2$ 问题，不过不用 hash，因为组合数有限，不会冲突

参考

1. XOR Hashing [TUTORIAL]
2. 哈希算法学习笔记

本文链接：https://blog.csdn.net/notonlysuccess/article/details/130959107

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

环境变量配置错误的解决方法_proxmark3gui系统环境变量配置错误-程序员宅基地

文章浏览阅读3.2k次。Linux下环境变量配置错误导致系统命令不能使用的解决方案_proxmark3gui系统环境变量配置错误

Spring开发注解 @Resource与@Autowired用法区别_@autowired spring不同版本-程序员宅基地

文章浏览阅读780次。**spring中，@Resource和@Autowired都是做bean的注入时使用。使用过程中，有时候 @Resource 和 @Autowired可以替换使用；有时，则不可以。下面，根据自己的学习，整理下这两个注解使用中的共同点和不同点，及用法上的不同。共同点 @Resource和@Autowired都可以作为注入属性的修饰，在接口仅有单一实现类时，两个注解的修饰效果相同，可..._@autowired spring不同版本

实例分割论文阅读之：《Mask Transfiner for High-Quality Instance Segmentation》-程序员宅基地

文章浏览阅读1.4k次，点赞14次，收藏8次。两阶段和基于查询的实例分割方法取得了显著的效果。然而，它们的分段掩模仍然非常粗糙。在本文中，我们提出了一种高质量和高效的实例分割Mask Transfiner。我们的Mask Transfiner不是在规则的密集张量上操作，而是将图像区域分解并表示为四叉树。我们基于变压器的方法只处理检测到的容易出错的树节点，并并行地自我纠正它们的错误。虽然这些稀疏像素只占总数的一小部分，但它们对最终的掩模质量至关重要。这使得Mask Transfiner能够以较低的计算成本预测高度准确的实例掩码。_mask transfiner for high-quality instance segmentation

《现代永磁同步电机控制原理及MATLAB仿真》之三相电压源逆变器PWM技术学习_三次谐波注入spwm仿真-程序员宅基地

文章浏览阅读845次，点赞4次，收藏10次。对于三相逆变电路，其直流电压的利用率为0.866，为了提高直流电压的利用率，考虑在调制波信号中注入三相谐波分量，对调制波求导得到调制波的最大幅值，当注入的三次谐波的幅值为Vm1/6时，基于三次谐波注入的基波电压幅值增加了15.48%，提高了直流电压利用率，仿真建模如下。其中V0为零序分量，V0的取值范围在[-1-Vmin 1-Vmax]之间，其中Vmax=Max{Vam Vbm Vcm}，Vmin=Min{Vam Vbm Vcm}，常见的典型的零序信号有：均值零序信号、极值零序信号和交替零序信号。_三次谐波注入spwm仿真

建设可信赖、公平开放的HMS生态，华为与全球伙伴合作共赢_可信赖,生态-程序员宅基地

文章浏览阅读3.6k次。在9月10日东莞松山湖召开的2020年华为开发者大会上，华为表示将继续与全球合作伙伴、开发者携手，通过HMS生态提供的能力和服务，共同建设可信赖、公平开放的移动生态，为用户提供多元化的创新体验。华为全球生态发展部总裁汪严旻在大会上发表《新挑战、新机遇、新生态》主题演讲，并表示华为将以更加开放的姿态，拥抱全球的开发者和用户。HMS生态快速发展的驱动力：一年内为用户实现300万个 “心愿”自2019年华为开发者大会，华为投入3000名工程师，数百名技术人员进行HMS Core能力的开发以及开发者.._可信赖,生态

salt-and-pepper是什么-程序员宅基地

文章浏览阅读284次，点赞5次，收藏3次。椒盐噪声”（salt-and-pepper noise），也称为脉冲噪声，是一种在数字图像中常见的噪声类型。它主要表现为图像中随机分布的亮（白色）和暗（黑色）像素点，这些噪声点非常突兀，看起来类似于撒在图像上的盐和胡椒粒，因此得名。