For the problem statement : DCE05 Problem - CodeChef
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 CodeChef: Practical coding for everyone
1 Like
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
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.
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 ( CodeChef: Practical coding for everyone ) 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 CodeChef: Practical coding for everyone
@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???