题目链接

最长异或公共子段

题目描述

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

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

解题思路

这是一个关于位运算性质的深刻问题。要找到最长的公共子段，我们需要找到最大的 ，使得存在起始下标 和 ，对于所有 ，都满足 。

这个方程看起来很复杂，因为它混合了加法和异或。解决问题的关键在于找到一个巧妙的构造，简化这个方程。

令 。

我们尝试构造一种特定的对应关系，使得方程在 时成立。一个自然的选择是令 。这样，当 时：

等式成立。

现在，我们需要找到最大的 ，使得对于一个合适的 ，以下等式在 的范围内恒成立：

令 。因为 可以是任意非负整数，所以 可以是任何 的整数。我们的方程变为：

这个方程揭示了一个位运算的重要性质。可以证明，如果 是 的倍数，其中 (ctz 表示二进制末尾零的个数)，那么上述等式对所有 均成立。我们可以自由选择 来调整 ，因此总可以找到一个满足条件的 。

因此，最长公共子段的长度 就是 ，其中 。

这个值可以通过位运算 (x^y) & -(x^y) 来高效计算，这个表达式可以分离出 x^y 的最低有效位（lowbit），其结果恰好是 。

代码

#include <iostream>

using namespace std;

void solve() {
    long long x, y;
    cin >> x >> y;
    long long z = x ^ y;
    cout << (z & -z) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            long x = sc.nextLong();
            long y = sc.nextLong();
            long z = x ^ y;
            // z & -z isolates the lowest set bit, which is equivalent to 2^ctz(z)
            System.out.println(z & -z);
        }
    }
}

def solve():
    x, y = map(int, input().split())
    z = x ^ y
    # z & -z isolates the lowest set bit (lowbit)
    print(z & -z)

t = int(input())
for _ in range(t):
    solve()

算法及复杂度

  • 算法：位运算
  • 时间复杂度：。每次查询只涉及几次位运算操作。
  • 空间复杂度：。只使用了常数个变量。