Bitwise operation: Finding only the most Significant bit that is set

For the problem statement : http://www.codechef.com/problems/DCE05/

the following tutorial is given on the bitwise operations : http://www.codechef.com/wiki/tutorial-bitwise-operations

and following is the code i wrote :

#include<iostream>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
        {
            int i;
            cin>>i;
            i=i|(i>>1);
            i=i|(i>>2);
            i=i|(i>>4);
            i=i|(i>>8);
            i=i|(i>>16);
            i=(i+1)>>1;
            cout<<i<<endl;
        }
}

but the chef says that the time limit is exceeded, so how can i minimize the the time of the program?

Use scanf and printf instead of cin and cout, My code gave tle when I used cin/cout and got AC when I used scanf/printf, Here is a link to my solution http://www.codechef.com/status/DCE05,v_akshay

1 Like

besides using scanf/printf instead of cin/cout is there any other approach for the problem?

@insaynasasin, if your logic is true, and if it gets AC when used C codes rather than C++, then dont persist on wrong. just get used to better and faster ones.

Small optimization : The question is equivalent to finding the smallest power of 2 less than the given number. I pre-computed all the powers of 2 before hand and then counted the highest power of 2. Lets say it is 2^23. then i simply print arr[23] i.e. 23rd element of pre-computed array. As you need powers of 2 upto around 30 pre-computation can help you save some time.

Also you can replace all those operations by a while loop. It will just make coding easier. Here is my solution for reference. However the main reason for tle is still the cin/cout.

1 Like

this answer gonna be thumbed up and AC

I don’t think that its an optimization instead its an overkill, After finding the number of bits just shifting the bits using (<< operator) is faster than fetching the value from a static array! you can see that your submission is taking longer time than mine.

@v_akshay The reaspon your program takes less time is because of the structure of your code. This ( http://www.codechef.com/viewsolution/3305471 ) is your code where i have pre-computed the powers of 2 and you can see a slight improvement in time using pre-computation.(0.77 vs 0.75). However as i had said, this is just a minor optimization and wont affect much.

I am still not convinced, I firmly believe that << is faster , you have to look how a[i] is implemented at lower level its
*(a+(i*sizeof(typeof(a)))) which involves more operations than just shifting the bits!

I am getting 0.77 when fetching from bss, 0.76 from register and 0.75 from stack! by the way your solution which ran in 0.75s, try submitting it again when I submitted it, I got a time of 0.77 Check my last submission http://www.codechef.com/status/DCE05,v_akshay

@garakchy sorry not used to the language very much but do you mean that instead of searching for right solution i should rather search for a solution that is faster???
i mean instead of depending of choice of language i should improve my algorithm for the problem???

//