Как сделать целое число 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

Если вы работаете на платформе 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;
}

Answer 2

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

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

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

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

Answer 3

Если вам нужна операция быстрого целочисленного журнала ₂ , следующая функция 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), доступных из здесь . Я бы не советовал использовать их, если скорость не имеет значения (я сам предпочитаю удобочитаемость), но вы должны знать, что они существуют.

Answer 4

Целочисленный логарифм Base-2

Вот что я делаю для 64-битных целых чисел без знака. Это вычисляет пол логарифма base-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); при входе в функцию.

Целочисленный логарифм Base-10

Целочисленные логарифмы Base-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
}

Answer 5

Это было предложено в комментариях выше. Использование встроенных 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);
}

Answer 6

У меня никогда не было проблем с точностью с плавающей точкой в ​​используемой формуле (и быстрая проверка чисел от 1 до 2 ³¹ - 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; 
}

Answer 7

Есть похожие ответы выше. Этот ответ

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;

Answer 8

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

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

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

Answer 9

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

Answer 10

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

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