UVa 10718 Bit Mask (贪心&位运算)
10718 - Bit Mask
Time limit: 3.000 seconds
http://uva.onlinejudge.org/index.php?option=com_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 integerN. You have to find a maskM such that L ≤ M ≤ U and N OR M is
Sample Input
Output for Sample Input
/*0.013s*/#include<cstdio>typedef unsigned int ui;int main(){ui n, l, u, m, temp;int i;while (~scanf("%u%u%u", &n, &l, &u)){m = 0;for (i = 31; i >= 0; --i){///若n的第i位是0，则m需尽量在这一位为1，且在这一位变为1后m<=U///若n的第i位是1，则m需尽量在这一位为0，但m不能太小以至于当L在这一位为1时m<L///注意n<L这种情况temp = m | (1u << i);///位运算形式的m + (1u << i)if (((n >> i) & 1) == 0 && temp <= u || (l >> i) & 1 && m < l) m = temp;}printf("%u\n", m);}return 0;}
