[贪心]UVA10718 Bit Mask

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.

题意：给出一个数，和一个范围，求这个范围内的一个数使得它与给定的这个数相或最大，注意如果有多个选择，选取最小的数。

思路：因为给出的数较大，直接暴力肯定是不行的。

要使得or运算结果最大，我们考虑从最高位开始进行or运算，如果该位是0，我们把他变为1，并且算出这个时候得M值是否在范围内，如果在范围内我们就把它加进来。如果该位是1，要使得M最小，我们尽量让M的这一位为0。这个时候会有一个问题，那就是如果M得这一位位0，会不会使得M太小而达不到L到U的范围，我认为是不可能的，因为如果该位选1并且后面所有位数都选1都达不到下线的话，那么和上一步的选择就矛盾了。

#include<iostream>

using namespace std;

int ans[64];
long long N,L,U;
long long dex[64];



int main()
{
	int i;
	dex[0]=1;
	for(i=1;i<=32;i++)
		dex[i]=dex[i-1]*2;
	while(cin>>N>>L>>U)
		{
			long long x,y,cnt=0;
			for(i=0;i<32;i++)
				{
					ans[i]=N%2;
					N/=2;
				}
			for(i=31;i>=0;i--)
				{
					if(ans[i]==0)
						{
							x=cnt+dex[i];
							if(x<=U)
								cnt=cnt+dex[i];
						}
					else
						{
							x=cnt;
							y=cnt+dex[i]-1;
							if(y<L)
								cnt=cnt+dex[i];
						}
				}
			cout<<cnt<<endl;
		}
	return 0;
}

[贪心]UVA10718 Bit Mask,布布扣,bubuko.com

[贪心]UVA10718 Bit Mask

原文：http://blog.csdn.net/zju_ziqin/article/details/22376131