Какой самый быстрый способ изменить степень двойки в С? - PullRequest
Новая
       24

Какой самый быстрый способ изменить степень двойки в С?

0 голосов
/ 16 мая 2019

В уравнении: 2^x=a

Какой самый быстрый способ на языке C найти x с заданной степенью двойного значения (a)?

Редактировать :

  1. Математическое точное решение: log2(x)
  2. As ( a ) представляет собой положительное целое число и степень двойки (без рационального числа, не равного нулю), эта проблема может быть упрощена как "поиск позиции установленного бита" .
  3. Эта статья посвященаоблегченные встроенные процессорные системы.Например: ARM CORTEX M4.

a to x результаты: 

  a | x
 -------
  1 | 0
  2 | 1
  4 | 2
  8 | 3
 16 | 4
 32 | 5
 64 | 6
128 | 7
256 | 8
512 | 9
...

Опция 1: грязная петля 

unsigned int get_power_of_two_exponent(unsigned int value)
{
    unsigned int x = 0;

    while( ( 1 << x ) != value)
    {
        x ++;
    }

return x;
}

Вариант 2: странный трюк 

#include <stdint.h>

#if defined(__GNUC__)
static int highest_bit_set(uint32_t value)
{
    if (sizeof (unsigned int) == sizeof value)
        return 31 - __builtin_clz(value);
    else
    if (sizeof (unsigned long) == sizeof value)
        return 31 - __builtin_clzl(value);
    else
        exit(127); /* Weird architecture! */
}
#endif

Есть ли более быстрые варианты?

Ответы [ 6 ]

4 голосов
/ 16 мая 2019

Самый быстрый в C - это почти всегда справочные таблицы за счет использования памяти.Предполагая, что значение всегда равно степени 2, вы можете создать справочную таблицу следующим образом: 

uint8_t get_exponent (uint8_t val)
{
  static const uint8_t byte[256] = 
  {
    [1]   = 0,
    [2]   = 1,
    [4]   = 2,
    [8]   = 3,
    [16]  = 4,
    [32]  = 5,
    [64]  = 6,
    [128] = 7,
  };

  return byte[val & 0xFF];
}

Она вернет 0, если вы передадите значение, не являющееся степенью 2.

Это может быть расширено либо путем циклического прохождения, например, 4 байтов uint32_t и выполнения 4 операций поиска в таблице.Или, сделав еще большие справочные таблицы.

На x86 я получаю вышеперечисленное, чтобы сводиться к этому крошечному машинному коду без веток: 

get_exponent:
        movzx   edi, dil
        movzx   eax, BYTE PTR byte.2173[rdi]
        ret

(Переключение на uint_fast8_tдает идентичный код в этом случае.)

2 голосов
/ 16 мая 2019

Наилучшие характеристики (на моем встроенном ядре процессора ARM CORTEX M4) достигаются с помощью:

