fork download 
  1. #include <ctime>
  2. #include <iostream>
  3. #include <cstdint>
  4. #ifdef __BMI2__
  5.   #include <immintrin.h>
  6. #endif
  7.  
  8. // テスト用のmix（この関数は遅いよ！これより早いの作ってね！）
  9. uint32_t mix_test(uint16_t a, uint16_t b) {
  10.     uint32_t o = 0;
  11.     for (int i = 0; i < 16; i++) {
  12.         if (a & (1 << i)) o |= 1 << (i * 2 + 0);
  13.         if (b & (1 << i)) o |= 1 << (i * 2 + 1);
  14.     }
  15.     return o;
  16. }
  17.  
  18. // 16bit を 0b0101…（偶数ビット）に展開
  19. static inline uint32_t part1by1(uint32_t x) {
  20.     x &= 0x0000FFFFu;
  21.     x = (x | (x << 8)) & 0x00FF00FFu;
  22.     x = (x | (x << 4)) & 0x0F0F0F0Fu;
  23.     x = (x | (x << 2)) & 0x33333333u;
  24.     x = (x | (x << 1)) & 0x55555555u;
  25.     return x;
  26. }
  27.  
  28. // mixはaとbのbitを交互に詰めて返す。aが下位(偶数)ビット側。
  29. uint32_t mix(uint16_t a, uint16_t b) {
  30. #ifdef __BMI2__
  31.     // BMI2 があるならビットデポジットで最速（-mbmi2 などで有効化）
  32.     uint32_t ae = _pdep_u32(a, 0x55555555u); // 偶数ビットに a を配置
  33.     uint32_t bo = _pdep_u32(b, 0xAAAAAAAAu); // 奇数ビットに b を配置
  34.     return ae | bo;
  35. #else
  36.     // ポータブルな定数マスク法
  37.     return part1by1(a) | (part1by1(b) << 1);
  38. #endif
  39. }
  40.  
  41. // テスト
  42. void test(uint32_t(*func)(uint16_t, uint16_t)) {
  43.     std::cout << "test...";
  44.     for (int i = 0; i < 100; i++) {
  45.         uint16_t a = rand(), b = rand();
  46.         if (func(a, b) != mix_test(a, b)) {
  47.             std::cout << "failed" << std::endl;
  48.             exit(EXIT_FAILURE);
  49.         }
  50.     }
  51.     std::cout << "passed!" << std::endl;
  52. }
  53.  
  54. // ベンチマーク
  55. void benchmark(uint32_t (*func)(uint16_t, uint16_t)) {
  56.     std::cout << "benchmark...";
  57.     uint32_t dammy = 0;
  58.     double start = clock();
  59.     for (int i = 0; i < 50000000; i++) dammy ^= func(rand(), rand());
  60.     double end = clock();
  61.     std::cout << "end! elapsed:" << (end - start) / CLOCKS_PER_SEC << "s " << dammy << std::endl;
  62. }
  63.  
  64. int main() {
  65.     test(mix);
  66.     benchmark(mix);
  67.     return 0;
  68. }
Success #stdin #stdout 1.82s 5280KB
comments (?)
stdin 
Standard input is empty
stdout 
test...passed!
benchmark...end! elapsed:1.8069s 4192649710
https://ideone.com/dAgRTL
language:
C++14 (gcc 8.3)
created:
20 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!