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

У меня есть функция:Оптимизация обнаружения целого числа только один бит установлен

inline uint32_t ShiftOf(uint32_t v) 
{ 
    for (uint32_t s = 0; s < 32; ++s) 
    { 
     if (v == 1 << s) 
      return s; 
    } 
    return -1; 
}

Есть ли способ оптимизировать его?

источник

2015-11-04 Anonymous

Вы действительно хотите 'ShiftOf (6) == -1'? – Hurkyl

@PeteBecker он, вероятно, имел в виду «полный» log2: если log2 (v) является целым числом, тогда верните его, иначе return -1. – jingyu9575

@ LưuVĩnhPhúc Этот вопрос требует способа проверить * если * установлен любой бит, игнорируя положение. Этот вопрос задает вопрос о том, как определить бит *, который * задан, по-видимому, предполагая, что на входе установлен только один бит. Связано, но не дублируется. – Bob

Есть несколько способов оптимизации функций.

Оптимизация с операторами поразрядными:

inline uint32_t ShiftOf(uint32_t v) 
{ 
    uint32_t s = 
     (bool)(v & 0xFFFF0000) * 16 + 
     (bool)(v & 0xFF00FF00) * 8 + 
     (bool)(v & 0xF0F0F0F0) * 4 + 
     (bool)(v & 0xCCCCCCCC) * 2 + 
     (bool)(v & 0xAAAAAAAA); 
    return v == 1 << s ? s : -1; 
}

Оптимизация с компилятором встроенных функций:

inline uint32_t ShiftOf(uint32_t v) 
{ 
#if defined(_MSC_VER) 
    DWORD s = 0; 
    if (!_BitScanForward(&s, v)) 
     return -1; 
#elif defined(__GNUC__) 
    uint32_t s = __builtin_ctz(v); 
#else 
# error This platform is unsupported! 
#endif 
    return v == 1 << s ? s : -1; 
}

Оптимизация с хэш-таблицы:

const uint32_t g_divider = 37; 
uint32_t g_hash[g_divider] = { 0 }; 
static void InitHash() 
{ 
    for (uint32_t s = 0; s < 32; ++s) 
     g_hash[(1 << s) % g_divider] = s; 
} 

inline uint32_t ShiftOf(uint32_t v) 
{ 
    uint32_t s = g_hash[v % g_divider]; 
    return v == 1 << s ? s : -1; 
}

источник

2015-11-04 07:53:03 ErmIg

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

Я не уверен, но вы можете разворачивания петля:

inline uint32_t ShiftOf(uint32_t v) 
{ 
    switch (v) 
    { 
    case 0x00000001: return 0; 
    case 0x00000002: return 1; 
    case 0x00000004: return 2; 
    case 0x00000008: return 3; 
    case 0x00000010: return 4; 
    case 0x00000020: return 5; 
    case 0x00000040: return 6; 
    case 0x00000080: return 7; 
    case 0x00000100: return 8; 
    case 0x00000200: return 9; 
    case 0x00000400: return 10; 
    case 0x00000800: return 11; 
    case 0x00001000: return 12; 
    case 0x00002000: return 13; 
    case 0x00004000: return 14; 
    case 0x00008000: return 15; 
    case 0x00010000: return 16; 
    case 0x00020000: return 17; 
    case 0x00040000: return 18; 
    case 0x00080000: return 19; 
    case 0x00100000: return 20; 
    case 0x00200000: return 21; 
    case 0x00400000: return 22; 
    case 0x00800000: return 23; 
    case 0x01000000: return 24; 
    case 0x02000000: return 25; 
    case 0x04000000: return 26; 
    case 0x08000000: return 27; 
    case 0x10000000: return 28; 
    case 0x20000000: return 29; 
    case 0x40000000: return 30; 
    case 0x80000000: return 31; 
    default: return -1; 
    } 
}

источник

2015-11-04 10:32:20

Не существует ли флаг 'gcc' |' clang'? '-funroll-loops' или что-то еще? –

@BlacklightShining: Это не цикл. Хотя я предполагаю, что разворачивание цикла, который проверял каждую позицию бита, в свою очередь, может привести к аналогичному результату в умном компиляторе с включенными оптимизациями. – ShadowRanger

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

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

Наиболее распространенным именем для этой операции является BSR (Bit Scan Reverse = найти индекс самого значимого бита). В MSVC он может генерироваться с помощью встроенных функций _BitScanReverse, соответственно. _BitScanReverse64 (что взять дополнительную маску аргумент)

Другие ссылки на следующей странице: https://en.wikipedia.org/wiki/Find_first_set

источник

2015-11-04 10:46:59 BrunoLevy

Несмотря на то, что советы не являются плохими, ссылки не принимаются. Не могли бы вы подвести итог статьи, с которой вы связались? Может быть, цитируя наиболее распространенных компиляторов? –

@Matthieu M., хороший момент (я отредактировал сообщение), спасибо. – BrunoLevy

Если вам нужно только обнаружить, если ровно один бит установлен, не который один, вы можете optimize this significantly:

int is_power_of_two(uint32_t v) { 
    return v && !(v & (v - 1)); 
}

Если вам нужно на самом деле вычислить, какой бит установлен, а не только того, установлен один бит, то есть a plethora of options (или просто обмануть и использовать log2 функцию C99 после проверки это двойки и кастовал результат).

Короткий ответ: Закладка Bit Twiddling Hacks. Это удобно.

источник

2015-11-04 13:10:23 ShadowRanger

Вы можете подсчитать количество битов и посмотреть, если это 1.

Обратитесь к Fast Bit Counting страницу, и вы найдете множество различных процедур для подсчета числа битов быстро.

Самый быстрый 4b. Предвычисления-16bit (хотя это в C):

static char bits_in_16bits [0x1u << 16]; 

int bitcount (unsigned int n) { 
    // works only for 32-bit ints 

    return bits_in_16bits [n   & 0xffffu] 
     + bits_in_16bits [(n >> 16) & 0xffffu]; 
}

Precompute_16bit представляет собой вариант Precompute_8bit в том, что массив bits_in_16bits [] сохраняет число битов 1 в последовательных 16 битных чисел (шорты).

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

источник

2015-11-04 19:21:23 ErikE

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

ответ

Смежные вопросы