Как получить наименьшее n, что 2 ^ n> = x для заданного целого числа x в O (1)?

Question

Как для данного целого числа без знака x найти наименьшее n, что 2 ^ n & ge; x в O (1)? другими словами, я хочу найти индекс старшего установленного бита в двоичном формате x (плюс 1, если x не является степенью 2) в O (1) (не зависит от размера целого числа и размера байта) .

Answer 1

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

Если вам нужно практичное решение, у большинства процессоров будет какой-то код операции «найти старший бит». На x86, например, это BSR. У большинства компиляторов будет механизм написания необработанного ассемблера.

Answer 2

Хорошо, так как пока никто не опубликовал решение во время компиляции, вот мое.Предварительным условием является то, что ваше входное значение является константой времени компиляции.Если у вас есть это, все это делается во время компиляции.

#include <iostream>
#include <iomanip>

// This should really come from a template meta lib, no need to reinvent it here, 
// but I wanted this to compile as is. 
namespace templ_meta {
    // A run-of-the-mill compile-time if. 
    template<bool Cond, typename T, typename E> struct if_;
    template<           typename T, typename E> struct if_<true , T, E> {typedef T result_t;};
    template<           typename T, typename E> struct if_<false, T, E> {typedef E result_t;};

    // This so we can use a compile-time if tailored for types, rather than integers. 
    template<int I>
    struct int2type {
        static const int result = I;
    };
}

// This does the actual work.
template< int I, unsigned int Idx = 0>
struct index_of_high_bit {
    static const unsigned int result = 
        templ_meta::if_< I==0
           , templ_meta::int2type<Idx>
           , index_of_high_bit<(I>>1),Idx+1> 
        >::result_t::result;
};

// just some testing
namespace {
    template< int I >
    void test() 
    {
        const unsigned int result = index_of_high_bit<I>::result;
        std::cout << std::setfill('0') 
                  << std::hex << std::setw(2) << std::uppercase << I << ": " 
                  << std::dec << std::setw(2) << result  
                  << '\n';
    }
}

int main()
{
    test<0>();
    test<1>();
    test<2>();
    test<3>();
    test<4>();
    test<5>();
    test<7>();
    test<8>();
    test<9>();
    test<14>();
    test<15>();
    test<16>();
    test<42>();
    return 0;
}

- это интересно.

Answer 3

Это вопрос о поиске старшего набора битов (как отметили Иштар и Оли Чарльзуорт). Bit Twiddling Hacks дает решение, которое занимает около 7 операций для 32-разрядных целых чисел и около 9 операций для 64-разрядных целых чисел.

Answer 4

Немного математики для преобразования выражения:

 int n = ceil(log(x)/log(2));

Это, очевидно, O (1).

Answer 5

В <cmath> есть функции логарифма, которые выполнят это вычисление для вас.

ceil(log(x) / log(2));

Answer 6

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

Во всяком случае, смутно основываясь на первом решении, предложенном Миграном, Я получаю:

int
topBit( unsigned x )
{
    int r = 1;
    if ( x > 1 ) {
        if ( frexp( static_cast<double>( x ), &r ) != 0.5 ) {
            ++ r;
        }
    }
    return r - 1;
}

Это работает в рамках ограничения, что входное значение должно быть точно представимый в double; если ввод unsigned long long, это может быть не так, и на некоторых более экзотических платформах это может даже не иметь места для unsigned.

Единственное другое постоянное время (относительно количества бит), которое я могу думаю это:

int
topBit( unsigned x )
{
    return x == 0 ? 0.0 : ceil( log2( static_cast<double>( x ) ) );
}

, который имеет то же ограничение в отношении того, что x точно представляются в double, а также могут страдать от ошибок округления присущ операциям с плавающей запятой (хотя, если log2 реализовано правильно, я не думаю, что это должно быть так). Если ваш компилятор не поддерживает log2 (функция C ++ 11, но также присутствует в C90, поэтому я ожидаю, что большинство компиляторов уже реализовали это), тогда, конечно, log( x ) / log( 2 ) можно использовать, но я подозреваю, что это увеличит риск ошибки округления, приводящей к неправильный результат.

FWIW, я нахожу O (1) на количество битов немного нелогичным, для причины, которые я указал выше: количество битов является лишь одним из многих «постоянные факторы», которые зависят от машины, на которой вы работаете. Во всяком случае, я пришел к следующему чисто целочисленному решению, которое O (lg 1) для количества бит и O (1) для всего остального:

