A ledger validator flags each integer by the parity of its Hamming weight (the number of 1 bits). An integer is called balanced when its number of set bits is even (0 counts as even).
Given n, count how many integers x with 1 <= x <= n are balanced (have an even number of set bits).
Input format
Line 1: an integer n.
Output format
A single integer: the count of integers in [1, n] whose set-bit count is even.
Constraints
- 1 <= n <= 1000000000