Битовая математика Arduino

Узнайте о битовой математике и о том, как управлять отдельными битами в скетчах Arduino.

Автор: Don Cross

Последнее обновление: 27.07.2023

Примечание

Статья была обновлена 28.09.2022 автором Hannes Siebeneicher.

Зачастую при программировании в среде Arduino (или на любом другом компьютере) возникает необходимость управлять отдельными битами. Вот несколько ситуаций, в которых битовая математика может быть полезна:

• Экономия памяти за счёт упаковки до 8 булевых значений (истина/ложь) в один байт.

• Включение/выключение отдельных битов в регистре управления или регистре порта оборудования.

• Выполнение определённых арифметических операций, связанных с умножением или делением на степени двойки.

В этой статье мы сначала рассмотрим основные побитовые операторы языка C++. Затем научимся комбинировать их для выполнения определённых распространённых и полезных операций. Эта статья основана на руководстве по битовой математике от CosineKitty.

Двоичная система счисления

Для лучшего объяснения побитовых операторов в этом руководстве большинство целочисленных значений будут выражены в двоичной записи, известной также как система счисления с основанием два. В этой системе все целочисленные значения используют только цифры 0 и 1 для каждого разряда. Именно так практически все современные компьютеры хранят данные внутри. Каждая цифра 0 или 1 называется битом, сокращённо от binary digit (двоичная цифра).

В привычной десятичной системе (с основанием десять) число, например 572, означает 5*10^2 + 7*10^1 + 2*10^0. Аналогично, в двоичной системе число 11010 означает 1*2^4 + 1*2^3 + 0*2^2 + 1*2^1 + 0*2^0 = 16 + 8 + 2 = 26.

Крайне важно понимать, как работает двоичная система, чтобы следовать остальной части этого руководства. Если вам нужна помощь в этой области, хорошей отправной точкой является статья Википедии о двоичной системе.

Arduino позволяет задавать двоичные числа с помощью префикса 0b, например 0b11 == 3. Для обратной совместимости также определены константы B0 .. B11111111, которые можно использовать аналогичным образом.

Побитовое И (AND)

Оператор побитового И в C++ обозначается одиночным амперсандом & и используется между двумя целочисленными выражениями. Побитовое И выполняется независимо для каждой битовой позиции окружающих выражений согласно следующему правилу: если оба входных бита равны 1, то результирующий бит равен 1, иначе — 0. Другой способ выразить это:

0 & 0 == 0
0 & 1 == 0
1 & 0 == 0
1 & 1 == 1

В Arduino тип int является 16-битным значением, поэтому использование & между двумя выражениями int вызывает 16 одновременных операций AND. В следующем фрагменте кода:

int a =  92;    // двоично: 0000000001011100
int b = 101;    // двоично: 0000000001100101
int c = a & b;  // результат: 0000000001000100, или 68 в десятичной.

Каждый из 16 битов a и b обрабатывается с помощью побитового AND, и все 16 результирующих битов сохраняются в c, давая значение 01000100 в двоичном виде, что равно 68 в десятичном.

Одним из наиболее распространённых применений побитового AND является выбор конкретного бита (или битов) из целочисленного значения — этот приём часто называют маскированием. Например, чтобы получить доступ к наименее значимому биту переменной x и сохранить его в другую переменную y, можно использовать следующий код:

int x = 5;       // двоично: 101
int y = x & 1;   // теперь y == 1
x = 4;           // двоично: 100
y = x & 1;       // теперь y == 0

Побитовое ИЛИ (OR)

Оператор побитового ИЛИ в C++ обозначается символом вертикальной черты |. Как и оператор &, оператор | действует независимо на каждый бит в двух окружающих целочисленных выражениях, но выполняет другую операцию. Побитовое ИЛИ двух битов равно 1, если один или оба входных бита равны 1, в противном случае — 0. Иными словами:

0 | 0 == 0
0 | 1 == 1
1 | 0 == 1
1 | 1 == 1

Вот пример использования побитового ИЛИ в коде на C++:

int a =  92;    // двоично: 0000000001011100
int b = 101;    // двоично: 0000000001100101
int c = a | b;  // результат: 0000000001111101, или 125 в десятичной.

