Как сделать целое число log2 () в C ++?

Question

В стандартных библиотеках C ++ я нашел только метод журнала с плавающей запятой. Теперь я использую журнал, чтобы найти уровень индекса в двоичном дереве (floor(2log(index))).

Код (C ++):

int targetlevel = int(log(index)/log(2));

Боюсь, что для некоторых краевых элементов (элементов со значением 2 ^ n) log вернет n-1.999999999999 вместо n.0. Этот страх правильный? Как я могу изменить свое утверждение так, чтобы оно всегда возвращало правильный ответ?

Answer 1

Эта функция определяет, сколько битов требуется для представления числового интервала: [0..maxvalue].

unsigned binary_depth( unsigned maxvalue )
   {
   int depth=0;
   while ( maxvalue ) maxvalue>>=1, depth++;
   return depth;
   }

Вычитая 1 из результата, вы получаете floor(log2(x)), что является точным представлением log2(x), когда x является степенью 2.

х у г-1 * ** 1022 тысяча двадцать одна тысяча двадцать три ** * 0 0 -1
1 1 0
* 1 042 * 2 * ** тысяча сорок-пять одна тысяча сорок-шесть * 2 * ** 1049 тысяча сорок-восемь * 1 * ** 1 051 1052 * 3 2 1
4 3 2
5 3 2
* +1078 * 6 3 * +1081 ** * 2 тысяча восемьдесят-дв
7 3 2
8 * +1094 ** ** +1096 1 095 * 4 * ** 1099 тысяча девяносто восемь * 3 * +1101 ** ** 1102 1103 *

Answer 2

Учитывая, как работают числа с плавающей запятой (грубо, мантисса * 2 ^ экспонента), тогда любое число до 2 ^ 127, которое является степенью 2, будет точно представлено без ошибок.

Это дает тривиальное, но довольно хакерское решение - интерпретировать битовую комбинацию числа с плавающей запятой как целое число и просто посмотреть на экспоненту. Это решение Дэвида Торнли выше.

float f = 1;
for (int i = 0; i < 128; i++)
{
    int x = (*(int*)(&f)>>23) - 127;
    int l = int(log(f) / log(2));

    printf("i = %d, log = %d, f = %f quick = %d\n",
        i, l, f, x);
    f *= 2;
}

Неверно, что любое целое число может быть представлено как число с плавающей запятой - только те, у которых меньше битов, чем у мантиссы. В 32-битных числах, это стоит 23 бита.

Answer 3

Переписывание Тодд Леман ответ будет более общим:

#include <climits>

template<typename N>
constexpr N ilog2(N n) {
    N i = 0;
    for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
        if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
    }
    return i;
}

Clang с -O3 разворачивает цикл:

0000000100000f50    pushq   %rbp
0000000100000f51    movq    %rsp, %rbp
0000000100000f54    xorl    %eax, %eax
0000000100000f56    cmpl    $0xffff, %edi
0000000100000f5c    setg    %al
0000000100000f5f    shll    $0x4, %eax
0000000100000f62    movl    %eax, %ecx
0000000100000f64    sarl    %cl, %edi
0000000100000f66    xorl    %edx, %edx
0000000100000f68    cmpl    $0xff, %edi
0000000100000f6e    setg    %dl
0000000100000f71    leal    (,%rdx,8), %ecx
0000000100000f78    sarl    %cl, %edi
0000000100000f7a    leal    (%rax,%rdx,8), %eax
0000000100000f7d    xorl    %edx, %edx
0000000100000f7f    cmpl    $0xf, %edi
0000000100000f82    setg    %dl
0000000100000f85    leal    (,%rdx,4), %ecx
0000000100000f8c    sarl    %cl, %edi
0000000100000f8e    leal    (%rax,%rdx,4), %eax
0000000100000f91    xorl    %edx, %edx
0000000100000f93    cmpl    $0x3, %edi
0000000100000f96    setg    %dl
0000000100000f99    leal    (%rdx,%rdx), %ecx
0000000100000f9c    sarl    %cl, %edi
0000000100000f9e    leal    (%rax,%rdx,2), %ecx
0000000100000fa1    xorl    %eax, %eax
0000000100000fa3    cmpl    $0x1, %edi
0000000100000fa6    setg    %al
0000000100000fa9    orl %ecx, %eax
0000000100000fab    popq    %rbp

Когда n является константой, результат вычисляется во время компиляции.

Answer 4

Это старый пост, но я разделяю мой однострочный алгоритм:

unsigned uintlog2(unsigned x)
{
   unsigned l;
   for(l=0; x>1; x>>=1, l++);
   return l;
} 

Answer 5

Эту функцию я написал здесь

// The 'i' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
  unsigned int log2Val = 0 ;
  // Count push off bits to right until 0
  // 101 => 10 => 1 => 0
  // which means hibit was 3rd bit, its value is 2^3
  while( x>>=1 ) log2Val++;  // div by 2 until find log2.  log_2(63)=5.97, so
  // take that as 5, (this is a traditional integer function!)
  // eg x=63 (111111), log2Val=5 (last one isn't counted by the while loop)
  return log2Val ;
}

Answer 6

Насколько глубоко вы проецируете свое дерево? Вы можете установить диапазон скажем ... +/- 0.00000001 для числа, чтобы сделать его целочисленным.

На самом деле я не уверен, что вы наберете число, например 1.99999999, потому что ваш log2 не должен терять точность при вычислении 2 ^ n значений (поскольку с плавающей запятой округляется до ближайшей степени 2).