num/nim_prod.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include <utility> | ||
| 4 | #include <cstdint> | ||
| 5 | |||
| 6 | namespace wala { | ||
| 7 | |||
| 8 | // Usage: | ||
| 9 | // constexpr nim_prod_t nimProd; | ||
| 10 | // C++20: | ||
| 11 | // constinit nim_prod_t nimProd; | ||
| 12 | struct nim_prod_t { | ||
| 13 | uint64_t bit_prod[64][64]{}; | ||
| 14 | ✗ | constexpr nim_prod_t() { | |
| 15 | ✗ | for (int i = 0; i < 64; i++) { | |
| 16 | ✗ | for (int j = 0; j < 64; j++) { | |
| 17 | ✗ | if ((i & j) == 0) { | |
| 18 | ✗ | bit_prod[i][j] = uint64_t(1) << (i|j); | |
| 19 | } else { | ||
| 20 | ✗ | int a = (i&j) & -(i&j); | |
| 21 | ✗ | bit_prod[i][j] = bit_prod[i ^ a][j] ^ bit_prod[(i ^ a) | (a-1)][(j ^ a) | (i & (a-1))]; | |
| 22 | } | ||
| 23 | } | ||
| 24 | } | ||
| 25 | } | ||
| 26 | 4404107 | constexpr uint64_t operator () (uint64_t x, uint64_t y) const { | |
| 27 | 4404107 | uint64_t res = 0; | |
| 28 |
4/4✓ Branch 11 → 12 taken 220856216 times.
✓ Branch 11 → 13 taken 2200394 times.
✓ Branch 12 → 3 taken 218652503 times.
✓ Branch 12 → 13 taken 2203713 times.
|
223056610 | for (int i = 0; i < 64 && (x >> i); i++) |
| 29 |
2/2✓ Branch 3 → 4 taken 140811548 times.
✓ Branch 3 → 10 taken 77840955 times.
|
218652503 | if ((x >> i) & 1) |
| 30 | ✗ | for (int j = 0; j < 64 && (y >> j); j++) | |
| 31 | ✗ | if ((y >> j) & 1) | |
| 32 | ✗ | res ^= bit_prod[i][j]; | |
| 33 | 4404107 | return res; | |
| 34 | } | ||
| 35 | }; | ||
| 36 | |||
| 37 | } // namespace wala | ||
| 38 |