Побитовое ИЛИ часто используется для того, чтобы гарантированно установить определённый бит (в 1) в заданном выражении. Например, чтобы скопировать биты из a в b, при этом обязательно установив наименьший бит в 1, используйте следующий код:

b = a | 1;

Побитовое исключающее ИЛИ (XOR)

В C++ существует несколько необычный оператор, называемый побитовое исключающее ИЛИ, также известный как побитовое XOR. (По-русски это произносится как «экс-ор».) Оператор побитового XOR записывается с помощью символа каретки ^. Этот оператор похож на оператор побитового ИЛИ |, за исключением того, что он принимает значение 1 для данной позиции тогда, когда ровно один из входных битов на этой позиции равен 1. Если оба равны 0 или оба равны 1, оператор XOR возвращает 0:

0 ^ 0 == 0
0 ^ 1 == 1
1 ^ 0 == 1
1 ^ 1 == 0

Другой способ смотреть на побитовое XOR: каждый бит в результате равен 1, если входные биты различны, или 0, если они одинаковы.

Вот простой пример кода:

int x = 12;     // двоично: 1100
int y = 10;     // двоично: 1010
int z = x ^ y;  // двоично: 0110, или десятичное 6

Оператор ^ часто используется для переключения (т.е. изменения с 0 на 1 или с 1 на 0) некоторых битов в целочисленном выражении, оставляя другие нетронутыми. Например:

y = x ^ 1;   // переключить наименьший бит x и сохранить результат в y.

Побитовое НЕ (NOT)

Оператор побитового НЕ в C++ обозначается символом тильды ~. В отличие от & и |, оператор побитового НЕ применяется к единственному операнду справа от него. Побитовое НЕ изменяет каждый бит на противоположный: 0 становится 1, а 1 становится 0. Например:

int a = 103;    // двоично:  0000000001100111
int b = ~a;     // двоично:  1111111110011000 = -104

Вас может удивить отрицательное число -104 в качестве результата этой операции. Это происходит потому, что старший бит переменной int является так называемым знаковым битом. Если старший бит равен 1, число интерпретируется как отрицательное. Такое кодирование положительных и отрицательных чисел называется дополнением до двух. Для получения дополнительной информации смотрите статью Википедии о дополнении до двух.

Кстати, интересно отметить, что для любого целого числа x выражение ~x равно -x-1.

Иногда знаковый бит в знаковом целочисленном выражении может приводить к нежелательным неожиданностям, как мы увидим позже.

Операторы сдвига битов

В C++ существуют два оператора сдвига битов: оператор сдвига влево << и оператор сдвига вправо >>. Эти операторы вызывают сдвиг битов левого операнда влево или вправо на количество позиций, заданных правым операндом. Например:

int a = 5;        // двоично: 0000000000000101
int b = a << 3;   // двоично: 0000000000101000, или 40 в десятичной
int c = b >> 3;   // двоично: 0000000000000101, или снова 5, как в начале

Когда значение x сдвигается на y битов (x << y), крайние левые y битов x теряются, буквально сдвигаясь в небытие:

int a = 5;        // двоично: 0000000000000101
int b = a << 14;  // двоично: 0100000000000000 - первая 1 в 101 была отброшена

Если вы уверены, что ни одна из единиц в значении не сдвигается в небытие, простой способ думать об операторе сдвига влево — что он умножает левый операнд на 2, возведённое в степень правого операнда. Например, для получения степеней двойки можно использовать следующие выражения:

1 <<  0  ==    1
1 <<  1  ==    2
1 <<  2  ==    4
1 <<  3  ==    8
...
1 <<  8  ==  256
1 <<  9  ==  512
1 << 10  == 1024
...

Когда x сдвигается вправо на y битов (x >> y), и старший бит в x равен 1, поведение зависит от точного типа данных x. Если x имеет тип int, старший бит является знаковым битом, определяющим, является ли x отрицательным или нет, как обсуждалось выше. В этом случае знаковый бит копируется в младшие биты по эзотерическим историческим причинам:

int x = -16;     // двоично: 1111111111110000
int y = x >> 3;  // двоично: 1111111111111110

Это поведение, называемое расширением знака, зачастую не является желаемым. Вместо этого вы можете захотеть, чтобы нули сдвигались справа налево. Оказывается, правила сдвига вправо различны для выражений типа unsigned int, поэтому можно использовать приведение типа, чтобы предотвратить копирование единиц слева:

