Вычислить быстрый потолок базы 2 - PullRequest
Новая
       45

Вычислить быстрый потолок базы 2

38 голосов
/ 17 июля 2010

Что такое быстрый способ вычисления (long int) ceiling(log_2(i)), где входные и выходные данные представляют собой 64-разрядные целые числа? Решения для целых чисел со знаком или без знака являются приемлемыми. Я подозреваю, что лучшим способом будет метод «немного перепутать», подобный найденным здесь , но вместо того, чтобы пытаться самостоятельно, я хотел бы использовать что-то, что уже хорошо протестировано. Общее решение будет работать для всех положительных значений.

Например, значения для 2,3,4,5,6,7,8: 1,2,2,3,3,3,3

Редактировать: Пока что наилучшим маршрутом, по-видимому, является вычисление целочисленной / минимальной базы 2 (позиция MSB) с использованием любого количества быстрых существующих битхаков или методов регистров, а затем добавление одного, если вход не сила двух. Быстрая битовая проверка для степеней двойки - (n&(n-1)).

Редактировать 2: Хороший источник по целочисленным логарифмам и методам начальных нулей - разделы 5-3 и 11-4 в Восторг Хакера Генри Уоррена. Это самое полное лечение, которое я нашел.

Редактировать 3: эта техника выглядит многообещающе: https://stackoverflow.com/a/51351885/365478

Ответы [ 14 ]

19 голосов
/ 11 марта 2013

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

19 голосов
/ 17 июля 2010

Если вы можете ограничить себя gcc, есть набор встроенных функций, которые возвращают количество начальных нулевых битов и могут быть использованы для выполнения того, что вы хотите с небольшой работой: 

int __builtin_clz (unsigned int x)
int __builtin_clzl (unsigned long)
int __builtin_clzll (unsigned long long)
10 голосов
/ 17 июля 2010

Если вы компилируете для 64-битных процессоров в Windows, я думаю, что это должно сработать._BitScanReverse64 является встроенной функцией. 

#include <intrin.h>
__int64 log2ceil( __int64 x )
{
  unsigned long index;
  if ( !_BitScanReverse64( &index, x ) )
     return -1LL; //dummy return value for x==0

  // add 1 if x is NOT a power of 2 (to do the ceil)
  return index + (x&(x-1)?1:0);
}

Для 32-разрядных систем вы можете эмулировать _BitScanReverse64 с помощью одного или двух вызовов _BitScanReverse.Проверьте старшие 32 бита x, ((long *) & x) [1], затем младшие 32 бита, если необходимо, ((long *) & x) [0].

5 голосов
/ 10 мая 2012

Используя встроенные gcc, упомянутые @egosys, вы можете создать несколько полезных макросов.Для быстрого и грубого расчета пола (log2 (x)) вы можете использовать: 

#define FAST_LOG2(x) (sizeof(unsigned long)*8 - 1 - __builtin_clzl((unsigned long)(x)))

Для аналогичного потолка (log2 (x)) используйте: 

#define FAST_LOG2_UP(x) (((x) - (1 << FAST_LOG2(x))) ? FAST_LOG2(x) + 1 : FAST_LOG2(x))

Последнийможет быть дополнительно оптимизирован с использованием большего числа особенностей gcc, чтобы избежать двойного вызова встроенного, но я не уверен, что вам это нужно здесь.

5 голосов
/ 03 августа 2010 
#include "stdafx.h"
#include "assert.h"

int getpos(unsigned __int64 value)
{
    if (!value)
    {
      return -1; // no bits set
    }
    int pos = 0;
    if (value & (value - 1ULL))
    {
      pos = 1;
    }
    if (value & 0xFFFFFFFF00000000ULL)
    {
      pos += 32;
      value = value >> 32;
    }
    if (value & 0x00000000FFFF0000ULL)
    {
      pos += 16;
      value = value >> 16;
    }
    if (value & 0x000000000000FF00ULL)
    {
      pos += 8;
      value = value >> 8;
    }
    if (value & 0x00000000000000F0ULL)
    {
      pos += 4;
      value = value >> 4;
    }
    if (value & 0x000000000000000CULL)
    {
      pos += 2;
      value = value >> 2;
    }
    if (value & 0x0000000000000002ULL)
    {
      pos += 1;
      value = value >> 1;
    }
    return pos;
}

