подсчитать количество нулевых групповых битов в числе

Question

Как вы считаете количество нулевых групповых битов в числе?биты группы - это любой последовательный ноль или один бит, например, 2 представлен как .... 0000000000000000010 имеет две группы нулевых битов, младший значащий бит, и группа начинается после одного.Кроме того, мне очень нужны алгоритмы для работы с битами, если у кого-то есть ссылка, пожалуйста, поделитесь

Answer 1

Вот несколько советов для вас:

• if (x & 1) {...} проверяет, установлен ли младший бит x;
• x >>= 1 сдвигает значение x один бит вправо;
• учитывайте отрицательные числа, когда вы выполняете битовую манипуляцию.

Answer 2

Вот пара забавных способов сделать это.# Define-s в начале предназначены только для возможности выразить входные данные функции в двоичной записи.Две функции, которые выполняют эту работу, являются вариациями темы: первая использует последовательность де Брюина и таблицу поиска, чтобы выяснить, сколько концевых нулей есть в параметре, и делает остальное соответственно.Второй использует таблицу Mod37, чтобы сделать то же самое, что очень похоже по концепции, но включает операцию по модулю вместо умножения и сдвига битов.Один из них быстрее.Лень выяснять, какой именно.

Это намного больше кода, чем очевидное решение.Но это может быть очень эффективно, если у вас есть в основном нули на входе, так как для этого требуется только одна итерация цикла (фактически только одна ветвь) для каждого 1-бита вместо одной итерации цикла для каждого бита.

#define HEX__(n) 0x##n##LU

#define B8__(x)  ((x&0x0000000FLU)?  1:0)   \
                +((x&0x000000F0LU)?  2:0)   \
                +((x&0x00000F00LU)?  4:0)   \
                +((x&0x0000F000LU)?  8:0)   \
                +((x&0x000F0000LU)? 16:0)   \
                +((x&0x00F00000LU)? 32:0)   \
                +((x&0x0F000000LU)? 64:0)   \
                +((x&0xF0000000LU)?128:0)

#define B8(d) ((unsigned char)B8__(HEX__(d)))

#define B16(dmsb,dlsb) (((unsigned short)B8(dmsb)<<8) + B8(dlsb))

#define B32(dmsb,db2,db3,dlsb) (((unsigned long)B8(dmsb)<<24) \
                              + ((unsigned long)B8(db2)<<16)  \
                              + ((unsigned long)B8(db3)<<8)   \
                              + B8(dlsb))

unsigned int count_zero_groups_debruijn(unsigned int v)
{
    // number of zero-bit groups (set to 1 if high-bit is zero)
    unsigned int g = (~(v & 0x80000000)) >> 31; 

    // lookup table for deBruijn 
    static const int _DeBruijnTable[32] = 
    {
        0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8, 
        31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9
    };

    do {
        // get number of trailing zeros in v
        int tz = _DeBruijnTable[((v & -v) * 0x077CB531U) >> 27];
        // increment zero group count if more than 1 trailing zero
        g += (tz > 0) * 1;
        // shift out trailing zeros and the preceding 1
        v = v >> (tz+1);
    } while (v);

    return g;
}

unsigned int count_zero_groups_mod37(unsigned int v)
{
    // number of zero-bit groups (set to 1 if high-bit is zero)
    unsigned int g = (~(v & 0x80000000)) >> 31; 

    // lookup table for mod37
    static const int _Mod37Table[] = 
    {
         0,  0,  1, 26,  2, 23, 27,  0,  3, 16, 24, 30, 28, 11,  0, 13,  4,
         7, 17,  0, 25, 22, 31, 15, 29, 10, 12,  6,  0, 21, 14,  9,  5, 20,
         8, 19, 18
    };

    do {
        // get number of trailing zeros in v
        int tz = _Mod37Table[(v & -v) % 37];
        // increment zero group count if more than 1 trailing zero
        g += (tz > 0) * 1;
        // shift out trailing zeros and the preceding 1
        v = v >> (tz+1);
    } while (v);

    return g;
}

int main(int argc, char* argv[])
{
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(10011001,10000000,00001001,00010011)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(10011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(00011001,10000000,00001001,00010001)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_debruijn(B32(00011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 0)\n", count_zero_groups_debruijn(B32(11111111,11111111,11111111,11111111)));
    printf("zero groups: %d (should be 1)\n", count_zero_groups_debruijn(B32(00000000,00000000,00000000,00000000)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(10011001,10000000,00001001,00010011)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(10011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(00011001,10000000,00001001,00010001)));
    printf("zero groups: %d (should be 6)\n", count_zero_groups_mod37   (B32(00011001,10000000,00001001,00010000)));
    printf("zero groups: %d (should be 0)\n", count_zero_groups_mod37   (B32(11111111,11111111,11111111,11111111)));
    printf("zero groups: %d (should be 1)\n", count_zero_groups_mod37   (B32(00000000,00000000,00000000,00000000)));
    return 0;
}

Answer 3

Самый простой способ - подсчитать количество переходов от одного до нуля в цикле, используя сдвиг битовой маски вместе с побитовой операцией `и '. Также необходимо проверить первый бит и увеличить полученное количество на единицу, если оно равно 0.

Answer 4

Решение Эндрю, без сомнения, самое простое в разработке и реализации, но я не могу не задаться вопросом, существует ли более быстрое решение с использованием больших битовых масок.

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

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

В любом случае, не исключено, что подобное подобное решение существует здесь.

Answer 5

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

Answer 6

Вы можете многократно использовать целочисленное деление и оператор по модулю для извлечения битов и отслеживания групп в вашем цикле. Это звучит как домашнее задание, так что я не уверен, сколько вам нужно услуг, чтобы дать вам полное решение? Предположим, что вы можете использовать этот алгоритм, чтобы получить представление base-2 для положительного целого числа (фактически, оно работает с любым основанием> = 2):

int example = 40;
while (example > 0) {
    printf("%d\n", example % 2);
    example /= 2;
}

Это распечатает биты в обратном порядке (то есть начиная с наименее значимого). Отсюда не так много работы для подсчета групп, которые вы хотите сосчитать. Должен ли я пойти дальше или вы можете взять его отсюда?