Number of distinct non-empty subsequences of binary expansion A subsequence is any sequence that you can get from another by deleting any amount of characters. The distinct non-empty subsequences of 100 are 0, 1, 00, 10, 100. The distinct non-empty subsequences of 1010 are 0, 1, 00, 01, 10, 11, 010, 100, 101, 110, 1010.

Write a program or function that given a positive integer n returns the number of distinct non-empty subsequences of the binary expansion of n.

Example: since 4 is 100 in binary, and we saw that it had five distinct non-empty subsequences above, so f(4) = 5. Starting from n = 1, the sequence begins:

1, 3, 2, 5, 6, 5, 3, 7, 10, 11, 9, 8, 9, 7, 4, 9, 14, 17, 15, 16, 19, 17, 12


However, your program must work for any n &lt; 250 in under a second on any modern machine. Some large examples:

f(1099511627775) = 40
f(1099511627776) = 81
f(911188917558917) = 728765543
f(109260951837875) = 447464738
f(43765644099) = 5941674
Python 3, 95 bytes  83 bytes

[-12 bytes thanks to Mr.XCoder :)]



def f(x):
 v=[2,1];c=1
 for i in bin(x)[3:]:k=int(i);c+=v[k];v[1-k]+=v[k]
 return c


Try it online!

A note on the algorithm.
The algorithm computes the increment in unique subsequences given by the bit at a given position t.
The increment for the first bit is always 1. The algorithm then runs over the sequence of bits s(t) and adds the increment v[s(t)]. At each step, the increment for the complement of s(t), v[1 - s(t)] is updated to v[1]+v[0]. 
The final number is the sum of all increments. 

It should run in O(log2(n)), where n is the input number.