int _tmain(int argc, _TCHAR* argv[])
{    
    assert(getpos(0ULL) == -1); // None bits set, return -1.
    assert(getpos(1ULL) == 0);
    assert(getpos(2ULL) == 1);
    assert(getpos(3ULL) == 2);
    assert(getpos(4ULL) == 2);
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos(1ULL << k);
        assert(pos == k);
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) - 1);
        assert(pos == (k < 2 ? k - 1 : k) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) | 1);
        assert(pos == (k < 1 ? k : k + 1) );
    }
    for (int k = 0; k < 64; ++k)
    {
        int pos = getpos( (1ULL << k) + 1);
        assert(pos == k + 1);
    }
    return 0;
}
4 голосов
/ 15 июля 2018

Самый быстрый из известных мне подходов использует быстрый log2, который округляет, комбинированную безусловную настройку входного значения до и после для обработки случая округления, как в lg_down(), показанном ниже. 

/* base-2 logarithm, rounding down */
static inline uint64_t lg_down(uint64_t x) {
  return 63U - __builtin_clzl(x);
}

/* base-2 logarithm, rounding up */
static inline uint64_t lg_up(uint64_t x) {
  return lg_down(x - 1) + 1;
}

По существу, добавление 1 к округленному результату уже корректно для всех значений, кроме точных степеней двух (поскольку в этом случае подходы floor и ceil должны возвращать один и тот же ответ), поэтому достаточно вычесть 1 из входного значения, чтобы обработать этот случай (он не меняет ответ для других случаев) и добавить один к результату.

Это обычно немного быстрее, чем подходы, которые корректируют значение путем явной проверки точных степеней двух (например, добавление члена !!(x & (x - 1))). Он избегает любых сравнений и условных операций или переходов, более вероятен просто при встраивании, более поддается векторизации и т. Д.

Это основывается на функциональности «подсчитывать начальные биты», предлагаемой большинством процессоров, использующих встроенный __builtin_clzl clang / icc / gcc, но другие платформы предлагают нечто подобное (например, встроенный в Visual Studio BitScanReverse).

К сожалению, многие из них возвращают неправильный ответ для log(1), поскольку это приводит к __builtin_clzl(0), что является неопределенным поведением, основанным на документации gcc. Конечно, общая функция «считать ведущие нули» имеет абсолютно определенное поведение в нуле, но встроенная функция gcc определяется таким образом, поскольку до расширения ISA BMI на x86 она использовала бы инструкцию bsr который сам по себе имеет неопределенное поведение.

Вы можете обойти это, если знаете, что у вас есть инструкция lzcnt, напрямую используя lzcnt. Большинство платформ, кроме x86, никогда не сталкивались с ошибкой bsr, и, вероятно, также предлагают методы для доступа к своей инструкции «считать ведущие нули», если она есть.

4 голосов
/ 12 января 2014

Следующий фрагмент кода является безопасным и переносимым способом расширения методов plain-C, таких как @ dgobbi, для использования встроенных функций компилятора при компиляции с использованием поддерживающих компиляторов (Clang).Размещение этого в верхней части метода приведет к тому, что метод будет использовать встроенную функцию, когда она будет доступна.Когда встроенная функция недоступна, метод возвращается к стандартному коду C. 

#ifndef __has_builtin
#define __has_builtin(x) 0
#endif

#if __has_builtin(__builtin_clzll) //use compiler if possible
  return ((sizeof(unsigned long long) * 8 - 1) - __builtin_clzll(x)) + (!!(x & (x - 1)));
#endif
3 голосов
/ 18 июля 2010

Самое быстрое решение true :

Двоичное дерево поиска из 63 записей.Это степени 2 от 0 до 63. Функция одноразовой генерации для создания дерева.Листья представляют собой логарифмическую базу 2 степеней (в основном, числа 1-63).

Чтобы найти ответ, вы вводите число в дерево и переходите к узлу листа больше, чем элемент.Если узел листа в точности равен, результатом является значение листа.В противном случае результатом является значение листа + 1.

Сложность фиксируется на O (6).

2 голосов
/ 17 июля 2010