template< int k >
struct TopBitImpl
{
    static int const k2 = k / 2;
    static unsigned const m = ~0U << k2;
    int operator()( unsigned x ) const
    {
        unsigned r = ((x & m) != 0) ? k2 : 0;
        return r + TopBitImpl<k2>()(r == 0 ? x : x >> k2);
    }
};

template<>
struct TopBitImpl<1>
{
    int operator()( unsigned x ) const
    {
        return 0;
    }
};

int
topBit( unsigned x )
{
    return TopBitImpl<std::numeric_limits<unsigned>::digits>()(x)
                + (((x & (x - 1)) != 0) ? 1 : 0);
}

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

Answer 7

После некоторых поисков в интернете я нашел эти 2 версии для 32-битного целого числа без знака. Я проверил их, и они работают. Мне понятно, почему работает второй, но я все еще думаю о первом ...

1

unsigned int RoundUpToNextPowOf2(unsigned int v)
{
    unsigned int r = 1;
    if (v > 1) 
    {
      float f = (float)v;
      unsigned int const t = 1U << ((*(unsigned int *)&f >> 23) - 0x7f);
      r = t << (t < v);
    }
    return r;
}

2

unsigned int RoundUpToNextPowOf2(unsigned int v)
{
    v--;
    v |= v >> 1;
    v |= v >> 2;
    v |= v >> 4;
    v |= v >> 8;
    v |= v >> 16;
    v++;
    return v;
}

редактировать: Первый также ясно.

Answer 8

Для 32-битного int следующий псевдокод будет O (1).

highestBit(x)
  bit = 1
  highest = 0
  for i 1 to 32
    if x & bit == 1
      highest = i
    bit = bit * 2
  return highest + 1

Неважно, насколько большой x, он всегда проверяет все 32 бита. Таким образом, постоянное время.

Если ввод может быть любого целого размера, скажем, ввод длиной n цифр. Тогда любое решение, читающее ввод, будет читать n цифр и должно быть не менее O (n). Если кто-то не найдет решение без чтения ввода, невозможно найти решение O (1).

Answer 9

Как уже упоминалось, длина двоичного представления x + 1 - это искомое n (если само x не является степенью двойки, то есть 10 ..... 0 в двоичном представлении),Я серьезно сомневаюсь, что существует истинное решение в O (1), если только вы не рассматриваете переводы в двоичное представление как O (1).

Answer 10

Возможно, эта ссылка поможет.

Предупреждение: код не совсем простой и кажется довольно не поддерживаемым.

  uint64_t v;          // Input value to find position with rank r.
  unsigned int r;      // Input: bit's desired rank [1-64].
  unsigned int s;      // Output: Resulting position of bit with rank r [1-64]
  uint64_t a, b, c, d; // Intermediate temporaries for bit count.
  unsigned int t;      // Bit count temporary.

  // Do a normal parallel bit count for a 64-bit integer,                     
  // but store all intermediate steps.                                        
  // a = (v & 0x5555...) + ((v >> 1) & 0x5555...);
  a =  v - ((v >> 1) & ~0UL/3);
  // b = (a & 0x3333...) + ((a >> 2) & 0x3333...);
  b = (a & ~0UL/5) + ((a >> 2) & ~0UL/5);
  // c = (b & 0x0f0f...) + ((b >> 4) & 0x0f0f...);
  c = (b + (b >> 4)) & ~0UL/0x11;
  // d = (c & 0x00ff...) + ((c >> 8) & 0x00ff...);
  d = (c + (c >> 8)) & ~0UL/0x101;
  t = (d >> 32) + (d >> 48);
  // Now do branchless select!                                                
  s  = 64;
  // if (r > t) {s -= 32; r -= t;}
  s -= ((t - r) & 256) >> 3; r -= (t & ((t - r) >> 8));
  t  = (d >> (s - 16)) & 0xff;
  // if (r > t) {s -= 16; r -= t;}
  s -= ((t - r) & 256) >> 4; r -= (t & ((t - r) >> 8));
  t  = (c >> (s - 8)) & 0xf;
  // if (r > t) {s -= 8; r -= t;}
  s -= ((t - r) & 256) >> 5; r -= (t & ((t - r) >> 8));
  t  = (b >> (s - 4)) & 0x7;
  // if (r > t) {s -= 4; r -= t;}
  s -= ((t - r) & 256) >> 6; r -= (t & ((t - r) >> 8));
  t  = (a >> (s - 2)) & 0x3;
  // if (r > t) {s -= 2; r -= t;}
  s -= ((t - r) & 256) >> 7; r -= (t & ((t - r) >> 8));
  t  = (v >> (s - 1)) & 0x1;
  // if (r > t) s--;
  s -= ((t - r) & 256) >> 8;
  s = 65 - s;