Re: [問題] 九九乘法表不用迴圈是叫我直接從1列到81?

看板C_and_CPP (C/C++)作者cole945 (躂躂..)時間6年前 (2018/07/22 19:15)推噓1(1推 0噓 5→)

留言6則, 3人參與討論串16/29 (看更多)

用 template specialization 做 recursion 直接全展開, 連 runtime branch 都不會用到乘法計算也是 compile time 用 template recursion, 不會有重覆計算的問題若要用 runtime cache, 可以搭 local static variable 來做 cache 因為是 compiler 計算, 所以不論計算方法, 沒有 performance 的問題, 不過這裡還是用 binary shift-add 來計算, 只需要做乘數的 ones-bit 次數的shift-add 再利用 pop-count 取 ones 較少的值當乘數可減少 shift-add 的次數, 例如 8 * 7 = (8) + (8 << 1) + (8 << 2) 7 * 8 = (7 << 3) 整個99乘法表只要做 26 次 ADD (吧?) 有開 optimization, 應該編完是直接展開成 printf call leaq .LC1(%rip), %rsi movl $24, %r8d movl $6, %ecx movl $4, %edx movl $1, %edi xorl %eax, %eax call __printf_chk@PLT // printf ("%d x %d = %2d; ", 4, 6, 24); leaq .LC1(%rip), %rsi movl $28, %r8d movl $7, %ecx movl $4, %edx movl $1, %edi xorl %eax, %eax call __printf_chk@PLT // printf ("%d x %d = %2d; ", 4, 7, 28); --- https://paste.ubuntu.com/p/xXXfG9mrpR/ --- #include <algorithm> #include <cstdio> using namespace std; // wrapping an interger to a type for specialization template<int Y> struct int2type { int x; public: constexpr int2type(const int &_x = Y) { x = _x; } }; template<int X, int Y> constexpr int bitmax() { return (__builtin_popcount(X) >= __builtin_popcount(Y) ? X : Y); } template<int X, int Y> constexpr int bitmin() { return (__builtin_popcount(X) < __builtin_popcount(Y) ? X : Y); } class foo { // multiplication by bit shifting template<int Y> constexpr int __mul(int2type<Y> _x) { // should only be called 26 times. constexpr int z = __builtin_ffs(Y >> 1); return _x.x + __mul(int2type<(Y >> z)>(_x.x << z)); } constexpr int __mul(int2type<1> _x) { return _x.x; } template<int X, int Y> const int mul() { // compile time cache constexpr int z = __builtin_ffs(Y) - 1; return __mul(int2type<(Y >> z)>(X << z)); } public: foo () {} // print 99 tables recurrsively template<int X, int Y> void print(int2type<X> = int2type<X>(), int2type<Y> = int2type<Y>()) { print(int2type<X>(), int2type<Y - 1>()); printf ("%d x %d = %2d; ", X, Y, mul<bitmax<X, Y>(), bitmin<X, Y>()>()); } // print next table template<int X> void print(int2type<X> _x, int2type<0>) { print(int2type<X - 1>(), int2type<9>()); puts(""); } // recurrsion termination template<int Y> void print(int2type<0>, int2type<Y>) { } }; int main () { foo f; f.print<9, 9>(); } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.119.18 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1532258157.A.966.html