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

Admin 1
Viewed 134

This is the recurrence relation of maximum sum subset problem.

The complete code is:

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

What does exactly mean the following if-statement?

if((mask | u) == u)

Thank you in advance!

if-statement bitwise-operators c++
2 Answers

It means: “Are all bits of mask in u”. So if there is a bit in mask not in u this test returns false.

For instance with mask=0b001 and u=0b011 it returns true. But with mask=0b101 and u=0b011 it returns false because the third bit of mask is not set in u.

user_50341400

Binary OR for binary values A, B evaluates as (1) if either A = 1 or B = 1. These bitwise operations extend to strings of binary digits. In C/C++, that's most commonly expressed as integral types.

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

(forgive the ASCII art - more concise illustrations and links are here)

mask = {m(n - 1), m(n - 2), .., m(1), m(0)} : (n) binary digits (bits) m(i)

u = {u(n - 1), u(n - 2), .., u(1), u(0)} : (n) binary digits (bits) u(i)

Let's consider (m(i) | u(i)) == u(i) for: i = {0, .., n - 1} ; should any of these bit-wise comparisons be false, then the expression ((mask | u) == u) evaluates as false.

From the OR table we can conclude that the expression is false if and only if m(i) = 1 and u(i) = 0. That is: m(i) | u(i) == (1) OR (0) == (1) which does not equal u(i) == 0

A more concise way of expressing the issue is that if mask has a bit at a position (i) set to (1), and u has a bit at the same position cleared to (0), then (mask | u) cannot equal u.

user_9068390
Related