Найдите бит наивысшего порядка в C

На ум приходит постоянное удаление младшего бита ...

int highest_order_bit( int x )
{
    int y = x;
    do { 
        x = y;
        y = x & (x-1); //remove low order bit
    }
    while( y != 0 );
    return x;
}

Это должно помочь.

int hob (int num)
{
    if (!num)
        return 0;

    int ret = 1;

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

    return ret;
}

hob (1234) возвращает 1024
. hob (1024) возвращает 1024
. hob (1023) возвращает 512

Из «Восторга хакера»:

int hibit(unsigned int n) {
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

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

Ядро linux имеет ряд таких удобных битовых операций, которые закодированы наиболее эффективным образом для ряда архитектур. Вы можете найти общие версии в включить / asm-generic / bitops / fls.h (и у друзей), но также смотрите включить / asm-x86 / bitops.h для определения, использующего встроенную сборку, если скорость имеет значение, а переносимость - нет.

Быстрый способ сделать это - использовать справочную таблицу. Для 32-битного ввода и 8-битной таблицы поиска требуется всего 4 итерации:

int highest_order_bit(int x)
{
    static const int msb_lut[256] =
        {
            0, 0, 1, 1, 2, 2, 2, 2, // 0000_0000 - 0000_0111
            3, 3, 3, 3, 3, 3, 3, 3, // 0000_1000 - 0000_1111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_0000 - 0001_0111
            4, 4, 4, 4, 4, 4, 4, 4, // 0001_1000 - 0001_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_0000 - 0010_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0010_1000 - 0010_1111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_0000 - 0011_0111
            5, 5, 5, 5, 5, 5, 5, 5, // 0011_1000 - 0011_1111

            6, 6, 6, 6, 6, 6, 6, 6, // 0100_0000 - 0100_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0100_1000 - 0100_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_0000 - 0101_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0101_1000 - 0101_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_0000 - 0110_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0110_1000 - 0110_1111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_0000 - 0111_0111
            6, 6, 6, 6, 6, 6, 6, 6, // 0111_1000 - 0111_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1000_0000 - 1000_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1000_1000 - 1000_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_0000 - 1001_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1001_1000 - 1001_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_0000 - 1010_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1010_1000 - 1010_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_0000 - 1011_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1011_1000 - 1011_1111

            7, 7, 7, 7, 7, 7, 7, 7, // 1100_0000 - 1100_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1100_1000 - 1100_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_0000 - 1101_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1101_1000 - 1101_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_0000 - 1110_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1110_1000 - 1110_1111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_0000 - 1111_0111
            7, 7, 7, 7, 7, 7, 7, 7, // 1111_1000 - 1111_1111
        };

    int byte;
    int byte_cnt;

    for (byte_cnt = 3; byte_cnt >= 0; byte_cnt--)
    {
        byte = (x >> (byte_cnt * 8)) & 0xff;
        if (byte != 0)
        {
            return msb_lut[byte] + (byte_cnt * 8);
        }
    }

    return -1;
}

как запутанный код? Попробуй это:

1 << (число) log2 (x)

Это можно легко решить с помощью существующих библиотечных вызовов.

int highestBit(int v){
  return fls(v) << 1;
}

На странице руководства Linux содержится более подробная информация об этой функции и ее аналогах для других типов ввода.

// Note doesn't cover the case of 0 (0 returns 1)
inline unsigned int hibit( unsigned int x )
{
  unsigned int log2Val = 0 ;
  while( x>>=1 ) log2Val++;  // eg x=63 (111111), log2Val=5
  return 1 << log2Val ; // finds 2^5=32
}

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

1<<(fls(input)-1)

Отличное решение, которое я придумал, - это двоичный поиск битов.

uint64_t highestBit(uint64_t a, uint64_t bit_min, uint64_t bit_max, uint16_t bit_shift){
    if (a == 0) return 0;
    if (bit_min >= bit_max){
        if ((a & bit_min) != 0)
            return bit_min;
        return 0;
    }
    uint64_t bit_mid = bit_max >> bit_shift;
    bit_shift >>= 1;
    if ((a >= bit_mid) && (a < (bit_mid << 1)))
        return bit_mid;
    else if (a > bit_mid)
        return highestBit(a, bit_mid, bit_max, bit_shift);
    else
        return highestBit(a, bit_min, bit_mid, bit_shift);

}

Максимальный бит - это максимальная степень 2, поэтому для 64-битного числа это будет 2 ^ 63. Битовый сдвиг должен быть инициализирован половиной количества бит, поэтому для 64 бит это будет 32.

Если вам не нужно переносимое решение и ваш код выполняется на процессоре, совместимом с x86, вы можете использовать встроенную функцию _BitScanReverse (), предоставляемую компилятором Microsoft Visual C / C++. Он сопоставляется с инструкцией ЦП BSR, которая возвращает самый высокий набор битов.

Немного поздно для этой вечеринки, но самое простое решение, которое я нашел, учитывая современный GCC в качестве компилятора, просто:

static inline int_t get_msb32 (register unsigned int val)
{
  return 32 - __builtin_clz(val);
}

static inline int get_msb64 (register unsigned long long val)
{
  return 64 - __builtin_clzll(val);
}

Он даже относительно портативен (по крайней мере, он будет работать на любой платформе GCC).

Лучший алгоритм, который мне очень нравится:

unsigned hibit(unsigned n) {
    n |= (n >>  1u);
    n |= (n >>  2u);
    n |= (n >>  4u);
    n |= (n >>  8u);
    n |= (n >> 16u);
    return n - (n >> 1);
}

И это легко расширяется для uint64_t вот так:

uint64_t hibit(uint64_t n) {
    n |= (n >>  1u);
    n |= (n >>  2u);
    n |= (n >>  4u);
    n |= (n >>  8u);
    n |= (n >> 16u);
    n |= (n >> 32u);
    return n - (n >> 1);
}

или даже __int128

__int128 hibit(__int128 n) {
    n |= (n >>  1u);
    n |= (n >>  2u);
    n |= (n >>  4u);
    n |= (n >>  8u);
    n |= (n >> 16u);
    n |= (n >> 32u);
    n |= (n >> 64u);
    return n - (n >> 1);
}

Кроме того, кроссплатформенное решение не зависит от использования компилятора.