如何有效地查找一系列数字的按位或

Question

给定一个范围内的数字 [a,b]，如何高效地求出该范围内所有数字的按位或。运行范围 [a,b] 的循环和单独计算所有数字的按位或对于非常大的范围来说太耗时了，所以这不是选项。

Answer 1

任何形式为 2ⁿ-1 的数字都是 n 1 的位模式。当您将其与其下方的任何数字进行 OR 运算时，您将得到 2ⁿ-1。所以范围内最高2ⁿ-1以下的所有数字都可以忽略。

范围内的下一个数字将是 1 后跟 n 0s，当你用它或运算时，你会得到 n+1 1秒。由于我们选择了上面的数字作为 2 的最大幂，所以我们将永远不会得到更多的数字。

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

以上假定范围包括 2ⁿ-1 个值。如果没有，就试试这个循环（可能有一些优化可以做，但我想不出来）。

Answer 2

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

Answer 3

您可以对所有位置都这样做，而不是对所有数字都这样做。那将只需要您 log(n) 个步骤。

那么让我们试着想象一下——单位位置什么时候会变成1？如果 upper 或 lower 是奇数或者它们之间有一个数字。所以 lower % 2 == 1 或 lower != upper.

太好了，我们得到了单位名额。现在，如果从高位和低位中删除低位并重复我们得到其他位置。

如果 lower == upper 只是一个特例。在那种情况下，我们 return 较低的本身。

代码如下 -

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 提供的驱动程序代码。

如何有效地查找一系列数字的按位或

How to efficiently find Bitwise OR of a range of numbers

c

algorithm

bit-manipulation

bitwise-operators

bitwise-or