fork download
copy 
  1. #include <unordered_set>
  2. #include <iostream>
  3.  
  4. #define MAX_LEN 18
  5.  
  6. unsigned long long prime_hash(const unsigned int *arr, size_t len)
  7. {
  8.     /* first 2 * MAX_LEN primes */
  9. 	static const unsigned long long p[2 * MAX_LEN] = { 
  10. 		  2,   3,   5,   7,  11,  13,  17,  19,  23,
  11. 		 29,  31,  37,  41,  43,  47,  53,  59,  61,
  12. 		 67,  71,  73,  79,  83,  89,  97, 101, 103,
  13. 		107, 109, 113, 127, 131, 137, 139, 149, 151
  14. 	};
  15.  
  16. 	unsigned long long h = 1;
  17. 	for (size_t i = 0; i < len; i++)
  18. 		h *= p[2 * i] * (arr[i] ? p[2 * i + 1] : 1);
  19.  
  20. 	return h;
  21. }
  22.  
  23. unsigned long long ternary_hash(const unsigned int *arr, size_t len)
  24. {
  25. 	static const unsigned long long p3[MAX_LEN] = {
  26. 		       1,            3,            9,           27,
  27. 		      81,          243,          729,         2187,         
  28. 		    6561,        19683,        59049,       177147,
  29. 		  531441,      1594323,      4782969,     14348907,
  30. 		43046721,    129140163
  31. 	};
  32.  
  33. 	unsigned long long h = 0;
  34. 	for (size_t i = 0; i < len; i++)
  35. 		if (arr[i])
  36. 			h += p3[i];
  37.  
  38. 	for (size_t i = len; i < MAX_LEN; i++)
  39. 		h += 2 * p3[i];
  40.  
  41. 	return h;
  42. }
  43.  
  44. void int2barr(unsigned int *dst, unsigned long long n, size_t len)
  45. {
  46. 	for (size_t i = 0; i < len; i++) {
  47. 		dst[i] = n & 1;
  48. 		n >>= 1;
  49. 	}
  50. }
  51.  
  52. int main()
  53. {
  54. 	std::unordered_set<unsigned long long> phashes, thashes;
  55.  
  56.  
  57. 	/* generate all possible bool-arrays from length 0 to length 18 */
  58.  
  59. 	/* first, we checksum the only 0-element array */
  60. 	phashes.insert(prime_hash(NULL, 0));
  61. 	thashes.insert(ternary_hash(NULL, 0));
  62.  
  63. 	/* then we checksum the arrays of length 1...18 */
  64. 	for (size_t len = 1; len <= MAX_LEN; len++) {
  65. 		unsigned int bits[len];
  66. 		for (unsigned long long i = 0; i < (1 << len); i++) {
  67. 			int2barr(bits, i, len);
  68.  
  69. 			phashes.insert(prime_hash(bits, len));
  70. 			thashes.insert(ternary_hash(bits, len));
  71. 		}
  72. 	}
  73.  
  74. 	std::cout << "prime hashes: " << phashes.size() << std::endl;
  75. 	std::cout << "ternary hashes: " << thashes.size() << std::endl;
  76.  
  77. 	return 0;
  78. }
  79.  
Success #stdin #stdout 0.66s 19240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
prime hashes: 524287
ternary hashes: 524287
https://ideone.com/KXUYEc
language:
C++14 (gcc 8.3)
created:
10 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!