Binary numbers with the same quantity of 0s and 1s

Question

When I was solving Euler project problem #15 I realized that it can be solved with the # of combinations of ways of the route from start to end. The route generated always has the same size of right or down choices (or 0s and 1s) and the right routes always have the same qty of 0s and 1s. So qty of numbers with the same qty of 0s and 1s in a binary word are C(2,1) for 1bit length C(4,2) for 2bit " " C(6,3) for 4bit " " ...

Now comes my questions: Is there a function that solves if a number has the same qty of 0s and 1s? I guess that it would be more like a logical function, I don't want to iterate all the digits or use regex (that would be worse than iterate).

**Other question is about the growth and the space between this "balanced" values?

Answer 1

You are looking for a popcount function, which counts the number of set bits in a given number. Some processors have it builtin, some don't.

c=0; while (n &= (n-1)) c++;

does the job, but destroys n.

See this link for better algorithms, or google "popcount".

Answer 2

As a follow up to Paul R's answer, there is a simplification of the formula for the central binomial coefficient, see http://mathworld.wolfram.com/CentralBinomialCoefficient.html

p = n! / ((n/2)!)² = 2^n/2 (n-1)!! / (n/2)!

k!! is the "double factorial", which means you skip every other number when calculating: k!! = k * (k-2) * (k-4) * ... (as long as the factor is positive).

For your calculation a lot of numbers will cancel out (you can use the gcd for this when calculating numerator and denominator simultaneously)