Извлечение n наиболее значимых ненулевых битов из int в C ++ без циклов - PullRequest
Новая
       34

Извлечение n наиболее значимых ненулевых битов из int в C ++ без циклов

5 голосов
/ 15 марта 2012

Я хочу извлечь n старших значащих бит из целого числа в C ++ и преобразовать эти n битов в целое число.

Например 

int a=1200;
// its binary representation within 32 bit word-size is
// 00000000000000000000010010110000

Теперь я хочу извлечь 4 наиболее значимые цифры из этого представления, то есть 1111 

00000000000000000000010010110000
                     ^^^^

и преобразовать их снова в целое число (1001 в десятичной = 9).

Как это возможно с простой функцией C ++ без циклов?

Ответы [ 3 ]

7 голосов
/ 15 марта 2012

Некоторые процессоры имеют инструкцию для подсчета начальных двоичных нулей целого числа, а некоторые компиляторы имеют встроенные функции, позволяющие вам использовать эту инструкцию.Например, используя GCC: 

uint32_t significant_bits(uint32_t value, unsigned bits) {
    unsigned leading_zeros = __builtin_clz(value);
    unsigned highest_bit = 32 - leading_zeros;
    unsigned lowest_bit = highest_bit - bits;

    return value >> lowest_bit;
}

Для простоты я пропустил проверки, чтобы запрошенное количество бит было доступно.Для компилятора Microsoft встроенная функция называется __lzcnt.

Если ваш компилятор не предоставляет эту встроенную функцию, а у вашего процессора нет подходящей инструкции, то один из способов быстрого подсчета нулей - этобинарный поиск: 

unsigned leading_zeros(int32_t value) {
    unsigned count = 0;
    if ((value & 0xffff0000u) == 0) {
        count += 16;
        value <<= 16;
    }
    if ((value & 0xff000000u) == 0) {
        count += 8;
        value <<= 8;
    }
    if ((value & 0xf0000000u) == 0) {
        count += 4;
        value <<= 4;
    }
    if ((value & 0xc0000000u) == 0) {
        count += 2;
        value <<= 2;
    }
    if ((value & 0x80000000u) == 0) {
        count += 1;
    }
    return count;
}
1 голос
/ 15 марта 2012

Это не быстро, но (int)(log(x)/log(2) + .5) + 1 скажет вам позицию самого старшего ненулевого бита. Завершить алгоритм оттуда довольно просто.

0 голосов
/ 15 марта 2012

Кажется, что это работает (сделано в C # с UInt32, затем портировано, поэтому приносит извинения Бьярне): 

        unsigned int input = 1200;
        unsigned int most_significant_bits_to_get = 4;
        // shift + or the msb over all the lower bits
        unsigned int m1 = input | input >> 8 | input >> 16 | input >> 24;
        unsigned int m2 = m1 | m1 >> 2 | m1 >> 4 | m1 >> 6;
        unsigned int m3 = m2 | m2 >> 1;
        unsigned int nbitsmask = m3 ^ m3 >> most_significant_bits_to_get;

        unsigned int v = nbitsmask;
        unsigned int c = 32; // c will be the number of zero bits on the right
        v &= -((int)v);
        if (v>0) c--;
        if ((v & 0x0000FFFF) >0) c -= 16;
        if ((v & 0x00FF00FF) >0) c -= 8;
        if ((v & 0x0F0F0F0F) >0 ) c -= 4;
        if ((v & 0x33333333) >0) c -= 2;
        if ((v & 0x55555555) >0) c -= 1;

        unsigned int result = (input & nbitsmask) >> c;

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

Я использовал некоторый код из ссылки @ OliCharlesworth, вы также можете удалить условные выражения, используя LUT для кода конечных нулей.

...