Как эффективно подсчитать максимальную мощность 2, которая меньше или равна заданному числу?

Ответ 1

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

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return x ^ (x >> 1);
}

Это работает, сначала "размазывая" бит с наивысшим набором вправо, а затем x ^ (x >> 1) хранит только биты, которые отличаются от бит, непосредственно слева от них (считается, что msb имеет 0 слева от него), который является только самым старшим битом, потому что благодаря размазыванию число имеет вид 0 ⁿ 1 ^m (в нотации строк, а не на числовое возведение в степень).

Поскольку никто на самом деле не публикует его, с внутренними функциями, которые вы могли бы написать (GCC, Clang)

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  return 0x80000000 >> __builtin_clz(x);
}

Или (MSVC, возможно, не проверен)

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  unsigned long index;
  // ignoring return value, assume x != 0
  _BitScanReverse(&index, x);
  return 1u << index;
}

Что, если оно напрямую поддерживается целевым оборудованием, должно быть лучше.

Результаты на coliru и результаты латентности на coliru (сравните с базовой линией, которая должна быть примерно указана на накладные расходы). В результате латентности первая версия highestPowerOfTwoIn больше не выглядит так хорошо (все еще хорошо, но это длинная цепочка зависимых инструкций, поэтому не удивительно, что она расширяет разрыв с версией intrinsics). Какое из них является наиболее релевантным, зависит от вашего фактического использования.

Если у вас есть нечетное аппаратное обеспечение с быстрой операцией по разворачиванию бит (но, возможно, медленные сдвиги или медленные clz), позвоните по телефону _rbit, затем вы можете сделать

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  x = _rbit(x);
  return _rbit(x & -x);
}

Это, конечно, основано на старом x & -x, который изолирует бит младшего разряда, окруженный разворотами бит, который изолирует старший бит.

Ответ 2

Таблица поиска выглядит как лучший вариант здесь. Следовательно, чтобы ответить

Может ли это быть оптимизировано еще больше? Какие трюки можно использовать здесь?

Да, мы можем! Давайте избили бинарный поиск стандартной библиотеки!

template <class T>
inline size_t
choose(T const& a, T const& b, size_t const& src1, size_t const& src2)
{
    return b >= a ? src2 : src1;
}
template <class Container>
inline typename Container::const_iterator
fast_upper_bound(Container const& cont, typename Container::value_type const& value)
{
    auto size = cont.size();
    size_t low = 0;

    while (size > 0) {
        size_t half = size / 2;
        size_t other_half = size - half;
        size_t probe = low + half;
        size_t other_low = low + other_half;
        auto v = cont[probe];
        size = half;
        low = choose(v, value, low, other_low);
    }

    return begin(cont)+low;
}

Использование этой реализации upper_bound дает существенное улучшение:

g++ -std=c++14 -O2 -Wall -Wno-unused-but-set-variable -Werror main.cpp && ./a.out
Pow and log took 2536 milliseconds.
Multiplying by 2 took 320 milliseconds.
Binsearching precomputed table of powers took 349 milliseconds.
Binsearching (opti) precomputed table of powers took 167 milliseconds.

(жить на coliru) Обратите внимание, что я улучшил ваш тест, чтобы использовать случайные значения; сделав это, я удалил смещение предсказания ветвей.

Теперь, если вам действительно нужно больше напрягаться, вы можете оптимизировать функцию choose с помощью x86_64 asm для clang:

template <class T> inline size_t choose(T const& a, T const& b, size_t const& src1, size_t const& src2)
{
#if defined(__clang__) && defined(__x86_64)
    size_t res = src1;
    asm("cmpq %1, %2; cmovaeq %4, %0"
        :
    "=q" (res)
        :
        "q" (a),
        "q" (b),
        "q" (src1),
        "q" (src2),
        "0" (res)
        :
        "cc");
    return res;
#else
    return b >= a ? src2 : src1;
#endif
}

С выходом:

clang++ -std=c++14 -O2 -Wall -Wno-unused-variable -Wno-missing-braces -Werror main.cpp && ./a.out
Pow and log took 1408 milliseconds.
Multiplying by 2 took 351 milliseconds.
Binsearching precomputed table of powers took 359 milliseconds.
Binsearching (opti) precomputed table of powers took 153 milliseconds.

(Live on coliru)

Ответ 3

Восходит быстрее, но падает с той же скоростью.

        uint multiply_quick(uint n)
        {
            if (n < 2u) return 1u;
            uint maxpow = 1u;

            if (n > 256u)
            {
                maxpow = 256u * 128u;

                // fast fixing the overshoot
                while (maxpow > n)
                    maxpow = maxpow >> 2;
                // fixing the undershoot
                while (2u * maxpow <= n)
                    maxpow *= 2u;
            }
            else
            {

                // quicker scan
                while (maxpow < n && maxpow != 256u)
                    maxpow *= maxpow;

                // fast fixing the overshoot
                while (maxpow > n)
                    maxpow = maxpow >> 2;

                // fixing the undershoot
                while (2u * maxpow <= n)
                    maxpow *= 2u;
            }
            return maxpow;
        }

возможно, это лучше подходит для 32-битных переменных с использованием 65k постоянного литерала вместо 256.

Ответ 4

Просто установите 0 всех битов, но первый. Это должно быть очень быстро и эффективно

Ответ 5

Как уже упоминалось @Jack, вы можете просто установить 0 всех бит, кроме первого. И вот решение:

#include <iostream>

uint16_t bit_solution(uint16_t num)
{
    if ( num == 0 )
        return 0;

    uint16_t ret = 1;
    while (num >>= 1)
        ret <<= 1;

    return ret;
}

int main()
{
    std::cout << bit_solution(1024) << std::endl; //1024
    std::cout << bit_solution(1025) << std::endl; //1024
    std::cout << bit_solution(1023) << std::endl; //512
    std::cout << bit_solution(1) << std::endl; //1
    std::cout << bit_solution(0) << std::endl; //0
}

Ответ 6

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

Но это мило.

uint_fast16_t bitunsetter(uint_fast16_t n)
{
  while (uint_fast16_t k = n & (n-1))
    n = k;
  return n;
}