## Tuesday, July 22, 2014

So today I learn a new bitwise manipulation technique :D

Problem Statement:

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;
}