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

Question

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

Answer 1

任何 2ⁿ-1 形式的数字都将是

n

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

范围中的下一个数字将是

1

，后跟

n

0

，当您与此进行 OR 时，您将得到

n+1

1

。由于我们选择了上述数字作为 2 的最大幂，因此我们将永远不会再获得该数字中的任何位。

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

n

1

位的数字。否则它是

n+1

1 位。

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

Answer 2

您可以对所有位置执行此操作，而不是对所有数字执行此操作。那只需要您记录（n）步。

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

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

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

Answer 4

#include <bits/stdc++.h>
using namespace std;
#define int long long
int bitwiseor(int a, int b){
if (a==b)
    return a;
int final = 0;
int 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;
}


int32_t main(){
long long N,M;
cin>>N>>M;
cout<<bitwiseor(N,M)<<endl;

return 0;
}

时间复杂度 O(max(log2(N),log2(M)))