Grade 9 · Number basesCitește în română

Number of 1 bits in binary

Original: Numărul de biți 1 din scrierea în baza 2

O(log n)C++1734 lines2 examples

The idea

The base-2 digits are obtained just like the base-10 digits, except that we divide by 2: the last binary digit is n % 2. We count how many of them are 1. 13 = 1101 in base 2, so it has 3 one bits.

Original description (Romanian)

Cifrele în baza 2 se obțin la fel ca cifrele în baza 10, doar că împărțim la 2: ultima cifră binară este n % 2. Numărăm câte dintre ele sunt 1. 13 = 1101 în baza 2, deci are 3 biți de 1.

Complexity
O(log n)
Grade
Grade 9 (Clasa a IX-a)

Examples

Example 1

Input

13

Expected output

3
Example 2

Input

1024

Expected output

1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

numarul-bitilor-de-1.cpp
/*
 * Titlu: Numărul de biți 1 din scrierea în baza 2
 * Clasa: 9
 * Capitol: Baze de numerație
 * Descriere: Cifrele în baza 2 se obțin la fel ca cifrele în baza 10, doar că
 *            împărțim la 2: ultima cifră binară este n % 2. Numărăm câte dintre
 *            ele sunt 1. 13 = 1101 în baza 2, deci are 3 biți de 1.
 * Complexitate: O(log n)
 *
 * Exemplu
 * Intrare: 13
 * Ieșire: 3
 *
 * Exemplu
 * Intrare: 1024
 * Ieșire: 1
 */
#include <iostream>
using namespace std;

int main()
{
    long long n;
    int biti = 0;
    cin >> n;
    while (n > 0)
    {
        biti = biti + n % 2;
        n = n / 2;
    }
    cout << biti << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.