'if((mask | u)==u)' 是什么意思？

Question

这是maximumsum子集问题的递推关系

完整代码为：

if ((mask | u) == u)
    dp[u] = max(max(0, dp[u ^ mask] + array[I], dp[u]);

以下 if 语句的确切含义是什么？

if((mask | u) == u)

提前致谢！

Answer 1

表示：“mask的所有位都在u”。因此，如果 mask 中有一个位而不是 u 此测试 returns false.

例如 mask=0b001 和 u=0b011 它 returns true。但是对于 mask=0b101 和 u=0b011 它 returns false 因为 mask 的第三位没有在 u.

中设置

Answer 2

二进制 OR 对于 二进制 值 A，B 计算为 (1) 如果或者 A = 1 或 B = 1。这些按位运算扩展到 字符串 的二进制数字。在 C/C++ 中，最常表示为 integral types。

OR    | A = 0 | A = 1 |
-----------------------
B = 0 | (0)   | (1)   |
-----------------------
B = 1 | (1)   | (1)   |
-----------------------

（请原谅 ASCII 艺术 - 更简洁的插图和链接是 here）

mask = {m(n - 1), m(n - 2), .., m(1), m(0)} : (n) 二进制数字（位） m(i)

u = {u(n - 1), u(n - 2), .., u(1), u(0)} : (n) 二进制数字（位） u(i)

让我们考虑 (m(i) | u(i)) == u(i) 为： i = {0, .., n - 1} ;这些按位比较的 any 应该是 false，然后表达式 ((mask | u) == u) 求值作为 false.

从ORtable我们可以得出结论，表达式为假当且仅当m(i) = 1和u(i) = 0 .即：m(i) | u(i) == (1) OR (0) == (1) 不等于u(i) == 0

更简洁的表达方式是，如果mask在(i)位置有一个位设置为(1)， u在相同的位置有一点清除到(0)，然后(mask | u)不能等于u.

What does 'if((mask | u)==u)' mean?