fork download 
  1. #include <ctime>
  2. #include <iostream>
  3.  
  4. // テスト用のmix（この関数は遅いよ！これより早いの作ってね！）
  5. uint32_t mix_test(uint16_t a, uint16_t b) {
  6.     uint32_t o = 0;
  7.     for (int i = 0; i < 16; i++) {
  8.         if (a & (1 << i)) o |= 1 << (i * 2 + 0);
  9.         if (b & (1 << i)) o |= 1 << (i * 2 + 1);
  10.     }
  11.     return o;
  12. }
  13.  
  14. // mixはaとbのbitを交互に詰めて返す。aが下位に来る。
  15. // (例)
  16. // a : 1111111111111111
  17. // b : 0000000000000000
  18. // o : 01010101010101010101010101010101
  19. uint32_t mix(uint16_t a, uint16_t b) {
  20.     // ここに実装
  21. 	// uint32_t c = a;
  22. 	// uint32_t d = b;
  23. 	// c = (c | (c << 8)) & 0x00ff00ff;
  24. 	// c = (c | (c << 4)) & 0x0f0f0f0f;
  25. 	// c = (c | (c << 2)) & 0x33333333;
  26. 	// c = (c | (c << 1)) & 0x55555555;
  27. 	// d = (d | (d << 8)) & 0x00ff00ff;
  28. 	// d = (d | (d << 4)) & 0x0f0f0f0f;
  29. 	// d = (d | (d << 2)) & 0x33333333;
  30. 	// d = (d | (d << 1)) & 0x55555555;
  31. 	// return c | d << 1;
  32. 	uint64_t c = ((uint64_t)b << 32) | a;
  33. 	c = (c | (c << 8)) & 0x00ff00ff00ff00ffULL;
  34. 	c = (c | (c << 4)) & 0x0f0f0f0f0f0f0f0fULL;
  35. 	c = (c | (c << 2)) & 0x3333333333333333ULL;
  36. 	c = (c | (c << 1)) & 0x5555555555555555ULL;
  37.     return uint32_t(c >> 31) | uint32_t(c & 0xffffffff);
  38. }
  39.  
  40. // テスト
  41. void test(uint32_t(*func)(uint16_t, uint16_t)) {
  42.     std::cout << "test...";
  43.     for (int i = 0; i < 100; i++) {
  44.         uint16_t a = rand(), b = rand();
  45.         if (func(a, b) != mix_test(a, b)) {
  46.             std::cout << "failed" << std::endl;
  47.             exit(EXIT_FAILURE);
  48.         }
  49.     }
  50.     std::cout << "passed!" << std::endl;
  51. }
  52.  
  53. // ベンチマーク
  54. void benchmark(uint32_t (*func)(uint16_t, uint16_t)) {
  55.     std::cout << "benchmark...";
  56.     uint32_t dammy = 0;
  57.     double start = clock();
  58.     for (int i = 0; i < 50000000; i++) dammy ^= func(rand(), rand());
  59.     double end = clock();
  60.     std::cout << "end! elapsed:" << (end - start) / CLOCKS_PER_SEC << "s " << dammy << std::endl;
  61. }
  62.  
  63. int main() {
  64.     test(mix);
  65.     benchmark(mix);
  66.     return 0;
  67. }
Success #stdin #stdout 1.13s 5308KB
comments (?)
stdin 
Standard input is empty
stdout 
test...passed!
benchmark...end! elapsed:1.12011s 4192649710
https://ideone.com/HtoK2w
language:
C++14 (gcc 8.3)
created:
2 days 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!