fork download 
  1. #include <ctime>
  2. #include <iostream>
  3. #include <vector> // テーブルのために追加
  4.  
  5. // --- ルックアップテーブルの定義 ---
  6. uint16_t table_a[256]; // 8bit -> 16bit (a -> 0a0a...)
  7. uint16_t table_b[256]; // 8bit -> 16bit (b -> b0b0...)
  8. bool tables_initialized = false;
  9.  
  10. // テーブルを初期化する関数
  11. void init_tables() {
  12.     if (tables_initialized) return;
  13.     for (int i = 0; i < 256; i++) {
  14.         uint16_t a_val = 0;
  15.         uint16_t b_val = 0;
  16.         for (int j = 0; j < 8; j++) {
  17.             if (i & (1 << j)) {
  18.                 a_val |= (1 << (j * 2 + 0));
  19.                 b_val |= (1 << (j * 2 + 1));
  20.             }
  21.         }
  22.         table_a[i] = a_val;
  23.         table_b[i] = b_val;
  24.     }
  25.     tables_initialized = true;
  26. }
  27.  
  28. // テスト用のmix（この関数は遅いよ！これより早いの作ってね！）
  29. uint32_t mix_test(uint16_t a, uint16_t b) {
  30.     uint32_t o = 0;
  31.     for (int i = 0; i < 16; i++) {
  32.         if (a & (1 << i)) o |= 1 << (i * 2 + 0);
  33.         if (b & (1 << i)) o |= 1 << (i * 2 + 1);
  34.     }
  35.     return o;
  36. }
  37.  
  38. // mixはaとbのbitを交互に詰めて返す。aが下位に来る。
  39. // (例)
  40. // a : 1111111111111111
  41. // b : 0000000000000000
  42. // o : 01010101010101010101010101010101
  43. uint32_t mix(uint16_t a, uint16_t b) {
  44. // 16bitの入力を8bitずつに分解し、テーブルを4回引く
  45.  
  46.     // 下位8ビット (a: 0-7, b: 0-7)
  47.     uint32_t low_part = table_a[a & 0xFF] | table_b[b & 0xFF];
  48.  
  49.     // 上位8ビット (a: 8-15, b: 8-15)
  50.     uint32_t high_part = table_a[a >> 8] | table_b[b >> 8];
  51.  
  52.     return (high_part << 16) | low_part;
  53. }
  54.  
  55. // テスト
  56. void test(uint32_t(*func)(uint16_t, uint16_t)) {
  57.     std::cout << "test...";
  58.     for (int i = 0; i < 100; i++) {
  59.         uint16_t a = rand(), b = rand();
  60.         if (func(a, b) != mix_test(a, b)) {
  61.             std::cout << "failed" << std::endl;
  62.             exit(EXIT_FAILURE);
  63.         }
  64.     }
  65.     std::cout << "passed!" << std::endl;
  66. }
  67.  
  68. // ベンチマーク
  69. void benchmark(uint32_t (*func)(uint16_t, uint16_t)) {
  70.     std::cout << "benchmark...";
  71.     uint32_t dammy = 0;
  72.     double start = clock();
  73.     for (int i = 0; i < 50000000; i++) dammy ^= func(rand(), rand());
  74.     double end = clock();
  75.     std::cout << "end! elapsed:" << (end - start) / CLOCKS_PER_SEC << "s " << dammy << std::endl;
  76. }
  77.  
  78. int main() {
  79. 	init_tables();
  80.     test(mix);
  81.     benchmark(mix);
  82.     return 0;
  83. }
Success #stdin #stdout 1.69s 5288KB
comments (?)
stdin 
Standard input is empty
stdout 
test...passed!
benchmark...end! elapsed:1.67762s 4192649710
https://ideone.com/CvRrSa
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!