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

Ответ 1

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

Оптимизация с помощью побитовых операторов:

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;
}

Ответ 2

Если вам нужно только определить, установлен ли ровно один бит, а не какой, вы можете оптимизировать это значительно:

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

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

Короткий ответ: Bookmark Бит Tweedling Hacks. Это удобно.

Ответ 3

Я не уверен, но вы можете развернуть цикл:

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;
    }
}

Ответ 4

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

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

Дополнительные ссылки на следующей веб-странице: https://en.wikipedia.org/wiki/Find_first_set

Ответ 5

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

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

Самый быстрый - 4b. Precompute-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-битных числах (shorts).

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