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

StackOverflow https://stackoverflow.com/questions/994593

Вопрос

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

Код (С++):

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

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

Это было полезно?

Решение

Вместо этого вы можете использовать этот метод:

int targetlevel = 0;
while (index >>= 1) ++targetlevel;

Примечание:это изменит index.Если он вам нужен без изменений, создайте еще один временный int.

Крайний случай — когда индекс равен 0.Вероятно, вам следует проверить это отдельно и выдать исключение или вернуть ошибку, если индекс == 0.

Другие советы

Если вы используете новейшую платформу x86 или x86-64 (а вы, вероятно, так и есть), используйте команду bsr инструкция, которая вернет позицию старшего установленного бита в беззнаковом целом числе.Оказывается, это то же самое, что и log2().Вот короткая функция C или C++, которая вызывает bsr используя встроенный ASM:

#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
  uint32_t y;
  asm ( "\tbsr %1, %0\n"
      : "=r"(y)
      : "r" (x)
  );
  return y;
}

Если вам просто нужен быстрый целочисленный журнал2 операция, следующая функция mylog2() сделает это, не беспокоясь о точности чисел с плавающей запятой:

#include <limits.h>

static unsigned int mylog2 (unsigned int val) {
    if (val == 0) return UINT_MAX;
    if (val == 1) return 0;
    unsigned int ret = 0;
    while (val > 1) {
        val >>= 1;
        ret++;
    }
    return ret;
}

#include <stdio.h>

int main (void) {
    for (unsigned int i = 0; i < 20; i++)
        printf ("%u -> %u\n", i, mylog2(i));
    putchar ('\n');
    for (unsigned int i = 0; i < 10; i++)
        printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));
    return 0;
}

В приведенном выше коде также есть небольшая тестовая программа, позволяющая проверить поведение:

0 -> 4294967295
1 -> 0
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 2
8 -> 3
9 -> 3
10 -> 3
11 -> 3
12 -> 3
13 -> 3
14 -> 3
15 -> 3
16 -> 4
17 -> 4
18 -> 4
19 -> 4

4294967286 -> 31
4294967287 -> 31
4294967288 -> 31
4294967289 -> 31
4294967290 -> 31
4294967291 -> 31
4294967292 -> 31
4294967293 -> 31
4294967294 -> 31
4294967295 -> 31

Оно вернется UINT_MAX для входного значения 0 как признака неопределенного результата, так что это то, что вам следует проверить (ни одно допустимое целое число без знака не будет иметь такой высокий логарифм).

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

Целочисленный логарифм по основанию 2

Вот что я делаю для 64-битных беззнаковых целых чисел.При этом вычисляется нижний предел логарифма по основанию 2, который эквивалентен индексу старшего бита.Этот метод невероятно быстро для больших чисел, поскольку он использует развернутый цикл, который всегда выполняется за log₂64 = 6 шагов.

По сути, он вычитает все меньшие квадраты в последовательности { 0 ≤ k ≤ 5:2^(2^k) } = { 2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹ } = { 4294967296, 65536, 256, 16, 4, 2, 1 } и суммирует показатели степени k вычтенных значений.

int uint64_log2(uint64_t n)
{
  #define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }

  int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;

  #undef S
}

Обратите внимание, что это возвращает –1, если введено недопустимое значение 0 (именно это было первоначальное значение). -(n == 0) проверяет).Если вы никогда не ожидаете вызвать его с помощью n == 0, вы можете заменить int i = 0; для инициализатора и добавьте assert(n != 0); при входе в функцию.

Целочисленный логарифм по основанию 10

Целочисленные логарифмы по основанию 10 можно вычислить аналогичным образом — при этом наибольший квадрат для проверки равен 10¹⁶, потому что log₁₀2⁶⁴ ≅ 19,2659...

int uint64_log10(uint64_t n)
{
  #define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }

  int i = -(n == 0);
  S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
  return i;

  #undef S
}

Это было предложено в комментариях выше.Использование встроенных функций gcc:

static inline int log2i(int x) {
    assert(x > 0);

    return sizeof(int) * 8 - __builtin_clz(x) - 1;
}

static void test_log2i(void) {
    assert_se(log2i(1) == 0);
    assert_se(log2i(2) == 1);
    assert_se(log2i(3) == 1);
    assert_se(log2i(4) == 2);
    assert_se(log2i(32) == 5);
    assert_se(log2i(33) == 5);
    assert_se(log2i(63) == 5);
    assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
}

У меня никогда не было проблем с точностью чисел с плавающей запятой в используемой вами формуле (и быстрой проверкой чисел от 1 до 2).31 - 1 не нашел ошибок), но если вы беспокоитесь, вместо этого вы можете использовать эту функцию, которая возвращает те же результаты и работает примерно на 66% быстрее в моих тестах:

int HighestBit(int i){
    if(i == 0)
        return -1;

    int bit = 31;
    if((i & 0xFFFFFF00) == 0){
        i <<= 24;
        bit = 7;
    }else if((i & 0xFFFF0000) == 0){
        i <<= 16;
        bit = 15;
    }else if((i & 0xFF000000) == 0){
        i <<= 8;
        bit = 23;
    }

    if((i & 0xF0000000) == 0){
        i <<= 4;
        bit -= 4;
    }

    while((i & 0x80000000) == 0){
        i <<= 1;
        bit--;
    }

    return bit; 
}

int targetIndex = floor(log(i + 0.5)/log(2.0));

Это не стандартно и не обязательно портативно, но в целом будет работать.Я не знаю, насколько это эффективно.

Преобразуйте целочисленный индекс в число с плавающей запятой достаточной точности.Представление будет точным, если точность достаточна.

Найдите представление чисел с плавающей запятой IEEE, извлеките показатель степени и внесите необходимые изменения, чтобы найти журнал по основанию 2.

Если вы используете C++11, вы можете сделать это функцией constexpr:

constexpr std::uint32_t log2(std::uint32_t n)
{
    return (n > 1) ? 1 + log2(n >> 1) : 0;
}

Подобные ответы есть выше.Этот ответ

  1. Работает с 64-битными числами.
  2. Позволяет выбрать тип округления и
  3. Включает тестовый/пример кода

Функции:

    static int floorLog2(int64_t x)
    { 
      assert(x > 0);
      return 63 - __builtin_clzl(x);
    }

    static int ceilLog2(int64_t x)
    {
      if (x == 1)
        // On my system __builtin_clzl(0) returns 63.  64 would make more sense   
        // and would be more consistent.  According to stackoverflow this result  
        // can get even stranger and you should just avoid __builtin_clzl(0).     
        return 0;
      else
        return floorLog2(x-1) + 1;
    }

Тестовый код:

for (int i = 1; i < 35; i++)
  std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
           <<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;

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

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

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

Иксйу-1
00-1
110
221
321
432
532
632
732
843

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

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

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

// 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 ;
}

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

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

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

#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;
}

Звон с -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 является константой, результат вычисляется во время компиляции.

Учитывая способ работы чисел с плавающей запятой (грубо говоря, мантисса * 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 бита.

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top