如何高效查找数字范围的按位或运算
给定数字范围[a,b],如何有效查找此范围内所有数字的按位或运算。对范围[a,b]运行一个循环并计算所有数字的逐位OR对于非常大的范围来说太耗费时间,所以这不是选项。如何高效查找数字范围的按位或运算
而不是所有的数字,你可以做所有的位置。这就需要你只记录(n)个步骤。
所以让我们试着想象一下 - 单元何时放置为1?如果上限或下限是奇数或者它们之间有一个数字。因此,要么%2 == 1或更低!=上。
太棒了,我们有单位的地方。现在,如果从高位和低位中删除较低的一位,并重复我们得到的其他位置。
只有一个特殊情况,如果==较低。在这种情况下,我们会返回低位。
以下是代码 -
unsigned int bitwiseor(unsigned int a, unsigned int b){
if (a==b)
return a;
unsigned final = 0;
unsigned rev = 0;
while(b){
final*=2;
if (a%2==1 || a != b)
final++;
a/=2;
b/=2;
}
while(final){
rev *= 2;
rev += final % 2;
final/=2;
}
return rev;
}
第二个循环是只保留位序列。这里
演示 - https://ideone.com/MCIugW
谢谢@Meixner的驱动程序代码。
任何数字的形式2 n -1将是n
1的位模式。当你使用任何数字或者低于它时,你会得到2 n -1。因此,范围内最高的所有数字都可以忽略不计。
范围内的下一个数字将是一个1
随后n
0
s,而当您或与此,你会得到n+1
1
秒。由于我们选择上述数字作为2的最大幂数,因此我们将永远不会在数字中获得更多位。
所以基本上只有2例。如果范围的顶部是2 n -1,则结果是具有n
1
位的数字。否则它是n+1
1位。
上面假设范围包括一个值。如果没有,只要尝试循环(可能会做一些优化,但我无法将它们想象成我的头顶)。
这是正确的,直到最后一段,它没有考虑范围的底部。 (例如,[9,10]的结果是1001 | 1010 = 1011,而你的方法会说它是1111) –
@Barmar当没有2^n-1位于范围内时,它不完整。 –
@AjayBrahmakshatriya是的,我意识到,因为我昨晚要去睡觉。 – Barmar
#include <stdio.h>
#include <stdlib.h>
int dumb(int a, int b)
{
int z=0;
while(a<=b) z|=a++;
return z;
}
int smart(int a, int b)
{
int d,z;
if(a>b) return 0;
d=b-a+1;
z=0;
while(d>1) { z=(z<<1)|1; d>>=1; }
d=z;
z|=a;
a+=d;
while(a<=b) z|=a++;
return z;
}
int main(int argc, char *argv[])
{
int a,b;
for(a=0;a<1000;a++) {
for(b=a;b<1000;b++) {
int z1=dumb(a,b);
int z2=smart(a,b);
if(z1!=z2) {
printf("fail %d %d\n",a,b);
}
}
}
return 0;
}
好吧,太糟糕了。 C没有什么比循环更好的了。如果目标拱有适当的命令,您可以尝试内联汇编。 – StoryTeller
记下一些连续数字的位模式。记下按位或结果。做这个很多不同的范围。你能发现一种模式吗? – kaylum
如果范围包含任何2^n-1值,那么这将全部为1,并且当您对任何事物进行或运算时,您将全部获得1,因此您可以跳过它下面的所有数字。 – Barmar