最长异或公共子段 题解

题目描述

给定两个不同的非负整数 。定义两条无限序列：

求最长公共子段长度，即最大正整数 ，存在 满足：

核心结论

答案： 最长公共子段长度 = ，其中 是 和 从最低位开始第一个不同位的位置。

算法： 使用位运算技巧 (x^y) & (-(x^y)) 直接得到答案。

标程实现

方法一：逐位检查

#include <iostream>
using namespace std;

int main() {
    int _;
    cin >> _;
    while (_--) {
        int x, y, i;
        cin >> x >> y;
        if (!min(x, y)) {  // 特判：如果 x 或 y 为 0
            cout << 1 << '\n';
            continue;
        }
        for (i = 0; 1; i++) {
            if ((x >> i & 1) ^ (y >> i & 1)) break;  // 找到第一个不同的位
        }
        cout << (1 << i) << '\n';  // 答案就是 2^i
    }
}

方法二：位运算技巧（推荐）

#include <iostream>
using namespace std;

int main() {
    int _;
    cin >> _;
    while (_--) {
        int x, y;
        cin >> x >> y;
        cout << ((x ^ y) & (-(x ^ y))) << '\n';
    }
}

算法解释

位运算技巧解释：

• x ^ y：得到 和 的异或结果
• -(x ^ y)：利用二进制补码的性质，得到该数的负数（二进制补码）
• (x ^ y) & (-(x ^ y))：提取最低位 1 对应的值，这正是我们要求的

详细解释： 设 z = x ^ y，则 -z 在二进制补码中等于 ~z + 1。

• 如果 z 的最低位 1 在第 i 位，那么 z 可以表示为 z = ...100...0（第 i 位为 1，更低位都为 0）
• ~z 的最低位 0 在第 i 位，可以表示为 ~z = ...011...1（第 i 位为 0，更低位都为 1）
• ~z + 1 会将第 i 位及更高位保持不变，第 i 位变为 1，更低位变为 0
• 因此 -z 的形式为 ...100...0，与 z 在第 i 位都为 1，其他位不同
• z & (-z) 的结果就是第 i 位为 1，其他位都为 0，即 2^i

示例分析

以 为例：

• 的二进制：
• 的二进制：
• 异或结果：
• 从右往左第一个不同的位是第 位（从 开始计数）
• 答案：

位运算技巧验证：

• x ^ y = 12 ^ 4 = 8（二进制：）
• -(x ^ y) = -8（二进制补码：，32位）
• (x ^ y) & (-(x ^ y)) = 8 & (-8) = 8 & 11111111111111111111111111111000 = 1000 = 8

以 为例：

• 的二进制：
• 的二进制：
• 异或结果：
• (x ^ y) & (-(x ^ y)) = 4 & (-4) = 4 & 11111111111111111111111111111100 = 100 = 4

复杂度分析

• 时间复杂度： 或 （取决于实现）
• 空间复杂度：

数学证明

核心观察

对于序列 和 ，我们需要找到最长的公共子段。

关键观察：两个序列的公共子段长度等于 和 从最低位开始连续相同位的个数对应的 的幂次。

证明

定义： 设 和 从第 位开始不同，即前 位相同，第 位不同。

引理 1： 对于序列 和 ， 和 的低 位相同。

证明： 对于 ，由于 ，有：

引理 2： 如果 和 的低 位相同，那么 和 的低 位 和 的低 位。

证明： 由引理 1， 和 的低 位只依赖于 的低 位。

主要定理： 最长公共子段长度为 。

证明：

存在性： 考虑 的所有整数，它们的低 位各不相同。由引理 1， 和 的低 位相同；由引理 2，不同 值对应的低 位不同。因此序列 和 的低 位一一对应相同。

唯一性： 假设存在长度 的公共子段。由鸽笼原理，必然存在两个位置的低 位相同。设这两个位置为 和 ，由引理 2， 和 的低 位 和 的低 位。但 且低 位相同，意味着 和 在第 位或更高位不同，因此 或 ，矛盾。

结论： 最长公共子段长度恰好为 。