Десятичное в двоичное преобразование в C

Question

Реализуйте функцию inspect_bits, которая проверяет, содержит ли данное число 2 или более последовательных в своем двоичном представлении. Если это так, функция должна вернуть 1. В противном случае она должна вернуть 0.

Например, inspect_bits (13) должен возвращать 1, поскольку он содержит 2 последовательных в двоичном представлении (1101).

Программа работает для определенных чисел, в данном случае 13, и некоторых других, однако программа не работает для «8», «10» и некоторых других чисел.

#include <stdlib.h>
#include <stdio.h>

int inspect_bits(unsigned int number)
{
    int arr[32];
    int i=0,temp,c=0;;

    while(number > 0)
    {
        arr[i] = number%2;
        number = number/2;
        i++;
    }
    for (int j=i-1; j>=0; j--)
    {
        temp = arr[j];
            for (int k=j+1; k>0; k--)
            {
                if (temp==arr[k])
                c++;
            }
    }
    if (c != 0)
        return 1;
    else
        return 0;
}

#ifndef RunTests
int main ()
{
    printf("%d", inspect_bits(13));
}
#endif

Answer 1

Чтобы определить, имеет ли целое число без знака n два установленных смежных бита, достаточно проверить:

(n & (n >> 1)) != 0

Там n >> 1 - это число n, сдвинутое на один бит вправо, что аналогично целочисленному делению на 2. Вы можете визуализировать этот метод путем нумерации битов:

n            7 6 5 4 3 2 1 0
n >> 1         7 6 5 4 3 2 1

Побитовое и (&) - бинарный оператор. Его результат будет иметь установленный бит, если оба операнда имеют соответствующий установленный бит. В приведенном выше выражении будет установлен бит 0, если в n установлены оба бита: 0 и 1; бит 1 будет установлен, если в n установлены биты 1 и 2 и т. д. У него не будет установленных битов (и, следовательно, они будут равны нулю), если не установлены два соседних бита n.

Answer 2

Это выглядит способ слишком сложным, как реализация алгоритма и для отладки. Это проще:

int inspect_bits(unsigned int number)
{
   while (number)
   {
      if ((number & 3) == 3)
          return 1;
      number >>= 1;
   }
   return 0;
}

Цикл проверяет последние два бита number против 3, что составляет 00000011 в двоичном виде. Если это совпадает, то в number было (как минимум!) Два последовательных бита. Если нет, биты в number сдвигаются вправо и проверяются снова. Цикл может остановиться, когда number достигнет 0 - технически даже while (number > 2), поскольку только значения выше 2 имеют более двух последовательных битов.