Побитовые операции - C (СИ) (69831)

Узнай цену своей работы

Формулировка задачи:

Доброго времени суток. Читаю KR, добрался до упражнения 2.9: Применительно к числам, в представлении которых использован дополнительный код, выражение х &= (х-1) уничтожает самую правую 1 в х. Объясните, почему. Используйте это наблюдение при написании более быстрого варианта функции bitcount. bitcount считает количество единичных битов для числа, которое ввел пользователь. (для 5 - 2, для 255 - 8 и т.п.) Функция bitcount в книге реализована с помощью сдвига переменной x в цикле for вправо на одну позицию и дальнейшей операции И с 01. Предлагается сделать то же самое только через x &= (x - 1). Я никак не могу понять принцип работы что книжного варианта, что предлагаемого. Попробую объяснить, давайте остановимся пока на книжном. Я ввел какое-то большое 8-битное число. Каждый раз при сдвиге (и до сдвига) я сравниваю его с единицей, которая дополнена нулями в левой части (00000001). Используется побитовая операция &. По-моей логике выражение (x & 01) будет равно только в том случае, если x ЦЕЛИКОМ равен единице, т.е. что у x 7 нулей и 1 единица, что у операнда в правой части то же самое( в нашем случае это единица). На практике же получается что компьютер сравнивает только самый правый бит. Как так получается? И какова будет логика работы предлагаемого варианта?

Решение задачи: «Побитовые операции»

textual
Листинг программы
#include <stdio.h>
 
size_t count_bits(const size_t number);
int main()
{
    const size_t number = 5;
    printf("\n%d\n", count_bits(number));
}
 
size_t count_bits(const size_t number)
{
    size_t counter = 0;
    auto on_bits = 0;
    const size_t QUANTITY_BITS = sizeof(number) * 8;
 
    while (counter < QUANTITY_BITS)
    {
        if ((number >> counter++) & 1)
        {
            on_bits++;
        }
    }
 
    return on_bits;
}

Объяснение кода листинга программы

  1. Включаем заголовочный файл для возможности использования функций ввода-вывода
  2. Функция count_bits() считает количество бит, установленных в единицу в числе number
  3. В функции main() создаем константную переменную number со значением 5
  4. Вызываем функцию count_bits() и передаем ей переменную number
  5. Выводим результат работы функции count_bits() на экран с помощью функции printf()
  6. В функции count_bits() создаем переменную counter для отслеживания количества просматриваемых бит
  7. Создаем переменную on_bits для подсчета количества найденных единиц
  8. Узнаем количество бит в числе number, умножая размер числа на 8 (2 в степени количества бит)
  9. Запускаем цикл while для перебора всех бит числа number
  10. Внутри цикла проверяем, является ли текущий бит единицей, используя побитовую операцию AND с 1
  11. Если бит является единицей, увеличиваем значение переменной on_bits на 1
  12. Возвращаем значение переменной on_bits из функции count_bits()
  13. Значение переменной on_bits будет содержать количество единиц в числе number

Оцени полезность:

10   голосов , оценка 3.7 из 5
Похожие ответы