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

For the problem statement :

the following tutorial is given on the bitwise operations :

and following is the code i wrote :

using namespace std;
int main()
    int t;
            int i;

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,v_akshay

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 ( ) 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,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???