Блог пользователя Hz_

Автор Hz_, 6 лет назад, По-английски

Today I puzzled to find out the value of log2((2^59)-1). Here, (2^59)-1 = 576460752303423487. We know that the value of log2(4)=2, log2(3)=1.58496 and log2(576460752303423488)=59 but why log2(576460752303423487)=59 when log2(x)=y and x=2^y. This happens not only for (2^59)-1 but also for other values.

(I searched about it on google but couldn't find out the reason behind this.)

  • Проголосовать: нравится
  • +10
  • Проголосовать: не нравится

»
6 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +35 Проголосовать: не нравится

Precision error?

$$$log2$$$ is a double function, which means precision error could occur.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится -37 Проголосовать: не нравится

Because $$$log(x)$$$ in Competitive Programming is usually equal to $$$y$$$ where $$$y$$$ is the smallest integer such that $$$2^y \gt = x$$$.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

This is because of precision error. The answer you are looking for is 58.9999999999999999975 A double variable cannot store these many decimal places. So it rounds it off to 59

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

You can also use __builtin_clzll, which should be faster than a loop.

»
6 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Use log2l

»
6 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

https://ideone.com/HcgbhH More to think about