从1994年微软面试题看SWAR：无SIMD时代的位运算优化艺术

1994 年，一个年轻的程序员走进微软面试间，迎接他的是四道编程题。其中第三道 ——CGA 洪水填充颜色检测 —— 被面试官称为 "让我们击败 Borland 性能" 的关键优化。这道题不仅考验了候选人的位运算功底，更揭示了 SIMD 指令出现之前，程序员如何在寄存器内实现 "单指令多数据" 的精妙技巧。

问题背景：4 色 CGA 的内存布局

在 1990 年代初的 PC 图形编程中，CGA（Color Graphics Adapter）的 4 色模式是常见配置。每个像素仅需 2 位即可表示 4 种颜色，而 x86 架构的最小可操作单位是 8 位字节。这意味着每个字节需要存储 4 个像素，采用 2 位 / 像素的紧凑打包方式。

洪水填充算法的核心步骤是：给定一个起始像素，找出所有与之颜色相同且连通的像素并填充新颜色。优化瓶颈在于如何快速判断 "一个字节（4 个像素）中是否包含目标颜色"。看似简单的问题暗藏陷阱 —— 必须确保不会误判跨像素边界的位组合。例如字节0b01100000虽然包含0b11模式，但这两个 1 分别属于像素 2 和像素 3 的边界，不能视为有效匹配。

朴素解法：逐像素检测的代价

面对这个问题，缺乏经验的程序员往往会写出直观的逐像素检测代码：

int ContainsColor_naive(uint8_t Pixels, uint8_t Color) {
    return ((Pixels & 3) == Color) |
           (((Pixels >> 2) & 3) == Color) |
           (((Pixels >> 4) & 3) == Color) |
           (((Pixels >> 6) & 3) == Color);
}

这段代码通过移位和掩码将每个像素隔离后单独比较。从指令周期看，在 8086 处理器上大约需要4 次比较、4 次 AND、3 次移位、3 次 OR，总计超过 20 个周期。更严重的是，这种写法暴露了程序员对位运算语义理解的表层化 —— 只知道 "机械地" 使用运算符，而未理解其 "语义" 层面的等价转换可能。

核心洞察：XOR 即 "不等于"

优化的关键在于一个常被忽视的事实：XOR（异或）本质上是按位的 "不等于"（!=）操作符。对比两者的真值表：XOR 在输入位不同时输出 1，而 "等于" 比较在输入位相同时输出 1—— 两者恰好互为补集。

利用这一洞察，我们可以将目标颜色预复制到字节的每个像素位置（如颜色 3 变为0b11111111），然后执行~(Pixels ^ Color)操作。结果字节中，1 表示对应位与目标颜色的对应位相等。

但这还不够。由于每个像素占 2 位，我们需要确保两个位都匹配才算颜色相等。解决方法是将高位右移 1 位与低位对齐，然后用 AND 操作检测双 1 情况。为避免移位时低位溢出到相邻像素，需先用掩码0b10101010清除所有像素的低位。

SWAR 优化：寄存器内的 SIMD

最终优化的代码简洁而优雅：

int ContainsColor_swar(uint8_t Pixels, uint8_t NotColor) {
    // NotColor = ~Color，预计算
    uint8_t Eq = Pixels ^ NotColor;           // 1 XOR：检测位相等
    uint8_t Mask = 0b10101010;
    return Eq & ((Eq & Mask) >> 1);           // 2 AND + 1 SHIFT + 1 AND
}

对应的 8086 汇编仅需 5 条指令、约13 个周期：

xor  al, cl      ; 3 cycles - Pixels ^ NotColor
mov  bl, al      ; 2 cycles - 保存Eq
and  al, dl      ; 3 cycles - Eq & Mask (dl=0xAA)
shr  al, 1       ; 2 cycles - 右移对齐
and  al, bl      ; 3 cycles - 最终检测

相比朴素解法的 20 + 周期，这是35% 的性能提升。更重要的是，这种写法体现了 SWAR（SIMD Within A Register）思想 —— 在没有专用 SIMD 指令的时代，通过巧妙的位运算在单个寄存器内并行处理多个数据元素。

工程权衡：查表法的空间换时间

当时还有另一个选择：256 字节的查找表配合XLAT指令。理论上单条指令 11 周期即可完成检测，但需要权衡256 字节内存的代价。在 1994 年的内存受限环境（尤其是嵌入式图形代码）中，这种空间换时间的策略往往不可接受。这提醒我们：最优解永远依赖于具体约束条件，而非纯粹的算法复杂度。

现代启示：从 SWAR 到 AVX-512

三十年后的今天，这个问题在现代处理器上有了更直接的解决方案。AVX-512 等 SIMD 指令集支持 8/16/32/64 位通道的并行比较，无需手动掩码和移位来防止通道间溢出。但 SWAR 思想并未过时 —— 在处理非标准位宽（如 2 位像素）或资源受限的嵌入式场景时，这些底层技巧依然有价值。

更重要的是，这道面试题传递的思维方式：深入理解操作符的语义本质（XOR 即不等于），善于利用预计算（NotColor 替代运行时 NOT），以及在寄存器层面思考数据并行。这些能力从 8086 时代到现代 GPU 编程始终适用。

可落地的检查清单

如果你在面试或实际工程中遇到类似问题，可按以下步骤思考：

1. 分析数据布局：确定位宽、对齐方式、是否有跨边界风险
2. 识别并行机会：能否在寄存器内同时处理多个数据元素？
3. 利用代数等价：XOR/NOT/AND 的组合能否简化比较逻辑？
4. 预计算权衡：哪些值可以预先计算并复用？内存是否允许查表？
5. 周期计数验证：对关键路径代码，手动估算指令周期数

从 1994 年的白板到今天的编译器优化，底层思维的价值从未衰减。理解机器如何工作，始终是写出高效代码的基石。

参考来源

• Casey Muratori, "The Four Programming Questions from My 1994 Microsoft Internship Interview", Computer Enhance, 2023
• "Color Graphics Adapter", Wikipedia, 技术规格与内存布局细节

systems