A problem relevate to bitmask (or operation) and segment

Question

I'm trying to solve this problem:

Given three integers N, L, and R, find the integer M between L and R (inclusive) that maximizes M|N (the bitwise-OR of M and N). If there are multiple such values of M, return the least of them.

For example: N=100,L=50,R=60. The result is 59. Because 100|59 reaches the maximum value and 50<=59<=60.

This is my attempt:

#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;
}

My idea is to browse each bit from left to right (it's mean form 31'st bit down to 0's bit) of L,R,N. Then, use the comparative statement to find the number M that satisfies the problem , specifically like above.

But when submit solution, I got Wrong Answer, this means, my algorithm is false, ans I'm stucking in ideal so solve this problem, can you help me this stuck ?

Answer 1

Without params validation

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