Разбор задачи «Сигнальные фонари»

Идея задачи

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

Проще говоря: нужно посчитать, сколько единиц в двоичной записи числа.

Например:

• 0 → 0 → ответ 0
• 11 → 1011 → ответ 3
• 128 → 10000000 → ответ 1

Это задача на битовые операции.

Что такое бит числа

Любое число в компьютере хранится в двоичном виде, то есть с помощью нулей и единиц.

Например:

• 5 = 101
• 10 = 1010
• 13 = 1101

Каждая 1 в записи означает, что соответствующий бит включён.

Значит, задача сводится к очень простой цели:

посчитать количество единиц в двоичной записи числа.

Первый способ — проверить все биты

Самая понятная идея: пройти по всем 32 битам числа и для каждого проверить, равен он 1 или 0.

Если i-й бит установлен, увеличиваем ответ.

Бит i включён, если выражение

n & (1 << i)

не равно нулю.

Решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    unsigned int n;
    cin >> n;

    int ans = 0;
    for (int i = 0; i < 32; i++) {
        if (n & (1u << i)) {
            ans++;
        }
    }

    cout << ans << '\n';
    return 0;
}

Решение на Python

n = int(input())

ans = 0
for i in range(32):
    if n & (1 << i):
        ans += 1

print(ans)

Этот способ хороший, потому что он очень прямой и понятный.

Но есть способ красивее.

Главная идея задачи

Существует очень полезный битовый приём:

n & (n - 1)

Эта операция удаляет у числа самый правый бит, равный 1.

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

Почему n & (n - 1) удаляет одну единицу

Рассмотрим число n = 12.

В двоичной записи:

12 = 1100

Тогда:

11 = 1011

Теперь выполним побитовое И:

1100 & 1011 = 1000

Одна единица исчезла.

Ещё пример:

13 = 1101

12 = 1100

1101 & 1100 = 1100

Снова исчез именно самый правый бит 1.

Почему это происходит

Когда мы вычитаем единицу из числа:

• самый правый бит 1 превращается в 0;
• все нули справа от него превращаются в единицы;
• биты левее не меняются.

После этого операция & оставляет только те биты, которые равны 1 в обоих числах.

В результате самый правый установленный бит исчезает.

Как построить алгоритм

Пока число не равно нулю:

• удаляем одну единицу с помощью n &= (n - 1);
• увеличиваем счётчик.

Когда число станет нулём, это значит, что все единицы уже удалены.

Количество выполненных шагов и будет ответом.

Пошаговый пример

Пусть n = 13.

В двоичной записи:

13 = 1101

Первый шаг

1101 -> 1100

Удалили одну единицу.

Второй шаг

1100 -> 1000

Удалили ещё одну единицу.

Третий шаг

1000 -> 0000

Удалили последнюю единицу.

Всего было 3 шага, значит ответ равен 3.

Алгоритм

1. Считываем число n.
2. Заводим переменную ans = 0.

3. Пока n != 0:

   • делаем n = n & (n - 1);
   • увеличиваем ans на 1.
4. Выводим ans.

Почему решение правильное

Каждая операция n & (n - 1) удаляет ровно одну единицу.

Значит:

• после первой операции единиц станет на одну меньше;
• после второй — ещё на одну меньше;
• и так далее.

Когда число станет равно нулю, единиц в нём уже не останется.

Следовательно, количество выполненных операций в точности равно количеству единиц в исходном числе.

Значит, алгоритм действительно находит правильный ответ.

Сложность

Пусть в числе n содержится k единичных битов.

Тогда цикл выполнится ровно k раз.

Значит:

• время работы: O(k)
• память: O(1)

Так как число 32-битное, максимум таких шагов может быть только 32.

Основное решение на C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    unsigned int n;
    cin >> n;

    int ans = 0;
    while (n) {
        n &= (n - 1);
        ans++;
    }

    cout << ans << '\n';
    return 0;
}

Основное решение на Python

n = int(input())

ans = 0
while n:
    n &= n - 1
    ans += 1

print(ans)

Альтернативные решения

Через двоичную запись в Python

n = int(input())
print(bin(n).count('1'))

Так можно решить задачу очень коротко.

Но полезнее понимать именно битовую идею с n & (n - 1).

Через встроенную функцию в C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    unsigned int n;
    cin >> n;
    cout << __builtin_popcount(n) << '\n';
    return 0;
}

Это тоже хорошее решение, но в учебной задаче лучше уметь решать её самостоятельно.

Частые ошибки

1. Забыть про число 0

Если n = 0, цикл не выполнится ни разу, и ответ будет 0.

Это правильно.

2. Думать, что n & (n - 1) удаляет все единицы сразу

Нет, эта операция удаляет только одну единицу — самую правую.

3. Небрежно работать со сдвигами в C++

Если проверяете биты циклом, лучше писать так:

1u << i

а не просто 1 << i.

Примеры

Вывод

В этой задаче нужно просто посчитать количество единиц в двоичной записи числа.

Самое красивое наблюдение такое:

• операция n & (n - 1) удаляет самый правый установленный бит;
• значит, можно удалять единицы по одной и считать количество шагов.

Это даёт короткое, быстрое и очень полезное решение, которое часто встречается в задачах на битовые операции.

Финальная эталонка

C++

#include <bits/stdc++.h>
using namespace std;

int main() {
    unsigned int n;
    cin >> n;

    int ans = 0;
    while (n) {
        n &= (n - 1);
        ans++;
    }

    cout << ans << '\n';
    return 0;
}

Python

n = int(input())

ans = 0
while n:
    n &= n - 1
    ans += 1

print(ans)