双面卡牌取数最大化bitwise AND值的代码片段逻辑异常咨询

两段代码的核心差异是当卡牌的正反面数字都包含当前判断的bit位时的处理逻辑不同，这也是注释代码出错的根本原因。

首先明确代码执行的前置条件：进入设置state的循环前，代码已经通过possible判断过滤了所有无法保留当前bit的情况，因此所有state[i]==-1的卡牌，必然满足A[i]&bit和B[i]&bit至少有一个为真。

正常运行的代码逻辑 #

if (state[i] != -1)continue;
if (!(A[i]&bit))state[i] = 1;
else if (!(B[i]&bit))state[i] = 0;

• 只有当卡牌只有反面包含当前bit时，才强制设置state为1（必须翻转才能保留当前bit）
• 只有当卡牌只有正面包含当前bit时，才强制设置state为0（必须不翻转才能保留当前bit）
• 如果正反面都包含当前bit，不会修改state[i]，保持为-1留到更低的bit位再做决策。这种情况选正面还是反面都不影响当前bit的AND结果，推迟决策可以让我们在处理更低bit时，选择能保留更多高位1、且翻转次数更少的方案。

注释代码的错误逻辑 #

if(state[i]!=-1)continue;
if(A[i] & bit)state[i]=0;
else if(B[i] & bit)state[i]=1;

• 只要卡牌正面包含当前bit，就直接强制设置state为0，哪怕反面也包含当前bit，也不会留到后面处理。
• 这种提前锁死state的操作，会导致后续处理更低bit时，无法选择更优的正反面方案，最终得到的AND值比最优解小。

错误复现示例 #

举个简单的例子就能复现错误：
假设n=2，卡牌数值如下：

• 卡牌1：正面A=11（二进制1011），反面B=12（二进制1100）
• 卡牌2：正面A=11（二进制1011），反面B=12（二进制1100）

最优解是两张都翻转，最终AND为12&12=12（1100），翻转次数为2。
注释代码的执行结果：

1. 处理最高位bit=8（1000）时，两张卡牌正反面都包含该bit，注释代码直接把两个state都设为0
2. 处理bit=4（100）时，state已经是0，检查A的该bit为0，直接判定无法保留该bit，跳过
3. 最终得到的AND值为11&11=11（1011），比最优解12更小，结果错误。

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