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
52
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
109
110
111
112
113 public static void main( String[] args ) throws Exception
114 {
115 new bitcounting().doit();
116 }
117
118 }