Contest Duration: - (local time) (100 minutes) Back to Home
Official

## B - log2(N) Editorial by en_translator

There are various approaches to solve this problem. Here, we will explain some of them. Even if you got accepted during the contest, we recommend considering other solutions.
Note that the sample codes in this editorials are provided in C++.

1. Basic solution
2. Solution using logarithmic function, and numerical errors
3. Solution using binary representation of an integer

#### 1. Basic solution

First, as $$k$$ increases, obviously $$2^k$$ gets larger too. Therefore, we can see that $$2^k \le N$$ for all integers $$k$$ up to some boundary, or $$2^k>N$$ for $$k$$ greater than that value.
Thus, we can find the answer with a loop where $$k$$ is incremented one by one .
Note that one can $$2^k$$ efficiently compute $$2^k$$ during the loop of incrementing $$k$$ for a good computational complexity.

#include<bits/stdc++.h>

using namespace std;

int main(){
long long n;
cin >> n;
long long val=1;
for(long long i=0;i<=60;i++){
if(val>n){
cout << i-1 << '\n';
break;
}
val*=2;
}
return 0;
}


#### 2. Solution using logarithmic function, and numerical errors

By applying logarithmic function to $$2^k \le N$$ we obtain $$k \le \log_2(N)$$. Therefore, one should be able to output the $$\log_2(N)$$, rounded down to an integer, to get accepted.
However, this code results in WA (Wrong Answer).

#include<bits/stdc++.h>

using namespace std;

int main(){
long long n;
cin >> n;
cout << floor(log2(n)) << '\n';
return 0;
}


The cause of WA is lack of precision. Specifically, a precision occurs for the following case ($$N=2^{59}-1$$). (WA: 59, AC: 58)

576460752303423487


In order to avoid the error, one can use a type having more precisions than 64-bit floating point decimal. If you modify the last code as follows, you can get accepted for this problem.

#include<bits/stdc++.h>

using namespace std;

int main(){
long long n;
cin >> n;
cout << floor(log2((long double)n)) << '\n';
return 0;
}


No that high-precision type is not always omnipotent. If the constraints for this problem were $$N \le 2 \times 10^{18}$$, the modified code still outputs a wrong answer for the following test case. (WA: 60, AC: 59)

1152921504606846975


In competitive programming, discarding the integral property in an integral problem and using only decimals is dangerous. We recommend you to process integral problems in integer-typed values as much as possible. When you inevitably use decimals, be very careful about the errors.

#### 3. Solution using binary representation of an integer

Consider the binary representation of the integer.
For example, we have the conversions $$6=110_{(2)}$$ and $$15=1111_{(2)}$$.
Here, the inequality $$2^{k} \le N < 2^{k+1}$$ can be transformed into binary notations as follows.
$$1 \underbrace{ 00 \dots 0 }_{ k }\ _{(2)} \le N < 1 \underbrace{ 00 \dots 0 }_{ k+1 }\ _{(2)}$$
Using this property, we can derive the following solution.

• If the binary notation of $$N$$ (without leading $$0$$’s) has $$k$$ digits (that is, if the most significant bit with value $$1$$ is the $$k$$-th least significant bit), then the answer is $$k-1$$.

There are various ways to implement this, while using bit operations simplifies it. (Note that the least significant digit is treated as the $$0$$-th digit.)

#include<bits/stdc++.h>

using namespace std;

int main(){
long long n;
cin >> n;
for(int i=60;i>=0;i--){
if(n&(1ll<<i)){cout << i << '\n';break;}
}
return 0;
}


posted:
last update: