c - 如何有效地找到一系列数字的按位或

Question

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

Answer 1

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

范围内的下一个数字将是 a1后跟n 0s，当您使用它进行 OR 操作时，您将得到n+1 1s。由于我们选择了上述数字作为 2 的最大幂，因此我们将永远不会在该数字中获得更多位。

所以基本上只有2个案例。如果范围的顶部是 2 ⁿ -1，则结果是一个带有n 1位的数字。否则为n+11 位。

以上假设范围包括 2 ⁿ -1 值。如果没有，请尝试循环（可能可以进行一些优化，但我无法想到它们）。

Answer 2

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

所以让我们试着想象一下——单位的位置什么时候是 1？如果上或下是奇数，或者它们之间有一个数字。所以要么降低 % 2 == 1 要么降低 != 上部。

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

如果 lower == upper 则只是一种特殊情况。在这种情况下，我们返回较低的本身。

以下是代码 -

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