Count numbers with same popcount up to all-ones bound

Problem

For any positive integer n, define f(n) as the smallest integer >= n whose binary representation consists only of 1 bits.

Equivalently, if k is the bit-length of n (so 2^(k-1) <= n <= 2^k - 1), then:

• f(n) = 2^k - 1 (binary: k ones)

You are given a positive integer n. Let popcount(x) be the number of set bits in x.

Task

Count how many integers m satisfy all of the following:

• 1 <= m <= f(n)
• m != n
• popcount(m) = popcount(n)

Return this count.

Input

• A positive integer n .

Output

• An integer: the count of valid m .

Constraints

• 1 <= n <= 10^18
• Target time complexity: O(log n) .

Examples

1. n = 5 (binary 101 )

• k=3 , f(n)=7 (binary 111 )
• Numbers <=7 with two set bits: 3(011), 5(101), 6(110)
• Excluding n=5 → answer 2

2. n = 7 (binary 111 )

• k=3 , f(n)=7
• Only number with three set bits is 7 itself → answer 0