Блог

Учитывая n = 2 ^ k, как я могу найти k, предполагая, что n является 32-разрядным целым числом, используя C / C побитово?

В GCC есть __builtin_clz , который преобразует в BSR на x86 / x64, CLZ на ARM и т.д. И эмулирует инструкцию, если аппаратное обеспечение ее не реализует.
В Visual C 2005 и выше есть _BitScanReverse .

Используя эти функции, вы можете получить свой k

В Википедии написано, как это сделать, используя побитовые операторы:

 /**
 * Returns the floor form of binary logarithm for a 32 bit integer.
 * −1 is returned if ''n'' is 0.
 */
int floorLog2(unsigned int n) {
  if (n == 0)
    return -1;

  int pos = 0;
  if (n >= 1<<16) { n >>= 16; pos  = 16; }
  if (n >= 1<< 8) { n >>=  8; pos  =  8; }
  if (n >= 1<< 4) { n >>=  4; pos  =  4; }
  if (n >= 1<< 2) { n >>=  2; pos  =  2; }
  if (n >= 1<< 1) {           pos  =  1; }
  return pos;
}
  

Код взят из: Википедия на тему: Двоичный логарифм с тех пор эта страница была изменена, оригинальную версию с примером кода все еще можно найти на ней: Википедия на тему: Двоичный логарифм (24 мая 2011)

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

 unsigned log2(unsigned x)
{
    float f = x;
    memcpy(amp;x, amp;f, sizeof x);
    return (x >> 23) - 127;
}
  

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

И просто для развлечения, вот совершенно другое, относительно простое решение:

 unsigned log2(unsigned x)
{
    unsigned exp = 0;
    for (; ;)
    {
        switch (x)
        {
            case 128:   exp;
            case 64:   exp;
            case 32:   exp;
            case 16:   exp;
            case 8:   exp;
            case 4:   exp;
            case 2:   exp;
            case 1: return exp;
            case 0: throw "illegal input detected";
        }
        x >>= 8;
        exp  = 8;
    }
}
  

И вот полностью развернутое решение:

 #define CASE(exp) case (1 << (exp)) : return (exp);

unsigned log2(unsigned x)
{
    switch (x)
    {
        CASE(31) CASE(30) CASE(29) CASE(28)
        CASE(27) CASE(26) CASE(25) CASE(24)
        CASE(23) CASE(22) CASE(21) CASE(20)
        CASE(19) CASE(18) CASE(17) CASE(16)
        CASE(15) CASE(14) CASE(13) CASE(12)
        CASE(11) CASE(10) CASE( 9) CASE( 8)
        CASE( 7) CASE( 6) CASE( 5) CASE( 4)
        CASE( 3) CASE( 2) CASE( 1) CASE( 0)
        default: throw "illegal input";
    }
}
  

продолжайте сдвигать значение n вправо, пока не получите 1. подсчитайте количество требуемых сдвигов вправо.

Для переносимого решения (не прибегая к специфичным для реализации материалам) вы можете использовать binary chop, который, вероятно, является одним из наиболее эффективных способов, не связанных с непереносимыми материалами. Допустим, ваше целое число равно 8 битам:

 // Given n = 2^k, k >= 0, returns k.

unsigned int getK (unsigned int n) {
    if (n <= 8) {
        if (n <= 2) {
            if (n == 1) return 0;
            return 1;
        }
        if (n == 4) return 2;
        return 3;
    }
    if (n <= 32) {
        if (n == 16) return 4;
        return 5;
    }
    if (n == 64) return 6;
    return 7;
}
  

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

Дано: 0 <= n <= 2**32 это означает 0 <= k <= 32 , что k может быть представлено байтом. Объем оперативной памяти в 2 ** 32 байта в общем случае не является чрезмерным, поэтому самым быстрым методом вычисления вполне может быть простой поиск по таблице.

Если вы используете GCC, я предполагаю, что это самый быстрый способ:

 int ilog2(int value) {
 return 31 - __builtin_clz(value);
}
  

Где __builtin_clz — оптимизированная встроенная функция GCC.