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

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

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

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

Угловой случай - это когда index равен 0. Вам, вероятно, следует проверить его отдельно и выбросить исключение или вернуть ошибку, если index == 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;
}

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

Начиная с C ++ 20 вы можете использовать

std::bit_width(index) - 1

Очень короткий, компактный, быстрый и читаемый.

Он следует той же идее, что и ответ, предоставленный Игорем Кривоконем.

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

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

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

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

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

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

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

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..maxvalue].

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

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

x y y-1
0 0 -1
1 1 0
2 2 1 < / strong>
3 2 1
4 3 2
5 3 2
6 3 2
7 3 2
8 4 3