fork(1) download
copy 
  1. #include <stdio.h>
  2. #include <math.h>
  3.  
  4. //gamma function using Lanczos approximation formula
  5. //output result in log base e
  6. //use exp() to convert back
  7. //has a nice side effect: can store large values in small [power of e] form
  8. double logGamma(double x)
  9. {
  10.     double tmp = (x-0.5) * log(x+4.5) - (x+4.5);
  11. 	double ser = 1.0 + 76.18009173     / (x+0) - 86.50532033    / (x+1)
  12. 	                 + 24.01409822     / (x+2) -  1.231739516   / (x+3)
  13. 	                 +  0.00120858003  / (x+4) -  0.00000536382 / (x+5);
  14. 	return tmp + log(ser * sqrt(2*M_PI) );	
  15. }
  16.  
  17. //result from logGamma() are actually (n-1)!
  18. double combination(int n, int r)
  19. {
  20. 	return exp(logGamma(n+1)-( logGamma(r+1) + logGamma(n-r+1) ));
  21. }
  22.  
  23. //primitive hamming weight counter
  24. int hWeight(int x)
  25. {
  26. 	int count, y;
  27. 	for (count=0, y=x; y; count++)
  28. 		y &= y-1; 
  29. 	return count;
  30. }
  31.  
  32. //-------------------------------------------------------------------------------------
  33. //recursively find the previous group's "hamming weight member count" and sum them
  34. int rCummGroupCount(int bitsize, int hw)
  35. {
  36. 	if (hw <= 0 || hw == bitsize) 
  37. 		return 1;
  38. 	else
  39. 		return round(combination(bitsize, hw)) + rCummGroupCount(bitsize,hw-1);
  40. }
  41. //-------------------------------------------------------------------------------------
  42.  
  43. int main(int argc, char* argv[])
  44. {
  45. 	int bitsize = 4, integer = 14;
  46. 	int hw = hWeight(integer);
  47. 	int groupStartIndex = rCummGroupCount(bitsize,hw-1);
  48. 	printf("bitsize: %d\n", bitsize);
  49. 	printf("integer: %d  hamming weight: %d\n", integer, hw);
  50. 	printf("group start index: %d\n", groupStartIndex);
  51. }
  52.  
Runtime error #stdin #stdout 0.02s 1720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
bitsize: 4
integer: 14  hamming weight: 3
group start index: 11
https://ideone.com/dNT3o4
language:
C (gcc 8.3)
created:
11 years ago
visibility:
public

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!