Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Bit Manipulation

Total Set Bits from 1 to N

Medium · Bit Manipulation · Asked at Amazon, Microsoft, Samsung

Print the total number of 1-bits in the binary representations of all integers from 1 to n.

Input

A single integer n.

Output

The total number of set bits.

Constraints

Bit k repeats a pattern of 2^k zeros then 2^k ones. For each k: full cycles · 2^k plus the ones in the last partial cycle.

Example 1

Input

3

Output

4

Example 2

Input

17

Output

35

Hints

  1. Counting bits number by number is far too slow for n = 10^15.
  2. Count per bit position instead: over 0..n, bit k cycles through 2^k zeros then 2^k ones. Full cycles contribute 2^k each; the partial last cycle contributes max(0, remainder − 2^k).

Approach

Let N = n + 1 (the count of numbers 0..n). For each bit k with 2^k ≤ N: cycle = 2^(k+1), full cycles give (N / cycle) · 2^k ones, and the leftover N % cycle numbers give max(0, N % cycle − 2^k) more. Summing over about 50 bit positions gives the answer in O(log n), well within 64-bit range.

Complexity: O(log n) time · O(1) space

Solution

C++ solution

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

int main() {
    long long n;
    cin >> n;
    long long N = n + 1, total = 0;
    for (int k = 0; (1LL << k) <= N; k++) {
        long long cycle = 1LL << (k + 1), half = 1LL << k;
        total += (N / cycle) * half + max(0LL, N % cycle - half);
    }
    cout << total << "\n";
    return 0;
}

Python solution

n = int(input())
N, total, k = n + 1, 0, 0
while (1 << k) <= N:
    cycle, half = 1 << (k + 1), 1 << k
    total += (N // cycle) * half + max(0, N % cycle - half)
    k += 1
print(total)

Java solution

import java.util.*;

public class Main {
    public static void main(String[] args) {
        long n = new Scanner(System.in).nextLong();
        long N = n + 1, total = 0;
        for (int k = 0; (1L << k) <= N; k++) {
            long cycle = 1L << (k + 1), half = 1L << k;
            total += (N / cycle) * half + Math.max(0, N % cycle - half);
        }
        System.out.println(total);
    }
}

Solve Total Set Bits from 1 to N online · All practice problems