异或两个unsigned char数组的高效实现：能否突破O(n)复杂度？

首先明确：不存在复杂度优于O(n)的方法。因为异或操作需要处理数组中的每一个字节——每个输出字节都完全依赖对应位置的两个输入字节，这是问题的固有属性，所以理论时间复杂度的下限就是O(n)，无法突破。

不过你可以通过以下方法提升实际运行效率（复杂度仍为O(n)，但常数项更小），替代逐字节循环：

1. 按更大的数据类型批量处理 #

利用CPU的字长优势，将数组转换为更大的整数类型（比如uint64_t）进行批量异或。对于你这个64字节的固定长度数组，刚好可以拆分为8个uint64_t元素，循环次数从64次降到8次：

#include <stdint.h>

unsigned char a1[64];
unsigned char a2[64];
unsigned char result[64];

// 栈上固定大小数组通常会被编译器自动对齐，满足uint64_t的8字节对齐要求
uint64_t *src1 = (uint64_t *)a1;
uint64_t *src2 = (uint64_t *)a2;
uint64_t *dst = (uint64_t *)result;

for (int i = 0; i < 8; i++) {
    dst[i] = src1[i] ^ src2[i];
}

注意：如果是堆分配的数组，需要用aligned_alloc等函数确保对齐，否则强制类型转换可能导致未定义行为。

2. 依赖编译器自动优化 #

现代编译器（GCC、Clang、MSVC等）在开启优化选项（如-O2、-O3）时，会自动将逐字节的异或循环优化为批量操作，甚至生成SIMD指令。比如你原本的逐字节循环，在-O3优化下，编译器会自动将其转换为更高效的批量异或代码，不需要手动修改。

建议先尝试开启编译器优化，很多时候这就足够获得最优性能。

3. 手动使用SIMD指令 #

如果需要极致性能，可以直接使用CPU的SIMD指令集（如SSE、AVX），一次处理16/32字节的数据：

SSE示例（一次处理16字节） #

#include <emmintrin.h>

unsigned char a1[64];
unsigned char a2[64];
unsigned char result[64];

__m128i *src1 = (__m128i *)a1;
__m128i *src2 = (__m128i *)a2;
__m128i *dst = (__m128i *)result;

// 64字节 = 4组16字节
for (int i = 0; i < 4; i++) {
    dst[i] = _mm_xor_si128(src1[i], src2[i]);
}

AVX示例（一次处理32字节） #

#include <immintrin.h>

unsigned char a1[64];
unsigned char a2[64];
unsigned char result[64];

__m256i *src1 = (__m256i *)a1;
__m256i *src2 = (__m256i *)a2;
__m256i *dst = (__m256i *)result;

// 64字节 = 2组32字节
for (int i = 0; i < 2; i++) {
    dst[i] = _mm256_xor_si256(src1[i], src2[i]);
}

这种方法的缺点是和CPU架构强相关，移植性较差，但在特定平台上能获得最大的性能提升。

内容的提问来源于stack exchange，提问作者GARcher