Logic please

help
1

Q-CodeChef: Practical coding for everyone

can anyone tell which method is this.

#include <bits/stdc++.h>
using namespace std;

int countMaxSetBits(int left, int right)
{
while ((left | (left + 1)) <= right)
left |= left + 1;

return left;

}

int main()
{
int t;
cin>>t;
while(t){
int l,r;
cin>>l;
cin>>r;
cout << countMaxSetBits(l, r) << endl;
t–;
}
return 0;
}

2
3

Can you explain the logic , I still didn’t got the logic even after reading it

4

Let’s firstly emphasize on what n=(n|n+1) does:

  • For n =12 \equiv 1100 (In binary) :
    (n|n+1)=1100|1101=1101

  • For n=47\equiv 101111
    (n|n+1)=101111|110000=111111

  • For n=71\equiv 1000111
    (n|n+1)=1000111|1001000=1001111

If you work out a few binary additions on paper then you’ll have the following interesting observation.

  • n=(n|n+1) sets the rightmost unset bit of n.

So what this algorithm essentially does is to iteratively keep on turning the rightmost unset bit of n while ensuring in each iteration that n \in[A, B]. So we can be assured that our result from the last iteration will have the maximum number of set bits(since we’re increasing the number of set bits in each iteration) and it will be minimum with that many set bits (since we’re greedily turning on the rightmost unset bit) .

4 Likes
5

Thanks Man, Now I understood , It really helped

1 Like