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
- 1 ≤ n ≤ 10^15
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
- Counting bits number by number is far too slow for n = 10^15.
- 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