int x = -16;               // двоично: 1111111111110000
int y = unsigned(x) >> 3;  // двоично: 0001111111111110

Если вы осторожно избегаете расширения знака, оператор сдвига вправо >> можно использовать для деления на степени двойки. Например:

int x = 1000;
int y = x >> 3;   // целочисленное деление 1000 на 8, в результате y = 125.

Операторы присваивания

Зачастую в программировании требуется выполнить операцию над значением переменной x и сохранить изменённое значение обратно в x. В большинстве языков программирования, например, можно увеличить значение переменной x на 7 с помощью следующего кода:

x = x + 7;    // увеличить x на 7

Поскольку подобное встречается в программировании очень часто, C++ предоставляет краткую нотацию в виде специализированных операторов присваивания. Приведённый выше фрагмент кода можно записать более лаконично как:

x += 7;    // увеличить x на 7

Оказывается, что побитовое AND, побитовое OR, сдвиг влево и сдвиг вправо также имеют краткие операторы присваивания. Вот пример:

int x = 1;  // двоично: 0000000000000001
x <<= 3;    // двоично: 0000000000001000
x |= 3;     // двоично: 0000000000001011 - потому что 3 это 11 в двоичной
x &= 1;     // двоично: 0000000000000001
x ^= 4;     // двоично: 0000000000000101 - переключение по маске 100
x ^= 4;     // двоично: 0000000000000001 - переключение по маске 100 снова

Для оператора побитового НЕ ~ краткого оператора присваивания не существует; если вы хотите переключить все биты в x, нужно сделать следующее:

x = ~x;    // переключить все биты x и сохранить обратно в x

Предостережение: побитовые операторы и булевы операторы

Очень легко спутать побитовые операторы в C++ с булевыми операторами. Например, оператор побитового AND & не является тем же, что и булев оператор AND &&, по двум причинам:

• Они вычисляют числа по-разному. Побитовый & действует независимо на каждый бит своих операндов, тогда как && преобразует оба операнда в булево значение (true == 1 или false == 0), а затем возвращает единственное значение true или false. Например, 4 & 2 == 0, потому что 4 — это 100 в двоичной и 2 — это 010 в двоичной, и ни один бит не равен 1 в обоих числах одновременно. Однако 4 && 2 == true, а true в числовом выражении равно 1. Это потому, что 4 — не ноль, и 2 — не ноль, поэтому оба считаются булевыми значениями true.

• Побитовые операторы всегда вычисляют оба своих операнда, тогда как булевы операторы используют так называемое вычисление с коротким замыканием. Это имеет значение только в том случае, если операнды имеют побочные эффекты, такие как вывод данных или изменение значения чего-либо в памяти. Вот пример того, как две похожие строки кода могут вести себя совершенно по-разному:

int fred (int x)
{
    Serial.print ("fred ");
    Serial.println (x, DEC);
    return x;
}

void setup()
{
    Serial.begin (9600);
}

void loop()
{
    delay(1000);    // подождать 1 секунду, чтобы не переполнить вывод данными!
    int x = fred(0) & fred(1);
}

Если вы скомпилируете и загрузите эту программу, а затем откроете монитор последовательного порта в Arduino GUI, каждую секунду вы будете видеть следующие строки текста:

fred 0
fred 1

Это происходит потому, что вызываются и fred(0), и fred(1), в результате чего генерируется вывод, возвращаемые значения 0 и 1 побитово складываются по AND, сохраняя 0 в x. Если вы отредактируете строку

int x = fred(0) & fred(1);

и замените побитовый & его булевым аналогом &&:

int x = fred(0) && fred(1);

и скомпилируете, загрузите и снова запустите программу, вас может удивить то, что в окне монитора последовательного порта каждую секунду будет повторяться только одна строка текста:

fred 0

Почему так происходит? Это потому, что булев оператор && использует короткое замыкание: если его левый операнд равен нулю (т.е. false), уже известно, что результат выражения будет false, поэтому нет необходимости вычислять правый операнд. Иными словами, строка кода

int x = fred(0) && fred(1);

по смыслу идентична:

int x;
if (fred(0) == 0) {
    x = false;  // сохраняет 0 в x
} else {
    if (fred(1) == 0) {
        x = false;  // сохраняет 0 в x
    } else {
        x = true;   // сохраняет 1 в x
    }
}