Встроенного CLZ решения (Count Leading Zero's)

Более того, CLZрешение гораздо более эффективно использует память, чем метод таблицы поиска, который занимает второе место.

Часто метод таблицы LookUp все еще менее эффективен, чем встроенный CLZ, поскольку таблица хранится в оперативной памяти, например, в DDR.,Таким образом, для доступа к данным в ОЗУ такого типа может потребоваться десяток циклов.В этом примере это усиливается тем фактом, что кеш команд включен, но не кеш данных.Кроме того, хранить эту огромную таблицу в кеше было бы не очень уместно.

benchmark

2 голосов
/ 16 мая 2019

Этот ответ является спорным - см. Комментарий.

Самый быстрый способ, несколько шутливо 1 , - написать 

switch (a)
{
    case 1: return 0;
    case 2: return 1;
    case 4: return 2;
    ...

Очевидно, что существует столько метокпоскольку в типе есть биты, но это все равно O (1).

Вы можете даже усечь a до степени два, используя идиому a ^ (a & (a - 1)), за счет переносимости, учитывая, что толькоработает, если a является типом дополнения 2.

1 Хотя в C ++ вы можете получить компилятор для построения таблицы с помощью constexpr и методов метапрограммирования.

0 голосов
/ 17 мая 2019

2 ^ x = a - уравнение

Предполагая 32-битную архитектуру и 'a' & 'x' как целые числа.

Вот мой подход 

uint32_t x;
uint8_t *ptr ;
uint8_t ByteNo,BitNo,i;

void My_Function(uint32_t a)
{
    ByteNo = BitNo = 9;//some random number
    ptr = (uint8_t*)&a;//Assuming points to LSB in variable a
    for(i=0;i<4;i++)
    {
        switch(*ptr)
        {
        case 0x01:  BitNo=0;break;
        case 0x02:  BitNo=1;break;
        case 0x04:  BitNo=2;break;
        case 0x08:  BitNo=3;break;
        case 0x10:  BitNo=4;break;
        case 0x20:  BitNo=5;break;
        case 0x40:  BitNo=6;break;
        case 0x80:  BitNo=7;break;
        case 0x00:  BitNo=9;break;
        default :   break;//take care error condition
        }

        if(9 != BitNo)
        {
            break;
        }
        else
        {
            ptr++;
        }
    }//for loop
    ByteNo = i;

    x = (BitNo) + (ByteNo*8);

}//My_Function

Другой подход: 

switch(a)
{
case   0x00000001:   x=0;   break;
case   0x00000002:   x=1;   break;
case   0x00000004:   x=2;   break;
case   0x00000008:   x=3;   break;
case   0x00000010:   x=4;   break;
case   0x00000020:   x=5;   break;
case   0x00000040:   x=6;   break;
case   0x00000080:   x=7;   break;
case   0x00000100:   x=8;   break;
case   0x00000200:   x=9;   break;
case   0x00000400:   x=10;   break;
case   0x00000800:   x=11;   break;
case   0x00001000:   x=12;   break;
case   0x00002000:   x=13;   break;
case   0x00004000:   x=14;   break;
case   0x00008000:   x=15;   break;
case   0x00010000:   x=16;   break;
case   0x00020000:   x=17;   break;
case   0x00040000:   x=18;   break;
case   0x00080000:   x=19;   break;
case   0x00100000:   x=20;   break;
case   0x00200000:   x=21;   break;
case   0x00400000:   x=22;   break;
case   0x00800000:   x=23;   break;
case   0x01000000:   x=24;   break;
case   0x02000000:   x=25;   break;
case   0x04000000:   x=26;   break;
case   0x08000000:   x=27;   break;
case   0x10000000:   x=28;   break;
case   0x20000000:   x=29;   break;
case   0x40000000:   x=30;   break;
case   0x80000000:   x=31;   break;
default:    break;//error condition
}
0 голосов
/ 16 мая 2019

@ Ответ Лундина кажется лучшим с точки зрения скорости (всего 3 инструкции по сборке!), Но он не может быть хорошим вариантом для вашей встроенной системы.Если огромные LUT не подходят:

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

#include <stdint.h>


static int get_pow2_exp(uint32_t value)
{

#if defined(__GNUC__)
        if (sizeof(unsigned int) == sizeof(value))
                return 31 - __builtin_clz(value);
        if (sizeof(unsigned long) == sizeof(value))
                return 31 - __builtin_clzl(value);
#endif
        int x;

        for (x = -1; value; value >>= 1)
                x++;

        return x;
}

Если вы хотите убедиться, что это степень двойки, вы можете использовать popcnt.Ваш цикл while является бесконечным циклом в случае, если входное значение не является степенью двойки, а мой просто дает решение на основе старшего бита (который может быть неправильным, в зависимости от ваших потребностей).

0 голосов
/ 16 мая 2019

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

Если x может быть, например, 100, поиск с начала (x = 0) с шагом x++ не является элегантным и оптимизированным (проверки 100). Вы можете установить шаг x+=5. Если результат ниже искомого значения, x+=5. Если больше - вернитесь назад с x-- (max 4 Times). Размер шага, который вы можете настроить в соответствии с вашими потребностями.

Если есть «верхний предел», вы можете создать массив возможных x и реализовать бинарный поиск.

...