Нахождение логической базы 2 целого числа (64-битного или любого другого бита) с целочисленным выводом эквивалентно нахождению старшего значащего бита, который установлен. Зачем? Поскольку база журнала 2 - это сколько раз вы можете разделить число на 2, чтобы достичь 1.

Один из способов найти установленный MSB - просто сдвигать бит вправо на 1 каждый раз, пока у вас не будет 0. Другой более эффективный способ - выполнить какой-либо двоичный поиск с помощью битовых масок.

Часть ceil легко обрабатывается, проверяя, установлены ли какие-либо другие биты, кроме MSB.

1 голос
/ 19 февраля 2019

Я протестировал несколько реализаций 64-битного «старшего бита».Самый «бесплатный» код на самом деле не самый быстрый.

Это мой highest-bit.c исходный файл: 

int highest_bit_unrolled(unsigned long long n)
{
  if (n & 0xFFFFFFFF00000000) {
    if (n & 0xFFFF000000000000) {
      if (n & 0xFF00000000000000) {
        if (n & 0xF000000000000000) {
          if (n & 0xC000000000000000)
            return (n & 0x8000000000000000) ? 64 : 63;
          else
            return (n & 0x2000000000000000) ? 62 : 61;
        } else {
          if (n & 0x0C00000000000000)
            return (n & 0x0800000000000000) ? 60 : 59;
          else
            return (n & 0x0200000000000000) ? 58 : 57;
        }
      } else {
        if (n & 0x00F0000000000000) {
          if (n & 0x00C0000000000000)
            return (n & 0x0080000000000000) ? 56 : 55;
          else
            return (n & 0x0020000000000000) ? 54 : 53;
        } else {
          if (n & 0x000C000000000000)
            return (n & 0x0008000000000000) ? 52 : 51;
          else
            return (n & 0x0002000000000000) ? 50 : 49;
        }
      }
    } else {
      if (n & 0x0000FF0000000000) {
        if (n & 0x0000F00000000000) {
          if (n & 0x0000C00000000000)
            return (n & 0x0000800000000000) ? 48 : 47;
          else
            return (n & 0x0000200000000000) ? 46 : 45;
        } else {
          if (n & 0x00000C0000000000)
            return (n & 0x0000080000000000) ? 44 : 43;
          else
            return (n & 0x0000020000000000) ? 42 : 41;
        }
      } else {
        if (n & 0x000000F000000000) {
          if (n & 0x000000C000000000)
            return (n & 0x0000008000000000) ? 40 : 39;
          else
            return (n & 0x0000002000000000) ? 38 : 37;
        } else {
          if (n & 0x0000000C00000000)
            return (n & 0x0000000800000000) ? 36 : 35;
          else
            return (n & 0x0000000200000000) ? 34 : 33;
        }
      }
    }
  } else {
    if (n & 0x00000000FFFF0000) {
      if (n & 0x00000000FF000000) {
        if (n & 0x00000000F0000000) {
          if (n & 0x00000000C0000000)
            return (n & 0x0000000080000000) ? 32 : 31;
          else
            return (n & 0x0000000020000000) ? 30 : 29;
        } else {
          if (n & 0x000000000C000000)
            return (n & 0x0000000008000000) ? 28 : 27;
          else
            return (n & 0x0000000002000000) ? 26 : 25;
        }
      } else {
        if (n & 0x0000000000F00000) {
          if (n & 0x0000000000C00000)
            return (n & 0x0000000000800000) ? 24 : 23;
          else
            return (n & 0x0000000000200000) ? 22 : 21;
        } else {
          if (n & 0x00000000000C0000)
            return (n & 0x0000000000080000) ? 20 : 19;
          else
            return (n & 0x0000000000020000) ? 18 : 17;
        }
      }
    } else {
      if (n & 0x000000000000FF00) {
        if (n & 0x000000000000F000) {
          if (n & 0x000000000000C000)
            return (n & 0x0000000000008000) ? 16 : 15;
          else
            return (n & 0x0000000000002000) ? 14 : 13;
        } else {
          if (n & 0x0000000000000C00)
            return (n & 0x0000000000000800) ? 12 : 11;
          else
            return (n & 0x0000000000000200) ? 10 : 9;
        }
      } else {
        if (n & 0x00000000000000F0) {
          if (n & 0x00000000000000C0)
            return (n & 0x0000000000000080) ? 8 : 7;
          else
            return (n & 0x0000000000000020) ? 6 : 5;
        } else {
          if (n & 0x000000000000000C)
            return (n & 0x0000000000000008) ? 4 : 3;
          else
            return (n & 0x0000000000000002) ? 2 : (n ? 1 : 0);
        }
      }
    }
  }
}

