Problem Statement:

UVa 10718 - Bit Mask

__Summary__

For \(N, M, U, L\) such that \(L \leq M \leq U\), find minimum \(M\) such that \(M\)

**OR**\(N\) is maximum (where

**OR**refers to bitwise OR operation).

This problem requires a strategy to switch on bits on M (starting from all 0 bit) such that we only switch on a bit on M when we absolutely need to, but we must also ensure that M can fall between L and U.

Strategy:

For i-th bit of N starting from the leftmost bit:

1. If the i-th bit of N is ON, the best case scenario is we do not need to turn on the i-th bit of M. That is, if by letting the i-th bit of M off, we can still have M in between L and U, we will do so. Otherwise, the i-th bit of M must be on.

2. Else, if the i-th bit of N is OFF, the best case to maximize M

**OR**N is by switching the i-th bit of M to ON. However, if the resulting M is higher than U, we must switch the i-th bit of M to OFF instead.

As such, the resulting M will be in between L and U.

For example, when N = 101101, L = 011010, U = 011110

i = 5:

leftmost bit of N is ON, hence M should be off, and indeed the resulting M can still fall between L and U.

i = 4:

bit of N is OFF, hence we would like to turn it on. The resulting M = 01**** can still be less than U, i.e the lowest M = 010000 is indeed less than U, so we can do so.

i = 3:

bit of N is ON, hence we want that bit on M to be OFF. but M = 010*** will always be less than L, i.e the highest possible M = 010111 is not lower than L, hence we must have that bit to be switched ON, i.e M = 011***

i = 2:

bit of N is ON, and we want M to be OFF. M = 0110** can still be in between L and U, i.e. the highest possible M = 011011 is not lower than L.

i = 1:

bit of N is OFF. If we switch that bit of M on, M = 01101* can still be less than U.

i = 0:

the rightmost bit is ON, so we want that bit on M OFF, and we have our minimum M such that M

**OR**N is maximum.

Here is the code:

#include <iostream> #include <cstdio> using namespace std; typedef long long ll; int main(){ ll N,U,L,ans; while(scanf("%lld %lld %lld",&N,&L,&U)!=EOF){ ans = 0; for(int i=0;i<=32;++i){ ll state = (N & (1L<<(32-i))); //printf("%lld\n", state); //printf("%lld\n", ans); if(state){ //if the bit is set //if not setting this bit can still fulfill the constraint ll temp = state -1; temp |= ans; if(temp < L){ ans |= state; } } else { //if not set, should set if fulfill constraint ll temp = ans; temp |= (1L<<(32-i)); if(temp <= U){ ans = temp; } } } printf("%lld\n",ans); } return 0; }