Двоичный файл, два последовательных бита 1

Вопрос:

Я пытаюсь реализовать с помощью C, который выводит количество двух последовательных 1-бит в целое число без перекрытия. Это мой код:

 #include <stdio.h>

int numPairs(int num) {
    int count = 0;
    while (num) {
        num = (num amp; (num << 1));
        count  ;
    }
    return count / 2;
}

int main(){
    printf("%dt", numPairs(10000));
    printf("%dt", numPairs(146));
    printf("%dt", numPairs(7645));
    printf("%dt", numPairs(16383));
    return 0;
}

Мой вывод 1 0 1 7

Но вывод должен быть 1 0 3 7

Все правильно, за исключением 7645 , и я не знаю, что с этим не так.

Для 7645 моего кода выдает результат 1 , но правильный результат 3 .

Ответ №1:

Ваш метод не подходит:

Вы подсчитываете количество итераций, необходимых для обнуления выражения n = n amp; (n << 1); . Это будет максимальное количество последовательных бит 1. Если пары битов разделены, результат будет отличаться от количества неперекрывающихся пар битов.

В случае в 7645 , 0x1ddd или 0001 1101 1101 1101 в десятичной системе счисления имеется 3 группы по 3 последовательных бита 1, но они обнуляются при параллельных 3 итерациях цикла, следовательно, count / 2 является 1 .

Вы должны использовать другой алгоритм, такой как:

 int numPairs(int num) {
    int count = 0;
    unsigned int x = num;
    while (x) {
        if ((x amp; 3) == 3) {
            count  ;
            x >>= 2;
        } else {
            x >>= 1;
        }
    }
    return count;
}

1. 1 за объяснение алгоритма, используемого OP. Я рассматривал решение, похожее на ваше, но не был уверен, что стандарт C гарантирует неизменность битового шаблона при переходе от подписанного к неподписанному. Для реализаций дополнения 2s, я думаю, битовый шаблон остается неизменным, но переносим ли он вообще?

2. @4386427: для архитектур с дополнением non two нельзя делать предположения о положении знакового бита и потенциальном присутствии битов заполнения, поэтому проблема не полностью указана для целых чисел со знаком. Помимо обсуждения языковых вопросов, которые мне нравятся, эти соображения не имеют практического применения, но для ясности OP следует сделать num unsigned.

Ответ №2:

В случае, если важна скорость, это также может быть сделано с помощью операций с битовыми манипуляциями:

 int numPairs(uint32_t x) {
    return __builtin_popcount((((x ^ 0x55555555)   0x55555555) ^ 0x55555555) amp; x);
}

Это приводит к получению 1 бита в верхнем бите каждой непересекающейся 2-разрядной группы единиц, а затем подсчитывает 1 бит.