Given an integer base 10, is there a known way of calculating how many 1s and 0s it has in binary without counting?

Solution 1:

I don't think there's a way. But since you have some stackoverflow posts, too, one approach might be to do it the "hard" way, print some results, and look for a pattern. Here's a two-line (so to speak) C program for that,

#include <stdio.h>
#include <stdlib.h>
int main ( int argc, char *argv[] ) {
  int n1 = ( argc>1? atoi(argv[1]) : 1 ),
      n2 = ( argc>2? atoi(argv[2]) : 10 );
  int  n = n1,  bin01count();
  for ( n=n1; n<=n2; n++ )
    printf(" %6d: %3d, %3d\n", n, bin01count(n,0), bin01count(n,1));
  exit(0);
  } /* --- end-of-function main() --- */
int bin01count ( int nbase10, int whichcount ) {
  int count0=0, count1=0;
  while ( nbase10 > 0 ) {
    if ( nbase10%2 == 1 ) count1++; else count0++;
    nbase10 /= 2; }
  return ( whichcount==1? count1 : count0 );
  } /* --- end-of-function bin01count() --- */
/* --- end-of-file bin01count.c --- */

And the default 1-to-10 run shows the expected

  1:   0,   1
  2:   1,   1
  3:   0,   2
  4:   2,   1
  5:   1,   2
  6:   1,   2
  7:   0,   3
  8:   3,   1
  9:   2,   2
 10:   2,   2

I'm not seeing much of any useful pattern there, nor for a few other ranges I took a quick look at. But maybe you want to look more carefully. And then, of course, please follow-up if you find anything interesting.

   E d i t
-------------
I subsequently noticed one maybe-interesting thing. It obviously has some straightforward explanation, since this all boils down to some pretty trivial number-theoretic stuff, but I can't see it myself...

Consider the integers whose binary representation contains the same number of 0's and 1's, e.g., in our 1-to-10 list above, that would be 2="10", 9="1001", and 10="1010". And in the 1-1000 range, there are 175 such numbers, with the last being 992="1111100000". And they're more-or-less uniformly distributed.

But guess what: the next one after 992 is 2079="100000011111", with absolutely no such numbers in the 1000-2000 range whatsoever. And then in the 2000-3000 range there are again 246 such numbers, which are again more-or-less uniformly distributed. And 3000-4000 has 215 such numbers.

But guess what: after 4032="111111000000", the next such number is 8255="10000000111111", with 146 such numbers in the 8000-9000 range. And this again continues more-or-less uniformly until 16256="11111110000000", after which 32895="1000000001111111" is next.

So the pattern seems to emerge...
  992="1111100000" followed by 2079="100000011111"
  4032="111111000000" followed by 8255="10000000111111"
  16256="11111110000000" followed by 32895="1000000001111111"
Numbers of the form "1111000000" begin a long gap that's ended by the subsequent number of the form "10000000111111". So exactly why is this??? It has nothing to do with your original question, per se. But it might well fit your comment below about "holiday project", which would seem to suggest a much wider latitude.