int highest_bit_bs(unsigned long long n)
{
  const unsigned long long mask[] = {
    0x000000007FFFFFFF,
    0x000000000000FFFF,
    0x00000000000000FF,
    0x000000000000000F,
    0x0000000000000003,
    0x0000000000000001
  };
  int hi = 64;
  int lo = 0;
  int i = 0;

  if (n == 0)
    return 0;

  for (i = 0; i < sizeof mask / sizeof mask[0]; i++) {
    int mi = lo + (hi - lo) / 2;

    if ((n >> mi) != 0)
      lo = mi;
    else if ((n & (mask[i] << lo)) != 0)
      hi = mi;
  }

  return lo + 1;
}

int highest_bit_shift(unsigned long long n)
{
  int i = 0;
  for (; n; n >>= 1, i++)
    ; /* empty */
  return i;
}

static int count_ones(unsigned long long d)
{
  d = ((d & 0xAAAAAAAAAAAAAAAA) >>  1) + (d & 0x5555555555555555);
  d = ((d & 0xCCCCCCCCCCCCCCCC) >>  2) + (d & 0x3333333333333333);
  d = ((d & 0xF0F0F0F0F0F0F0F0) >>  4) + (d & 0x0F0F0F0F0F0F0F0F);
  d = ((d & 0xFF00FF00FF00FF00) >>  8) + (d & 0x00FF00FF00FF00FF);
  d = ((d & 0xFFFF0000FFFF0000) >> 16) + (d & 0x0000FFFF0000FFFF);
  d = ((d & 0xFFFFFFFF00000000) >> 32) + (d & 0x00000000FFFFFFFF);
  return d;
}

int highest_bit_parallel(unsigned long long n)
{
  n |= n >> 1;
  n |= n >> 2;
  n |= n >> 4;
  n |= n >> 8;
  n |= n >> 16;
  n |= n >> 32;
  return count_ones(n);
}

int highest_bit_so(unsigned long long x)
{
  static const unsigned long long t[6] = {
    0xFFFFFFFF00000000ull,
    0x00000000FFFF0000ull,
    0x000000000000FF00ull,
    0x00000000000000F0ull,
    0x000000000000000Cull,
    0x0000000000000002ull
  };

  int y = (((x & (x - 1)) == 0) ? 0 : 1);
  int j = 32;
  int i;

  for (i = 0; i < 6; i++) {
    int k = (((x & t[i]) == 0) ? 0 : j);
    y += k;
    x >>= k;
    j >>= 1;
  }

  return y;
}

int highest_bit_so2(unsigned long long value)
{
  int pos = 0;
  if (value & (value - 1ULL))
  {
    pos = 1;
  }
  if (value & 0xFFFFFFFF00000000ULL)
  {
    pos += 32;
    value = value >> 32;
  }
  if (value & 0x00000000FFFF0000ULL)
  {
    pos += 16;
    value = value >> 16;
  }
  if (value & 0x000000000000FF00ULL)
  {
    pos += 8;
    value = value >> 8;
  }
  if (value & 0x00000000000000F0ULL)
  {
    pos += 4;
    value = value >> 4;
  }
  if (value & 0x000000000000000CULL)
  {
    pos += 2;
    value = value >> 2;
  }
  if (value & 0x0000000000000002ULL)
  {
    pos += 1;
    value = value >> 1;
  }
  return pos;
}

Это highest-bit.h: 

int highest_bit_unrolled(unsigned long long n);
int highest_bit_bs(unsigned long long n);
int highest_bit_shift(unsigned long long n);
int highest_bit_parallel(unsigned long long n);
int highest_bit_so(unsigned long long n);
int highest_bit_so2(unsigned long long n);

И основная программа (извините за все, что скопировали и вставили): 

#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include "highest-bit.h"

double timedelta(clock_t start, clock_t end)
{
  return (end - start)*1.0/CLOCKS_PER_SEC;
}

