最大的位或

布满荆棘的人生 2022-06-09 01:06 171阅读 0赞

B君和G君聊天的时候想到了如下的问题。   
给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。   
其中|表示按位或，即C、 C++、 Java中的|运算。

Input

包含至多10001组测试数据。   
第一行有一个正整数，表示数据的组数。   
接下来每一行表示一组数据，包含两个整数l,r。   
保证 0 <= l <= r <=  1018 1018。

Output

对于每组数据输出一行，表示最大的位或。

Sample Input

5
    1 10
    0 1
    1023 1024
    233 322
    1000000000000000000 1000000000000000000

Sample Output

15
    1
    2047
    511
    1000000000000000000

思路:都从二进制的角度来看，将L和R第一个不相同的数的后面全变为1,再去和R按为或即可

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    long long find_high(long long x)
    {
        int sum=0;
        while(x!=0)
        {
            x>>=1;
            sum++;
        }
        return sum;
    }
    int main()
    {
        int T;
        cin >> T;
        while(T--)
        {
            long long l,R,k,x;
            cin >> l >> R;
            k = l^R;
            long long num_=find_high(k);
            x = (1ll<<num_)-1;
            printf("%I64d\n",R|x);
        }
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，171人围观）

还没有评论，来说两句吧...

相关阅读

相关找到最大或最小的N个元素

某个集合中找出最大或最小的N个元素 `heapq` 模块的 `nsmallest 和 nlargest`是我们所需要的。如果只是找最大和最小 `max min` ...

待我称王封你为后i/ 2024年04月17日 16:36/ 0 赞/ 84 阅读

相关求数组中的最大差值或最小差值

描述给出长度为n的整数数组arr\[n\], 有n个整数，求出数组中两个数的最大差值。算法可以先求出最大值和最小值,在一轮循环中求出最大值和最小值，时间...

曾经终败给现在/ 2024年04月17日 05:33/ 0 赞/ 78 阅读

相关按位与、按位或、异或

按位与运算符（&）参加运算的两个数，按二进制位进行“与”运算。运算规则：只有两个数的二进制同时为1，结果才为1，否则为0。（负数按补码形式参加按位与运算）即 0

比眉伴天荒/ 2023年01月19日 08:27/ 0 赞/ 20 阅读

相关 AcWing | 最大异或对

题目内容： > 在给定的N个整数A1，A2……AN 中选出两个进行xor（异或）运算，得到的结果最大是多少？输入格式 > 第一行输入一个整数N。 > > 第二行输入N

「爱情、让人受尽委屈。」/ 2022年12月19日 11:47/ 0 赞/ 159 阅读

相关 “k最小”或“k最大”问题

最近看了看算法题，发现这类问题比较有趣。当你看到求“k最小”一类的问题，可以立即想打用“k selection”来解决。首先说一下“k selection”要

谁借莪１个温暖的怀抱￠/ 2022年07月12日 15:59/ 0 赞/ 202 阅读

相关最大的位或

B君和G君聊天的时候想到了如下的问题。给定自然数l和r ,选取2个整数x,y满足l <= x <= y <= r ,使得x|y最大。其中|表示按位或，即C、 C

布满荆棘的人生/ 2022年06月09日 01:06/ 0 赞/ 172 阅读

相关位运算总结(按位与,或,异或)

按位与运算符（&）参加运算的两个数据，按二进制位进行“与”运算。运算规则：0&0=0; 0&1=0; 1&0=0; 1&1=1; 即：两位同时为“1”，结果才为

傷城~/ 2022年05月21日 12:46/ 0 赞/ 284 阅读

相关杭电 5969 最大的位或

题目链接：[点我][Link 1] Problem Description B君和G君聊天的时候想到了如下的问题。给定自然数l和r ,选取2个整数x,y满足l <

小灰灰/ 2022年05月15日 02:34/ 0 赞/ 149 阅读

相关 143. 最大异或对(字典树 + 位运算)

题目描述：在给定的N个整数A1，A2……AN 中选出两个进行xor（异或）运算，得到的结果最大是多少？输入格式第一行输入一个整数N。第二行输入N个整数A

刺骨的言语ヽ痛彻心扉/ 2021年12月05日 21:43/ 0 赞/ 273 阅读

相关【Java】位与&，位或| ,位异或 ^ 总结

文章目录按位与运算符（&）按位或运算符（|）异或运算符（^）应用举例1:

一时失言乱红尘/ 2021年09月24日 23:52/ 0 赞/ 405 阅读