The Java Program: B_counting/bitcounting.java

  1 import java.io.*;
  2 import java.util.*;
  3 
  4 public class bitcounting 
  5 {
  6     public Scanner sc;
  7     public PrintStream ps;
  8     
  9     public int bitcount( int n )
 10     {
 11         int count = 0;
 12         while( n>0 )
 13         {
 14             if( (n&1)==1 ) ++count;
 15             n /= 2;
 16         }
 17         
 18         return count;
 19     }
 20 
 21     public long counts[][] = new long[65][65];
 22     public int steps[] = new int[65];
 23     public long totals[] = new long[65];
 24 
 25     public long countup( long n, int k  )
 26     {
 27         Arrays.fill( totals, 0 );
 28         int sofar = 0;
 29         for( int bit=63; bit>=0; --bit)
 30         {
 31             if( (n&(1l<<bit))!=0 )
 32             {
 33                 for( int i=63; i-sofar>=0; i--)
 34                 {
 35                     totals[i] += counts[bit][i-sofar];    
 36                 }
 37                 ++sofar;
 38             } 
 39         }
 40            
 41         long grandtotal = 0;
 42         for( int i=0; i<steps.length; i++ )
 43         {
 44             if( 1+steps[i]==k ) grandtotal += totals[i];
 45         }
 46         
 47         return n<2 ? 0 : grandtotal;
 48     }
 49     
 50     /**
 51      * Driver.
 52      * @throws Exception
 53      */
 54     public void doit() throws Exception
 55     {
 56         sc = new Scanner( new File( "bitcounting.judge" ) );
 57         ps = new PrintStream( new FileOutputStream( "bitcounting.out" ) ); 
 58                 
 59         for( int i=0; i<counts.length; i++ )
 60         {
 61             Arrays.fill( counts[i], 0 );
 62             counts[i][1] = i;
 63         }
 64                
 65         for( int i=1; i<counts.length; i++ ) 
 66         {
 67             for( int j=2; j<counts[i].length; j++ )
 68             {
 69                 counts[i][j] = counts[i-1][j] + counts[i-1][j-1];
 70             }
 71         }
 72         
 73         for( int i=0; i<counts.length; i++ )
 74         {
 75             ++counts[i][1];
 76         }
 77                 
 78         steps[0] = 0;
 79         steps[1] = 0;
 80         for( int i=2; i<steps.length; i++ )
 81         {
 82             steps[i] = 1 + steps[bitcount(i)];
 83         }
 84         
 85         for(;;)
 86         {
 87             long lo = sc.nextLong();
 88             long hi = sc.nextLong();
 89             int x = sc.nextInt();
 90             if( lo==0 ) break;
 91             
 92             long total;
 93             if( x>0 )
 94             {
 95                 total = countup(hi,x) - countup(lo-1,x);
 96                 if( lo==1 && x==1 && hi!=1 ) --total;
 97             }
 98             else
 99             {
100                 total = lo==1 ? 1 : 0;
101             }
102             ps.println( total );
103             System.out.println( total );            
104         }
105     }
106     
107     /**
108      * The main just creates an object and calls doit().
109      * 
110      * @param args Command line args, necessary but unused.
111      * @throws Exception
112      */
113     public static void main( String[] args ) throws Exception
114     {
115         new bitcounting().doit();
116     }
117 
118 }