int main(int argc, char **argv)
{
  int i;
  volatile unsigned long long v;
  clock_t start, end;

  start = clock();

  for (i = 0; i < 10000000; i++) {
    for (v = 0x8000000000000000; v; v >>= 1)
      highest_bit_unrolled(v);
  }

  end = clock();

  printf("highest_bit_unrolled = %6.3fs\n", timedelta(start, end));

  start = clock();

  for (i = 0; i < 10000000; i++) {
    for (v = 0x8000000000000000; v; v >>= 1)
      highest_bit_parallel(v);
  }

  end = clock();

  printf("highest_bit_parallel = %6.3fs\n", timedelta(start, end));

  start = clock();

  for (i = 0; i < 10000000; i++) {
    for (v = 0x8000000000000000; v; v >>= 1)
      highest_bit_bs(v);
  }

  end = clock();

  printf("highest_bit_bs = %6.3fs\n", timedelta(start, end));

  start = clock();

  for (i = 0; i < 10000000; i++) {
    for (v = 0x8000000000000000; v; v >>= 1)
      highest_bit_shift(v);
  }

  end = clock();

  printf("highest_bit_shift = %6.3fs\n", timedelta(start, end));

  start = clock();

  for (i = 0; i < 10000000; i++) {
    for (v = 0x8000000000000000; v; v >>= 1)
      highest_bit_so(v);
  }

  end = clock();

  printf("highest_bit_so = %6.3fs\n", timedelta(start, end));

  start = clock();

  for (i = 0; i < 10000000; i++) {
    for (v = 0x8000000000000000; v; v >>= 1)
      highest_bit_so2(v);
  }

  end = clock();

  printf("highest_bit_so2 = %6.3fs\n", timedelta(start, end));

  return 0;
}

Я пробовал разные Intel x86 коробки, старые и новые.

highest_bit_unrolled(развернутый бинарный поиск) значительно быстрее, чем highest_bit_parallel (битовые операции без ответвлений).Это быстрее, чем highest_bit_bs (цикл двоичного поиска), и, в свою очередь, быстрее, чем highest_bit_shift (цикл наивного сдвига и подсчета).

highest_bit_unrolled также быстрее, чем тот, который принят вОтвет SO (highest_bit_so), а также ответ, данный в другом ответе (highest_bit_so2).

В тесте циклически проходит однобитовая маска, которая охватывает последовательные биты.Это делается для того, чтобы попытаться опровергнуть предсказание ветвления в развернутом бинарном поиске, что является реалистичным: в реальной программе входные регистры вряд ли будут демонстрировать локальность положения бита.

Вот результаты для старого Intel(R) Core(TM)2 Duo CPU E4500 @ 2.20GHz: 

$ ./highest-bit
highest_bit_unrolled =  6.090s
highest_bit_parallel =  9.260s
highest_bit_bs = 19.910s
highest_bit_shift = 21.130s
highest_bit_so =  8.230s
highest_bit_so2 =  6.960s

На более новой модели Intel(R) Core(TM) i7-6700K CPU @ 4.00GHz: 

highest_bit_unrolled =  1.555s
highest_bit_parallel =  3.420s
highest_bit_bs =  6.486s
highest_bit_shift =  9.505s
highest_bit_so =  4.127s
highest_bit_so2 =  1.645s

На более новом оборудовании highest_bit_so2 приближается к highest_bit_unrolled на более новом оборудовании.Порядок не совсем то же самое;теперь highest_bit_so действительно отстает и медленнее, чем highest_bit_parallel.

Самый быстрый, highest_bit_unrolled содержит больше всего кода с наибольшим количеством ветвей.Каждое возвращаемое значение, достигаемое различным набором условий со своим собственным выделенным фрагментом кода.

Интуиция «избегать всех ветвей» (из-за опасений по поводу неправильных предсказаний ветвлений) не всегда верна.Современные (и даже не очень современные) процессоры содержат значительные хитрости, чтобы не мешать их ветвлению.

PS highest_bit_unrolled был введен на языке TXR в декабре2011 (с ошибками после отладки).

В последнее время я начал задумываться о том, не может ли какой-нибудь более приятный, более компактный код без веток работать быстрее.

Я несколько удивленрезультаты.

Возможно, код действительно должен быть #ifdef для GNU C и использовать некоторые примитивы компилятора, но что касается переносимости, эта версия остается.

Страница:
...