Baseline Bit Manipulation · Learn Bit Manipulation O(log n) — one recursive block per set bit of n · O(log n) recursion depth
Every fleet vessel broadcasts its ID in binary beacon pulses, one pulse per set bit. Control wants the total pulse count across IDs 1 through n. Counting vessel by vessel is too slow, so dispatch exploits the block structure of binary numbers: below the highest power of two, each bit position holds a predictable share of pulses, and the remainder above it is one more block of the same shape.
Input: An integer n.
Output: The total number of set bits across all integers from 1 to n inclusive.
1 <= n <= 10^9Input: {"n":4}
Output: 5
IDs 1..4 flash 1 + 1 + 2 + 1 = 5 pulses in total.
Input: {"n":7}
Output: 12
Across 1..7 every bit position below 8 turns on exactly four times: 3 * 4 = 12.