我的代码在c中++并且当前正在尝试完成任务。下方给出的链接
难度等级：中等
我的算法对20个测试用例中的18个运行良好。其他2个由于超时而终止。
我知道这意味着什么，但现在我不知道如何提高算法的效率。
我已经在下面给出了我的代码，有人能帮我解决这个问题吗https://www.hackerrank.com/challenges/and-product
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int t;
unsigned long int x,y,a;
cin>>t;
while(t)
{
cin>>x>>y;
a=x;
for(;x<=y;x++)
a=a&(x);
cout<<a<<"n";
t--;
}
return 0;
}
"……每个人类问题都有一个众所周知的解决方案——简洁、合理和错误。"-H.L.Mencken
在计算机科学中，我们可以重新表述：
"对于每一个计算问题，都存在一个简单、优雅且错误的解决方案。">
网站上的问题，如黑客链接、面试、游戏中演员的寻路、三维宇宙飞船的绘制，以及任何涉及筛选数据的制作系统中的问题，从来都不是关于是否有解决方案。
真正的问题总是这样：
"找到一种方法来降低这个看似微不足道的任务的复杂性。">
从a到b计数，同时将值固定在一起是一种线性时间算法-O(b-a)。当a和b很接近时，这没关系。但这个问题告诉你，他们被允许有一个高达2^32-1的间隔，这是在40亿次测试的数量级。
碰巧，这个问题可以简化为O(log2(b-a))，因为我们知道b比a大。
查看以下二进制表示的顶部：
a 01001 (9)
b 11001 (25)
有一些常见的比特，我们直观地想象这些比特是答案中剩余1的候选者。
然而，b有一个1的比特，其值比a的顶部比特大一个数量级。
为了从a到b计数，每一个低于顶部比特的比特都必须存在于1和0的每一个排列中，因为二进制表示就是这样工作的。
如果我们通过每个排列来排列二进制位字段，那么最终该字段中的每个位都将在某个点包含0。这意味着对比特字段的每个排列进行"与"运算的结果为零。
因此，当我们在b中发现一个不在a中的1比特时，我们可以简单地屏蔽a中所有较低幅度的比特。
现在问题变成了：
找到b中不存在于a中的最高位，并屏蔽a中的所有低阶位。返回结果。
我们刚刚将搜索空间从0<N<2^32)到0<N<=32.换句话说，复杂性可以从O(N)降低到O(log2(N))。
这里有一个天真的解决方案——它甚至不需要优化比特掩码的计算——它通过了hackerlink的所有测试。
#define TESTING 0
#include <iostream>
#include <string>
#if TESTING
#include <sstream>
#endif
#include <cstdint>
using namespace std::literals;
#if TESTING
const char test_data[] =
R"__(
3
12 15
2 3
8 13
)__";
#endif
bool has_bit(const std::uint32_t x, int bitnum)
{
return (x & (1 << bitnum)) != 0;
}
constexpr std::uint32_t mask_here_down(int bitnum)
{
std::uint32_t result = 0;
while (bitnum--)
{
result |= std::uint32_t(1) << bitnum;
}
return result;
}
void algo(std::istream& in, std::ostream& out)
{
std::uint32_t a,b;
in >> a >> b;
for (int bit = 32 ; bit-- ; )
{
if (has_bit(b, bit) and not has_bit(a, bit))
{
std::cout << (a & ~mask_here_down(bit)) << std::endl;
break;
}
}
}
void run_tests(std::istream& in, std::ostream& out)
{
int n;
in >> n;
while (n--)
{
algo(in, out);
}
}
int main()
{
#if TESTING
auto in = std::istringstream(test_data);
#else
auto& in = std::cin;
#endif
run_tests(in, std::cout);
}