UVa 10718 Bit Mask (贪心&位演算)

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 mask M such that L ≤ M ≤ U and N OR M is maximum. For example, ifN is 100 and L = 50, U = 60 thenM 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 ofM.

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 makesN OR M maximum.

Look, a brute force solution may not end within the time limit.

Sample Input	Output for Sample Input
100 50 60 100 50 50 100 0 100 1 0 100 15 1 15	59 50 27 100 1

贪心思路：

从高位往低位考虑，

若n的第i位是0，则m需尽量在这一位为1，且在这一位变为1后m<=U；
若n的第i位是1，则m需尽量在这一位为0，但m不能太小以至于当L在这一位为1时m<L。

完整代码：

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