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

When I was solving Euler project problem #15 I realized that it can be solved 开发者_如何学Cwith 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?

---

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".

---

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)

---

If I understand you correctly then you just what p = nCr where r = n/2. So:

p = n! / ((n/2)! * (n/2)!)

---

The balanced values can be found directly by imagining that you're picking your path along the way (i.e. choose to go up n times out of 2n).

There are, therefore, C(2n,n) of those values, which is 2n! / (n! * n!). The total number of values is, of course, 2^2n. Using Stirling's approximation, we find

ln n! ~= n ln n - n + ln(2*pi*n)/2
ln 2n!/(n!*n!) = ln(2n!) - 2*ln(n!) ~= 2n*ln(2) - n + ln(4*pi*n)/2 - ln(2*pi*n)

so that the fraction of values which are good, C(2n,n)/2^(2n) is

exp(2n*ln(2) - n + ln(4*pi*n)/2 - ln(2*pi*n) - 2n*ln(2)) =
exp(-n)/sqrt(pi*n)

so the number of good values decrease exponentially.

This is why it's wise to just pick them out directly instead of test.

But if you really want to test, there are various bit-counting methods here. (Kernighan's is probably the fastest--note however that he wasn't the first person to notice it, and that an equivalent algorithm is already posted here!)

---

You could use a look-up table mapping an n-bt number to its 1-count. For example, if you always had 23-bit unsigned integers a lookup table of 16 bits and 7 bits would allow you to split the number and add the one-count from the lookup tables for the 16 and 7 bit portions. (The 7-bit look-up table could be just a section of the 16 bit table).

---

For an even value of 'i', the number of such numbers(equal 1's and 0's) between 2^i and 2^(i-1) are given by the following formula:

(i-1)!/[x! * (x-1)!]

where x=i/2.

I tried writing a program in C for generating this, but it overflowed. Then I did it using floating point arithmetic. Till i=56 its good. After that the accuracy decreases.

But BigInt libraries should be able to do this task without overflow.