布尔表达式树转最优位运算操作集的算法及实现方案咨询

一、单步位校验场景（仅含AND/字面量取反） #

当表达式可等价为「若干比特位的取值同时满足固定要求」时（即所有逻辑运算仅为AND连接的原始位/取反位，无OR运算），可直接转换为(input & mask) == test形式，转换步骤如下：

• 第一步：收集表达式中所有涉及的位标志，生成全量掩码full_mask，即所有涉及位的按位或结果
• 第二步：收集所有要求必须置1的位，生成校验值set_bits，即所有要求置1位的按位或结果
• 第三步：最终校验逻辑为(input & full_mask) == set_bits

示例对应转换：
表达式Apples && Pears && !Bananas的full_mask = Apples | Pears | Bananas，set_bits = Apples | Pears，最终校验逻辑与示例完全一致。

二、含OR运算的通用场景转换算法 #

当表达式存在OR嵌套无法用单步校验时，采用以下步骤得到最优位运算组合：

1. 先将AST转换为析取范式（DNF），即若干个AND子句通过OR连接的标准形式，例如示例表达式Apples && (Pears || Bananas)转DNF后为(Apples && Pears) || (Apples && Bananas)
2. 每个AND子句均可按第一部分的单步校验逻辑实现，得到一组(input & mask_i) == test_i的判断条件
3. 提取所有AND子句的公共约束做前置判断，减少重复运算：
   • 示例中两个AND子句的公共约束为Apples必须置1，先做前置判断(input & Apples) == Apples，不满足直接返回false
   • 剩余OR逻辑可简化为「Pears和Bananas任意一个置1」，对应位运算(input & (Pears | Bananas)) != 0
4. 最终示例的最优校验逻辑为：

(input & Apples) == Apples && (input & (Pears | Bananas)) != 0

额外优化技巧 #

• 若OR子句为「多个位任意一个为1」，直接简化为(input & mask) != 0，无需拆分为多个判断
• 若OR子句为「多个位任意一个为0」，直接简化为(input & mask) != mask
• 涉及的位数量较少时（一般不超过8位），可直接预先生成查找表，用lookup_table[input & full_mask]直接拿到结果，完全消除分支判断，性能最优

三、通用算法参考 #

该问题本质是布尔函数最小化问题，数字电路领域的经典算法可直接复用：

• 位标志数量≤16时，使用卡诺图化简，实现简单运算速度快，可直接得到最少的位运算步骤
• 位标志数量更多时，使用奎因-麦克拉斯基算法，支持自动化简任意AND/OR/NOT组合的布尔表达式，得到全局最优的运算组合

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