fork(3) download
copy 
  1. #include <stdio.h>
  2.  
  3. unsigned long long binom(unsigned n, unsigned k) {
  4.     if (k == 0 || n == k) return 1;
  5.     if (n < k) return 0;
  6.     if (k > (n >> 1)) k = n-k;
  7.     unsigned long long res = n, j;
  8.     // We're not doing all we can to avoid overflow, as this is a proof of concept,
  9.     // not production code.
  10.     for(j = 2; j <= k; ++j) {
  11.         res *= (n+1-j);
  12.         res /= j;
  13.     }
  14.     return res;
  15. }
  16.  
  17. unsigned popcount(unsigned long long n) {
  18.     unsigned k = 0;
  19.     while(n) {
  20.         ++k;
  21.         n &= (n-1);
  22.     }
  23.     return k;
  24. }
  25.  
  26. unsigned long long rank(unsigned long long n) {
  27.     if (n == 0) return 1;
  28.     unsigned p = 0, k = popcount(n);
  29.     unsigned long long mask = 1,h = n >> 1;
  30.     while(h > 0) {
  31.         ++p;
  32.         h >>= 1;
  33.     }
  34.     mask <<= p;
  35.     unsigned long long r = binom(p,k);
  36.     r += rank(n-mask);
  37.     return r;
  38. }
  39.  
  40. int main()
  41. {
  42. 	unsigned long long n;
  43.  
  44. 	scanf( "%lld", &n );
  45.  
  46. 	printf( "%lld", rank( n ) );
  47.  
  48. 	return 0;
  49. }
Success #stdin #stdout 0.01s 1724KB
comments (?)
stdin
copy 
5
stdout
copy 
2
https://ideone.com/159HJ
language:
C (gcc 8.3)
created:
11 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!