时间戳

首页 > 解决方案 > 与位掩码（或操作）和段有关的问题

c++ - 与位掩码（或操作）和段有关的问题

问题描述

我正在尝试解决这个问题：

给定三个整数 N、L 和 R，找到 L 和 R（含）之间的整数 M，它使 M|N（M 和 N 的按位或）最大化。如果 M 有多个这样的值，则返回其中最少的一个。

例如：N=100,L=50,R=60。结果是59。因为100|59达到最大值，50<=59<=60。

这是我的尝试：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
    ll n,m,l,r,i,tmp,res,first,second,vt,dau,third=0,aka,check_high=0;
    while(cin>>n>>l>>r){
        tmp=0;dau=0;
      for(i=31;i>=0;i--){
            first = (l>>i)&1;
            second = (r>>i)&1;
            third = (n>>i)&1;
          if(first==0&&second==0&&dau==0) continue;
          dau=1;
          if(first==1&&dau==1&&tmp==0) {tmp|=(1<<i);continue;}
          if(first==0&&dau==1&&tmp==0) if(third==0) {tmp|=(1<<i);continue;}
          if(first==0&&second==0&&third==0){
              if(tmp|(1<<i)<=r) tmp|=(1<<i);
              continue;
          }
          if(first==0&&second==1&&third==0){
              if(tmp|(1<<i)<=r) tmp|=(1<<i);
              continue;
          }
          if(first==1&&second==0&&third==0){
              if(tmp|(1<<i)<=r) tmp|=(1<<i);
              continue;
          }
          if(first==1&&second==1&&third==0){
              if(tmp|(1<<i)<=r) tmp|=(1<<i);
              continue;
          }
      }
      cout<<tmp<<'\n';
    }
    return 0;
}

我的想法是从左到右浏览 L、R、N 的每一位（这意味着从第 31 位向下到 0 位）。然后，使用比较语句找到满足问题的数字M，具体如上。

但是当提交解决方案时，我得到了错误的答案，这意味着我的算法是错误的，我陷入了理想状态，所以解决这个问题，你能帮我解决这个问题吗？

标签： c++algorithmbitmask

解决方案

没有参数验证

uint32_t getM(uint32_t L, uint32_t R, uint32_t N) {
    auto M = L;

    for (int bit = sizeof(L) * 8; bit > 0;) {
        const decltype(L) value = 1 << (--bit);

        if (value & N) {
            if (value & M) {
                decltype(L) check_value = M & (~value);
                for (int i = bit; i > 0;) {
                    check_value |= (1 << (--i));
                }
                if (check_value >= L) {
                    M = check_value;
                }
            }
        }
        else {
            if (!(value & M)) {
                decltype(L) check_value = M | value;
                for (int i = bit; i > 0;) {
                    check_value &= (~(1 << (--i)));
                }
                if (check_value <= R) {
                    M = check_value;
                }
            }
        }
    }

    return M;
}

int main(int, char**)
{
    std::cout << "M=" << getM(50, 60, 100) << std::endl;
    std::cout << "M=" << getM(184, 270, 103) << std::endl;
    return 0;
}

Output:
M=59
M=264

推荐阅读