Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1659
In bit-wise expression, mask is a common term. You can get a certain bit-pattern using mask. For example, if you want to make first 4 bits of a 32-bit number zero, you can use 0xFFFFFFF0 as mask and perform a bit-wise AND operation. Here you have to find such a bit-mask. Consider you are given a 32-bit unsigned integer N. You have to find a mask M such that L ≤ M ≤ U and N OR M is maximum. For example, if N is 100 and L = 50, U = 60 then M will be 59 and N OR M will be 127 which is maximum. If several value of M satisfies the same criteria then you have to print the minimum value of M. Input Each input starts with 3 unsigned integers N, L, U where L ≤ U. Input is terminated by EOF. Output For each input, print in a line the minimum value of M, which makes N OR M maximum. Look, a brute force solution may not end within the time limit.
Sample Input 100 50 60 100 50 50 100 0 100 1 0 100 15 1 15
Sample Output 59 50 27 100 1
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
// idea, check if we can do without a certain bit or add a bit
int main()
{
unsigned int m,l,u;
while(scanf("%u %u %u",&m,&l,&u) != EOF){
unsigned int cur = 0;
for(int i=31;i>=0;i--){
if(((1<<i)&m) == 0){
// bit is not set, try to set it if <= upper
unsigned int newNum = cur|(1<<i);
if(newNum < = u) cur = newNum;
} else {
// bit is set, try to unset it if we can still fulfill constraint
// largest possible without the i bit
unsigned int largestPossible = cur | ((1<<i)-1); // assume we set all subsequence bits later
if(largestPossible < l) cur |= (1<<i>; // we need the bit so that cur >= lower
}
}
cout << cur << endl;
}
}
Input
100 50 50
100 0 100
1 0 100
15 1 15
Output
50
27
100
1
Demonstration
UVA Online Judge solution - 10718-Bit Mask - UVA Online Judge solution in C,C++,java