Очевидно, что булев оператор && является гораздо более лаконичным способом выражения этой удивительно сложной логики.

Как и между побитовым AND и булевым AND, существуют различия между побитовым OR и булевым OR. Оператор побитового OR | всегда вычисляет оба своих операнда, тогда как булев оператор OR || вычисляет правый операнд только тогда, когда левый операнд равен false (нулю). Также побитовый | действует независимо на все биты своих операндов, тогда как булев || рассматривает оба операнда как истинные (ненулевые) или ложные (нулевые) и возвращает либо true (если один из операндов ненулевой), либо false (если оба операнда равны нулю).

Всё вместе: решение типичных задач

Теперь начнём изучать, как можно комбинировать различные побитовые операторы для выполнения полезных задач с использованием синтаксиса C++ в среде Arduino.

О регистрах портов микроконтроллера Atmega8

Обычно, когда вы хотите читать или записывать данные на цифровые выводы Atmega8, вы используете встроенные функции digitalRead() или digitalWrite(), предоставляемые средой Arduino. Предположим, что в функции setup() вы хотите определить цифровые выводы с 2 по 13 как выходы, а затем установить выводы 11, 12 и 13 в HIGH, а все остальные — в LOW. Вот как обычно это достигается:

void setup()
{
    int pin;
    for (pin=2; pin <= 13; ++pin) {
        pinMode (pin, OUTPUT);
    }
    for (pin=2; pin <= 10; ++pin) {
        digitalWrite (pin, LOW);
    }
    for (pin=11; pin <= 13; ++pin) {
        digitalWrite (pin, HIGH);
    }
}

Оказывается, есть способ добиться того же самого, используя прямой доступ к аппаратным портам Atmega8 и побитовые операторы:

void setup()
{
    // установить вывод 1 (передача Serial) и выводы 2..7 как выходы,
    // но оставить вывод 0 (приём Serial) как вход
    // (иначе последовательный порт перестанет работать!) ...
    DDRD = B11111110;  // цифровые выводы 7,6,5,4,3,2,1,0

    // установить выводы 8..13 как выходы...
    DDRB = B00111111;  // цифровые выводы -,-,13,12,11,10,9,8

    // выключить цифровые выводы 2..7 ...
    PORTD &= B00000011;   // выключает 2..7, не трогая выводы 0 и 1

    // одновременно записать значения в выводы 8..13...
    PORTB = B00111000;   // включает 13,12,11; выключает 10,9,8
}

Этот код использует тот факт, что регистры управления DDRD и DDRB каждый содержат 8 битов, определяющих, является ли данный цифровой вывод выходом (1) или входом (0). Два старших бита DDRB не используются, поскольку цифрового вывода 14 или 15 на Atmega8 не существует. Аналогично, регистры портов PORTB и PORTD содержат по одному биту для последнего записанного значения каждого цифрового вывода: HIGH (1) или LOW (0).

В целом, делать подобное не является хорошей идеей. Почему? Вот несколько причин:

• Код становится значительно сложнее отлаживать и поддерживать, а другим людям гораздо труднее его понять. Процессору требуется лишь несколько микросекунд для выполнения кода, но у вас могут уйти часы на то, чтобы разобраться, почему он не работает правильно, и исправить это! Ваше время ценно, не так ли? А время компьютера очень дёшево, измеряется стоимостью электричества, которым вы его питаете. Обычно гораздо лучше писать код наиболее очевидным способом.

• Код менее переносим. Если вы используете digitalRead() и digitalWrite(), гораздо проще написать код, который будет работать на всех микроконтроллерах Atmel, тогда как регистры управления и портов могут различаться на разных видах микроконтроллеров.

• Гораздо легче вызвать непреднамеренные неисправности при прямом доступе к порту. Обратите внимание, что строка DDRD = B11111110; выше указывает на необходимость оставить вывод 0 как входной. Вывод 0 — это линия приёма последовательного порта. Очень легко случайно превратить вывод 0 в выходной, вследствие чего последовательный порт перестанет работать! Это было бы очень запутанным, когда вы вдруг не сможете принимать последовательные данные, не правда ли?

Итак, вы можете сказать себе: отлично, зачем тогда вообще это использовать? Вот некоторые положительные аспекты прямого доступа к портам:

