how do i efficiently find bitwise OR of all elements in a given range[l,r].
someone please help me out
I am not able to understand the code given in stack overflow . someone please explain me the logic Here is the code below
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;
}
Also how this problem is a solution to the october cook off question DOR ? how is it related ??
See my comments below.
unsigned int bitwiseor(unsigned int a, unsigned int b){
if (a==b)
return a; // if a and b are equal then a || b == a
unsigned final = 0; // variable to store result in reverse order
unsigned rev = 0; // variable for result in correct order
while(b){ // as long as there are bits set in b do the loop
final*=2; // shift all bits in 'final' to the left, better: final <<= 1
if (a%2==1 || a != b) // Wrong! Should be "if( (a | b) & 1)"
final++; // set right-most bit in 'final'
a/=2; // a >>= 1 -> get next bit of 'a' in position 1
b/=2; // b >>= 1 -> get next bit of 'b' in position 1
} // now we have the result in the wrong order, bits are reversed
while(final){ // now reverse the result, do loop as long as there are bits set
rev *= 2; // rev <<= 1 -> shift bits to the left
rev += final % 2; // set right-most bit, if 'final' is odd
final/=2; // final >>= 1 -> shift bits to the right
}
return rev;
}
Apart from the mistake in the if(), it is poorly coded. Divisions and multiplications are expensive operations, should be replaced by >> and <<. Also testing for odd number should be “a & 1” instead of “a % 2”.
Why do you need this function? Bitwise or is “a | b” in C.
I see, it’s not a | b, but a | a+1 | a+2 | … | b-2 | b-1 | b that you are looking for. Let me have another look, I misunderstood what you were looking for.
In that case the if() is correct. We look for the right-most bit. If a is odd, then we set the bit OR if the range is not only a single number, i.e. a!=b. In that case, even if a is even, we can be sure that there is another number within the range that has the right-most bit set. Then we shift a and b bitwise to the right and check the next position.
Still the code could be optimised, multiplications and divisions should be avoided.
Dear what is the question ?
What’s wrong to create a Fibonacci series?
N=int (input ())
for i in range (N):
f=[0,1]
f.append (f [i]+f [i+1])
print (f)