How to efficiently find Bitwise OR of a range of numbers

Question

Given a range of number [a,b], how to efficiently find Bitwise OR of all numbers in this range. Running a loop for range [a,b] and computing Bitwise OR of all the numbers individually is too much time consuming for a range which is very large, so this is not the option.

Answer 1

Instead of doing it for all numbers, you can do it for all positions. That would require you only log(n) steps.

So lets try to imagine - when will units place be 1? If either upper or lower is odd or if there is one number between them. So either lower % 2 == 1 or lower != upper.

Great we got units place. Now if remove the lower one bit from both upper and lower bits and repeat we get the other positions.

Only a special case if lower == upper. In that case we return the lower itself.

Following is the code -

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

The second loop is to just reserve the bit sequence.

Demo here - https://ideone.com/MCIugW

Thank you @Meixner for the driver code.