• Если у вас заканчивается память программы, вы можете использовать эти приёмы, чтобы сделать код компактнее. Одновременная запись на несколько аппаратных выводов через регистры портов требует значительно меньше байтов скомпилированного кода, чем использование цикла for для установки каждого вывода по отдельности. В некоторых случаях это может быть разницей между тем, поместится ли ваша программа во flash-память или нет!

• Иногда может потребоваться одновременно установить несколько выходных выводов в один и тот же момент времени. Вызов digitalWrite(10,HIGH); с последующим digitalWrite(11,HIGH); приведёт к тому, что вывод 10 перейдёт в HIGH на несколько микросекунд раньше вывода 11, что может запутать определённые чувствительные ко времени внешние цифровые схемы. В качестве альтернативы можно установить оба вывода в HIGH в точно одно и то же мгновение с помощью PORTB |= B1100;.

• Возможно, вам потребуется очень быстро переключать выводы — в пределах долей микросекунды. Если вы посмотрите на исходный код в lib/targets/arduino/wiring.c, вы увидите, что digitalRead() и digitalWrite() каждая состоит примерно из дюжины строк кода, которые компилируются в довольно много машинных команд. Каждая машинная команда требует один такт при тактовой частоте 16 МГц, что может существенно накапливаться в приложениях, критичных ко времени. Прямой доступ к порту позволяет выполнить ту же работу за значительно меньшее количество тактов.

Более сложный пример: отключение прерывания

Теперь возьмём то, что мы узнали, и разберёмся в некоторых странных вещах, которые иногда делают продвинутые программисты в своём коде. Например, что означает следующее?

// Отключить прерывание.
GICR &= ~(1 << INT0);

Это реальный пример кода из библиотеки времени выполнения Arduino 0007, из файла lib\targets\arduino\winterrupts.c. Прежде всего, нужно знать, что означают GICR и INT0. Оказывается, GICR — это регистр управления, определяющий, включены (1) или выключены (0) определённые прерывания процессора. Если поискать в стандартных заголовочных файлах Arduino определение INT0, можно найти различные определения. В зависимости от типа микроконтроллера, для которого вы пишете, это либо:

#define INT0   6

либо:

#define INT0   0

Таким образом, на некоторых процессорах приведённая выше строка кода скомпилируется в:

GICR &= ~(1 << 0);

а на других — в:

GICR &= ~(1 << 6);

Рассмотрим последний случай, так как он более показателен. Прежде всего, значение (1 << 6) означает, что мы сдвигаем 1 влево на 6 битов, что равносильно 2^6, то есть 64. В данном контексте удобнее рассмотреть это значение в двоичном виде: 01000000. Затем к этому значению применяется оператор побитового НЕ ~, в результате чего все биты инвертируются: 10111111. Далее используется оператор присваивания с побитовым AND, поэтому приведённый выше код имеет тот же эффект, что и:

GICR = GICR & B10111111;

Это оставляет все биты GICR нетронутыми, за исключением второго по значимости бита, который сбрасывается в 0.

В случае, когда INT0 определён как 0 для вашего конкретного микроконтроллера, строка кода будет интерпретироваться как:

GICR = GICR & B11111110;

что сбрасывает наименьший бит в регистре GICR, оставляя остальные биты без изменений. Это пример того, как среда Arduino может поддерживать широкий спектр микроконтроллеров с помощью единственной строки исходного кода библиотеки времени выполнения.

Экономия памяти путём упаковки нескольких элементов данных в один байт

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

Простой способ хранения такого изображения — использование массива целых чисел. Код для этого подхода может выглядеть так:

const prog_uint8_t BitMap[5][7] = {   // хранить в памяти программ для экономии RAM
    {1,1,0,0,0,1,1},
    {0,0,1,0,1,0,0},
    {0,0,0,1,0,0,0},
    {0,0,1,0,1,0,0},
    {1,1,0,0,0,1,1}
};

void DisplayBitMap()
{
    for (byte x=0; x<5; ++x) {
        for (byte y=0; y<7; ++y) {
            byte data = pgm_read_byte (&BitMap[x][y]);   // получить данные из памяти программ
            if (data) {
                // включить светодиод в позиции (x,y)
            } else {
                // выключить светодиод в позиции (x,y)
            }
        }
    }
}

