UVA 10718 Bit Mask

Problem A	Bit Mask
Time Limit	1 Second

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, ifN 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.

InputEach input starts with 3 unsigned integers N, L, U where L ≤U. Input is terminated by EOF.

OutputFor 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	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和一個範圍l，u在這個範圍内找一個最小的m能使n or m最大。

因為涉及到位運算，是以先把n轉化為二進制，然後根據或運算的性質來構造m

#include<iostream>
using namespace std;
int a[64];
long long n, l, r, i, cnt;

int main()
{
  while (cin >> n >> l >> r)
  {
    for (i = 0; i < 32; i++, n >>= 1) a[i] = n % 2;
    for (cnt = 0, i = 31; i >= 0; i--)
    {
      cnt += (long long) 1 << i;
      if (!a[i] && cnt <= r || a[i] && cnt <= l) continue;//保證了值最大m最小且在範圍内。
      cnt -= (long long) 1 << i;
    }
    cout << cnt << endl;
  }
  return 0;
}