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

Question

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

#include <stdio.h>

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

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

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

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

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

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

Answer 1

Ваш метод неуместен:

Вы считаете количество итераций, необходимое для обнуления выражения n = n & (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 & 3) == 3) {
            count++;
            x >>= 2;
        } else {
            x >>= 1;
        }
    }
    return count;
}