如何高效查找数字范围的按位或运算

Question

给定数字范围[a，b]，如何有效查找此范围内所有数字的按位或运算。对范围[a，b]运行一个循环并计算所有数字的逐位OR对于非常大的范围来说太耗费时间，所以这不是选项。

Answer 1

而不是所有的数字，你可以做所有的位置。这就需要你只记录（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的驱动程序代码。

Answer 2

任何数字的形式2 ⁿ -1将是n 1的位模式。当你使用任何数字或者低于它时，你会得到2 ⁿ -1。因此，范围内最高的所有数字都可以忽略不计。

范围内的下一个数字将是一个1随后n0 s，而当您或与此，你会得到n+11秒。由于我们选择上述数字作为2的最大幂数，因此我们将永远不会在数字中获得更多位。

所以基本上只有2例。如果范围的顶部是2 ⁿ -1，则结果是具有n1位的数字。否则它是n+1 1位。

上面假设范围包括一个值。如果没有，只要尝试循环（可能会做一些优化，但我无法将它们想象成我的头顶）。

Answer 3

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