Если бы это была единственная битовая карта в программе, это было бы простым и эффективным решением. Мы используем 1 байт памяти программ (из доступных примерно 7K в Atmega8) для каждого пикселя нашей битовой карты, что в сумме составляет 35 байт. Это не так много, но что если нужна битовая карта для каждого из 96 печатаемых символов набора символов ASCII? Это потребовало бы 96 * 35 = 3360 байт, что оставило бы значительно меньше flash-памяти для хранения кода программы.

Существует гораздо более эффективный способ хранения битовой карты. Заменим двумерный массив выше одномерным массивом байтов. Каждый байт содержит 8 битов, и мы будем использовать 7 младших битов каждого для представления 7 пикселей в столбце нашей битовой карты 5x7:

const prog_uint8_t BitMap[5] = {   // хранить в памяти программ для экономии RAM
    B1100011,
    B0010100,
    B0001000,
    B0010100,
    B1100011
};

(Здесь мы используем предопределённые двоичные константы, доступные начиная с Arduino 0007.) Это позволяет нам использовать 5 байт для каждой битовой карты вместо 35. Но как использовать этот более компактный формат данных? Вот ответ: перепишем функцию DisplayBitMap() для доступа к отдельным битам каждого байта в BitMap…

void DisplayBitMap()
{
    for (byte x=0; x<5; ++x) {
        byte data = pgm_read_byte (&BitMap[x]);   // получить данные из памяти программ
        for (byte y=0; y<7; ++y) {
            if (data & (1<<y)) {
                // включить светодиод в позиции (x,y)
            } else {
                // выключить светодиод в позиции (x,y)
            }
        }
    }
}

Ключевая строка для понимания:

if (data & (1<<y)) {

Выражение (1<<y) выбирает заданный бит внутри data, к которому мы хотим обратиться. Затем с помощью побитового AND data & (1<<y) проверяет данный бит. Если этот бит установлен, результат ненулевой, что заставляет оператор if воспринимать его как истину. В противном случае, если бит равен нулю, он воспринимается как ложь, и выполняется ветка else.

Краткий справочник

В этом кратком справочнике мы обозначаем биты 16-битного целого числа, начиная с наименее значимого бита как бит 0, и наиболее значимого бита (знакового бита, если целое число знаковое) как бит 15, что показано на следующей схеме:

Везде, где встречается переменная n, её значение предполагается от 0 до 15.

y = (x >> n) & 1;    // n=0..15.  сохраняет n-й бит x в y.  y становится 0 или 1.

x &= ~(1 << n);      // устанавливает n-й бит x в 0. остальные биты не затрагиваются.

x &= (1<<(n+1))-1;   // оставляет нетронутыми n младших битов x; все старшие биты устанавливаются в 0.

x |= (1 << n);       // устанавливает n-й бит x в 1. остальные биты не затрагиваются.

x ^= (1 << n);       // переключает n-й бит x. остальные биты не затрагиваются.

x = ~x;              // переключает ВСЕ биты в x.

Вот интересная функция, которая использует и побитовый &, и булев &&. Она возвращает true тогда и только тогда, когда заданное 32-битное целое число x является точной степенью двойки, т.е. 1, 2, 4, 8, 16, 32, 64 и т.д. Например, вызов IsPowerOfTwo(64) вернёт true, а IsPowerOfTwo(65) вернёт false. Чтобы понять, как работает эта функция, рассмотрим число 64 как пример степени двойки. В двоичной системе 64 — это 1000000. Когда мы вычитаем 1 из 1000000, получаем 0111111. Применяя побитовый &, результат равен 0000000. Но если сделать то же самое с 65 (двоичное 1000001), получаем 1000001 & 1000000 == 1000000, что не равно нулю.

bool IsPowerOfTwo (long x)
{
    return (x > 0) && (x & (x-1) == 0);
}

Вот функция, которая считает, сколько битов в 16-битном целом числе x равны 1, и возвращает это количество:

int CountSetBits (int x)
{
    int count = 0;
    for (int n=0; n<16; ++n) {
        if (x & (1<<n)) {
            ++count;
        }
    }
    return count;
}

Ещё один способ:

int CountSetBits (int x)
{
    unsigned int count;
    for (count = 0; x; count++)
        x &= x - 1;
    return count;
}

Различные приёмы для распространённых операций с битами можно найти здесь.