Search code examples
binaryboolean-logicbitwise-and

How to maximize the value of binary expression?


How can we simplify (a&b)*(c&b)? where '&' is bitwise and also * represents product.

Or find b in [L,R] such that (a&b)*(c&b) is maximum?


Solution

  • Assume unsigned. Look at a & mask a bit will be set if it is set in both a and the mask. A zero in the mask will never make the result larger but could make it smaller, if the corresponding bit in a was set.

    so:

    (a&b)*(c&b) will never be larger than a*c which is achieved when all bits in b is set.

    If b should be as small as possible you could clear all the bits which will not decrement either a or c, i.e. a bit set in either one of them:

    b = a | c