如何高效查找數字範圍的按位或運算

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