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

For number which represented with N bits you have some exponential factor of such numbers with same count of zeros and ones. So you definitely have to write some code, this will require at least linear time.

For example you can do:

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

This will give you a number of ones inside n when you will be able to compare and decide.

Answer 2

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

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

Answer 3

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 4

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!)

Answer 5

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)

Answer 6

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