已知二进制数z及x、y部分位，求x|y=z的合法状态数量

问题描述 #

现有三个二进制数，要求第一个数(x)与第二个数(y)的**按位或（bitwise OR）**运算结果等于第三个数(z)。已知完整的z，以及x、y的部分位信息，求解满足条件的(x,y)合法状态总数。

示例 #

已知：

• x = 0 _（仅确定最高位为0，最低位未知）
• y = _ _（两位均未知）
• z = 11

满足条件的合法(x,y)状态为：[(00,11),(01,10),(01,11)]，总共有3种合法状态。

核心解法：逐位独立计算 #

由于二进制按位或运算中，每一位的结果仅由x和y的对应位决定，因此可对z的每一位单独分析，计算该位上(x,y)的合法组合数，最后将所有位的组合数相乘，即可得到总的合法状态数。

分情况讨论每一位的合法组合 #

针对z的每一位取值，结合x、y对应位的已知限制，合法组合数如下：

1. 当z的当前位为1时
   按位或规则要求：x和y的该位至少有一个为1
   • 若x该位固定为0：y该位必须为1，仅1种合法组合
   • 若x该位固定为1：y该位可取值为0或1（需符合y的已知限制，若y该位固定则仅当取值符合时算1种，否则0种；无限制则为2种）
   • 若x该位未知：
     • 若y该位固定为0：x必须为1，仅1种组合
     • 若y该位固定为1：x可取值0或1，共2种组合
     • 若y该位也未知：合法组合为(0,1)、(1,0)、(1,1)，共3种
2. 当z的当前位为0时
   按位或规则要求：x和y的该位必须都为0
   • 若x该位固定为1，或y该位固定为1：直接冲突，总组合数为0
   • 若x该位固定为0：y该位必须为0（若y该位固定为非0则冲突，组合数为0；否则为1种）
   • 若y该位固定为0：x该位必须为0（若x该位固定为非0则冲突，组合数为0；否则为1种）
   • 若x和y该位都未知：仅(0,0)这1种合法组合

示例验证 #

用给出的示例计算：
z为11，分两位计算：

• 最高位：z=1，x固定为0，因此y必须为1，仅1种组合
• 最低位：z=1，x、y该位均未知，有3种组合
  总状态数 = 1 × 3 = 3，与示例结果一致。

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