作者cole945 (躂躂..)
看板C_and_CPP
标题Re: [问题] 九九乘法表不用回圈是叫我直接从1列到81?
时间Sun Jul 22 19:15:53 2018
用 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://webptt.com/cn.aspx?n=bbs/C_and_CPP/M.1532258157.A.966.html
1F：→ Killercat: 连int2type都出来了..... XD 07/22 21:47
2F：→ Killercat: modern c++ design也好几年没翻了（远目 07/22 21:47
3F：推 nowar100: 推 cole945 07/22 22:30
4F：→ nowar100: 下面给 LPH 接力 07/22 22:37
5F：→ cole945: 原本想把结果cache在class member才写的这麽恶搞.. 07/23 00:16
6F：→ cole945: 用class template就不会写这麽绕了XD cache拿掉忘了改 07/23 00:16