如何优雅地利用c++编程从1乘到20？第1页

xiaobaibai520 网友的相关建议:

数学家版本：

       #include <iostream> #include <cmath> int main() {     std::cout << std::tgamma(20 + 1) << std::endl; }

语言学家版本：

       #include <iostream> #include <utility>  template<std::size_t...I> constexpr auto foo(std::index_sequence<I...>) { return ((I+1) * ...); }  int main()  {     std::cout << foo(std::make_index_sequence<20>()) << std::endl; }

“快速”版本：

       #include <iostream> #include <future>  long long foo(int a, int b, std::future<long long> last = std::async(std::integral_constant<long long, 1>())) {     return a == b ? a * last.get() : foo((a + b) / 2 + 1, b, std::async(foo, a, (a + b) / 2, std::move(last))); }  int main() {     std::cout << foo(1, 20) << std::endl; }

历史学家版本：

       #include <stdio.h> void main(void) {     int i;     long long j;     for(i = 1, j = 1;i <= 20; j *= i++);         printf("%lld", j); }

敏捷开发上线1.0版本：

       #include <stdio.h> int main() {     //printf("%d", 1*2*3*4*5*6*7*8*9*10);     printf("%lld", (long long)1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20); }

面向对象专家版本：

       #include <iostream> #include <string> #include <memory>  struct IBaseInterface {     virtual ~IBaseInterface() = 0; }; inline IBaseInterface::~IBaseInterface() = default;  struct IDataProvider : virtual public IBaseInterface {     virtual int first() = 0;     virtual int last() = 0;     virtual int next(int v) = 0; };  struct ICalculator : virtual public IBaseInterface {     virtual long long calc(IDataProvider *) = 0; };  struct IPrinter : virtual public IBaseInterface {     virtual void print(const std::string &) = 0; };  struct ISerializer : virtual public IBaseInterface {     virtual std::string serialize(long long value) = 0; };  struct IRunnable : virtual public IBaseInterface {     virtual void run() = 0; };  class Foo : virtual public IRunnable {     std::shared_ptr<IDataProvider> m_dp;     std::shared_ptr<ICalculator> m_c;     std::shared_ptr<ISerializer> m_s;     std::shared_ptr<IPrinter> m_p; public:     Foo(std::shared_ptr<IDataProvider> dp, std::shared_ptr<ICalculator> c, std::shared_ptr<ISerializer> s, std::shared_ptr<IPrinter> p) : m_dp(std::move(dp)), m_c(std::move(c)), m_s(std::move(s)),m_p(std::move(p)) {}     void run() override { return  m_p->print(m_s->serialize(m_c->calc(m_dp.get()))); } };  class DefaultSerializer : virtual public ISerializer { public:     std::string serialize(long long value) override { return std::to_string(value); } };  class StreamPrinter : virtual public IPrinter {     std::ostream &m_os; public:     explicit StreamPrinter (std::ostream &os) : m_os(os) {}     void print(const std::string &s)  override { m_os << s << std::endl; } };  class MultiplyAccumulateCalculator : virtual public ICalculator { public:     long long calc(IDataProvider *dp) override {         int i = dp->first();         long long j = i;         do             j *= (i = dp->next(i));         while(i != dp->last());         return j;     } };  int main() {     struct MyDataProvider : virtual public IDataProvider {         int first() override { return 1; }         int last() override { return 20; }         int next(int v) override { return v+1; }     };     Foo foo(std::make_shared<MyDataProvider>(), std::make_shared<MultiplyAccumulateCalculator>(), std::make_shared<DefaultSerializer>(), std::make_shared<StreamPrinter>(std::cout));     foo.run(); }

提前优化的并行版本：

       #include <iostream> #include <xmmintrin.h>  double foo(int x) {     __m128 a = {1.0f, 2.0f, 3.0f, 4.0f};     __m128 b = {4.0f, 4.0f, 4.0f, 4.0f};     __m128 c = {1.0f, 1.0f, 1.0f, 1.0f};     for(int i = 0; i < x / 4; ++i, a = _mm_add_ps(a, b))         c = _mm_mul_ps(c, a);     for(int i = x % 4; i < 4; ++i)         a[i] = 1.0f;     c = _mm_mul_ps(c, a);     return (double)c[0] * (double)c[1] * (double)c[2] * (double)c[3]; }  int main() {     std::cout << foo(20) << std::endl; }

“宏孩儿”元编程版：

       #include <boost/preprocessor.hpp>  // 由于boost.preprocessor仅提供255以下的整数运算 // 所以使用sequence来 (十位个位)(千位百位)(十万位万位) 的方式来表示大整数。  // 不进位加法：(77)(66)(55) + (44)(33)(22) = (121)(99)(77) #define PP_ADD_N_N_CARRY_OP(R, DATA, I, ELEM) (BOOST_PP_ADD(BOOST_PP_SEQ_ELEM(I, DATA), ELEM)) #define PP_ADD_N_N_CARRY(SEQ_A, SEQ_B) BOOST_PP_SEQ_FOR_EACH_I(PP_ADD_N_N_CARRY_OP, SEQ_A, SEQ_B)  // 进位加法：(121)(99)(77) = （21)(0)(78) // 注意SEQ_A的长度要比SEQ_B长 #define PP_ADD_N_N_OP(S, STATE, ELEM_CARRY)      BOOST_PP_SEQ_PUSH_FRONT(              BOOST_PP_SEQ_REPLACE(STATE, 0, BOOST_PP_MOD(BOOST_PP_ADD(BOOST_PP_SEQ_HEAD(STATE), ELEM_CARRY), 100)),              BOOST_PP_DIV(BOOST_PP_ADD(BOOST_PP_SEQ_HEAD(STATE), ELEM_CARRY), 100)              ) #define PP_ADD_N_N(SEQ_A, SEQ_B) BOOST_PP_SEQ_REVERSE(BOOST_PP_SEQ_FOLD_LEFT(PP_ADD_N_N_OP, BOOST_PP_SEQ_NIL(0), PP_ADD_N_N_CARRY(SEQ_A, SEQ_B)))  // 没什么好说的，X*N = X+X+X+X+X+...+X #define PP_MUL_N_1_EXP_OP(Z, I, DATA) (DATA) #define PP_MUL_N_1_EXP(SEQ_N, N) BOOST_PP_REPEAT(N, PP_MUL_N_1_EXP_OP, SEQ_N) #define PP_MUL_N_1_MYOP(S, STATE, ITEM) PP_ADD_N_N(STATE, ITEM) #define PP_MUL_N_1_FWD(EXP) BOOST_PP_SEQ_FOLD_LEFT(PP_MUL_N_1_MYOP, BOOST_PP_SEQ_HEAD(EXP), BOOST_PP_SEQ_TAIL(EXP)) #define PP_MUL_N_1(SEQ_N, N) PP_MUL_N_1_FWD(PP_MUL_N_1_EXP(SEQ_N, N))  #define FACT5 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1((1), 2), 3), 4), 5) #define FACT10 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT5, 6), 7), 8), 9), 10) #define FACT15 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT10, 11), 12), 13), 14), 15) #define FACT20 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT15, 16), 17), 18), 19), 20) #define FACT25 PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(PP_MUL_N_1(FACT20, 21), 22), 23), 24), 25)  static_assert(false, BOOST_PP_STRINGIZE(FACT10));

警告：目前只有Clang能算出FACT20，编译缓慢是十分正常的，请耐心等待。默认计算10的阶乘10!=3628800，期待输出：

       error: static_assert failed "(0) (88) (62) (3) (0) (0) (0) (0) (0) (0)"

真·模板元编程版本（大整数）

       #include <iostream> #include <iomanip> #include <type_traits>  using BaseType_t = long long; constexpr BaseType_t lgBase = 9; // 注意10000*10000刚刚好小于int的取值范围 constexpr BaseType_t Base = 1000000000; // 注意10000*10000刚刚好小于int的取值范围  // 大整数的表示 template<BaseType_t...I> struct BigInteger {     using type = BigInteger; };  // 连接 template<class T1, class T2> struct BI_Cat; template<BaseType_t...I1, BaseType_t...I2> struct BI_Cat <BigInteger<I1...>, BigInteger<I2...>> : BigInteger<I1..., I2...> {};  // 左移一个单元（即*Base） template<class T> struct BI_SHL; template<BaseType_t...I> struct BI_SHL<BigInteger<I...>> : BigInteger<I..., 0> {};  // 去除开头的0 template<class T> struct BI_Remove_Zeros : T {}; template<BaseType_t...I> struct BI_Remove_Zeros<BigInteger<0, I...>> : BI_Remove_Zeros<BigInteger<I...>> {};  // 填充0到N个单元 template<int X, class IS> struct BI_Fill_Impl; template<int X, class T, T...I> struct BI_Fill_Impl<X, std::integer_sequence<T, I...>> : BigInteger<(I, X)...> {}; template<int Size> struct BI_Fill_Zeros : BI_Fill_Impl<0, std::make_index_sequence<Size>> {};  template<class T, int N> struct BI_Resize; template<BaseType_t...I, int N> struct BI_Resize<BigInteger<I...>, N> : BI_Cat<typename BI_Fill_Zeros<N - sizeof...(I)>::type, BigInteger<I...>> {};  // 返回较大的数值 template<int A, int B> struct int_min : std::integral_constant<int, (A<B?B:A)> {};  // 非进位加法：先把两个数的位数改成一样的然后依次相加 template<class A, class B, class ShouldResize> struct BI_AddNotCarry_Impl; template<BaseType_t...I1, BaseType_t...I2> struct BI_AddNotCarry_Impl <BigInteger<I1...>, BigInteger<I2...>, std::true_type> : BigInteger<(I1 + I2)...> {};  template<BaseType_t...I1, BaseType_t...I2> struct BI_AddNotCarry_Impl <BigInteger<I1...>, BigInteger<I2...>, std::false_type>      : BI_AddNotCarry_Impl<          typename BI_Resize<BigInteger<I1...>, int_min<sizeof...(I1), sizeof...(I2)>::value>::type,          typename BI_Resize<BigInteger<I2...>, int_min<sizeof...(I1), sizeof...(I2)>::value>::type,          std::true_type      >{};  template<class A, class B> struct BI_AddNotCarry; template<BaseType_t...I1, BaseType_t...I2> struct BI_AddNotCarry <BigInteger<I1...>, BigInteger<I2...>>     : BI_AddNotCarry_Impl<BigInteger<I1...>, BigInteger<I2...>, std::bool_constant<sizeof...(I1) == sizeof...(I2)>> {};  // 判断是否为0 template<class Y> struct BI_IsZero; template<BaseType_t...I> struct BI_IsZero<BigInteger<I...>> : std::bool_constant<((I == 0) && ...)> {};  // 自动进位 template<class A> struct BI_Carry; template<class A, class B> struct BI_Add : BI_Carry<typename BI_AddNotCarry<A, B>::type> {};  template<class Mod, class Div, class ShouldCalc = typename BI_IsZero<Div>::type> struct BI_Carry_Impl; template<class Mod, class Div> struct BI_Carry_Impl<Mod, Div, std::true_type> : Mod {}; template<class Mod, class Div> struct BI_Carry_Impl<Mod, Div, std::false_type>         : BI_Add<Mod, typename BI_SHL<Div>::type > {}; template<BaseType_t...I> struct BI_Carry<BigInteger<I...>>         : BI_Remove_Zeros<typename BI_Carry_Impl<BigInteger<(I % Base)...>, BigInteger<(I / Base)...>>::type> {};  // 乘以X并自动进位 template<class A, int X> struct BI_MulX; template<BaseType_t...I1, int X> struct BI_MulX <BigInteger<I1...>, X>         : BI_Carry<BigInteger<(I1 * X)...>> {};  // 计算阶乘 template<int X> struct BI_Fact : BI_MulX<typename BI_Fact<X-1>::type, X> {}; template<> struct BI_Fact<0> : BigInteger<1> {};  template<BaseType_t...I> std::ostream &operator<<(std::ostream &out, BigInteger<I...>) {     return ((out << std::setfill('0') << I << std::setw(lgBase)), ...); }  int main() {     std::cout << typename BI_Fact<20>::type() << std::endl; }

如果将BI_Fact<20>改为BI_Fact<1000>后，我们可爱的Clang解释器花了3秒多的时间很偷税地算出来了1000! =

402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

无人值守自动迭代版本

       #include <iostream> #include <numeric> #include <vector> #include <functional> int main() {  std::vector<int> v(std::atoi(std::end(__DATE__) - (__LINE__) / 2)); // 2020年，第六行  std::iota(v.begin(), v.end(), 1);  std::cout << std::accumulate(v.begin(), v.end(), 1ull, std::multiplies<>()) << std::endl; }

模板元编程版本（二进制）

       #include <iostream> #include <bitset> #include <type_traits> using Zero = std::integer_sequence<bool>; using One = std::integer_sequence<bool, true>; template<class T> struct type_identity : std::enable_if<true, T> {}; // *2 template<class T> struct shl; template<bool...B> struct shl<std::integer_sequence<bool, B...>> : type_identity<std::integer_sequence<bool, false, B...>> {}; // *2+1 template<class T> struct shl_inc; template<bool...B> struct shl_inc<std::integer_sequence<bool, B...>> : type_identity<std::integer_sequence<bool, true, B...>> {}; // /2 template<class T> struct shr; template<bool First, bool...Rest> struct shr<std::integer_sequence<bool, First, Rest...>> : type_identity<std::integer_sequence<bool, Rest...>> {}; // +1 template<class T> struct inc; template<> struct inc<Zero> : type_identity<One> {}; template<bool...B> struct inc<std::integer_sequence<bool, true, B...>> : shl<typename inc<std::integer_sequence<bool, B...>>::type> {}; template<bool...B> struct inc<std::integer_sequence<bool, false, B...>> : type_identity<std::integer_sequence<bool, true, B...>> {}; // -1 template<class T> struct dec; template<bool...B> struct dec<std::integer_sequence<bool, true, B...>> : type_identity<std::integer_sequence<bool, false, B...>> {}; template<bool...B> struct dec<std::integer_sequence<bool, false, B...>> : shl_inc<typename dec<std::integer_sequence<bool, B...>>::type> {}; // 取最低位 template<class T> struct lowest : std::false_type {}; template<bool First, bool...Rest> struct lowest<std::integer_sequence<bool, First, Rest...>> : std::bool_constant<First> {}; // 扩展位数 template<class T> struct ext; template<bool...B> struct ext<std::integer_sequence<bool, B...>> : type_identity<std::integer_sequence<bool, B..., false>> {}; // 比较两个数是否相等 template<class A, class B> struct test; template<bool...B1, bool...B2> struct test<std::integer_sequence<bool, B1...>, std::integer_sequence<bool, B2...>> : std::bool_constant<(... || (B1 || B2)) > {}; // 计算位数大小 template<class T> struct len; template<> struct len<Zero> : std::integral_constant<std::size_t, 0> {}; template<bool...B> struct len<std::integer_sequence<bool, B...>> : std::integral_constant<std::size_t, sizeof...(B)> {}; // 去除多余的高位 template<class T, bool not_empty = test<T, T>::value> struct shrink : type_identity<Zero> {}; template<bool...B> struct shrink<std::integer_sequence<bool, false, B...>, true> : shl<typename shrink<std::integer_sequence<bool, B...>>::type> {}; template<bool...B> struct shrink<std::integer_sequence<bool, true, B...>, true> : shl_inc<typename shrink<std::integer_sequence<bool, B...>>::type> {}; // 实现超前进位加法器 template<class A, class B, bool loop = test<B, B>::value> struct add_impl : type_identity<A> {}; template<bool...B1, bool...B2> struct add_impl<std::integer_sequence<bool, B1...>, std::integer_sequence<bool, B2...>, true>  : add_impl<std::integer_sequence<bool, (B1^ B2)..., false>, std::integer_sequence<bool, false, (B1& B2)...>> {}; // 加法时处理位数不同的情况 template<class A, class B, bool = (len<A>::value > len<B>::value)> struct add_fill2 : add_impl<A, B> {}; template<class A, class B> struct add_fill2<A, B, true> : add_fill2<A, typename ext<B>::type>{}; template<class A, class B, bool = (len<A>::value < len<B>::value)> struct add : add_fill2<A, B> {}; template<class A, class B> struct add<A, B, true> : add<typename ext<A>::type, B> {}; // 实现乘法器 template<class A, class B, bool add = lowest<B>::value> struct mul; template<class A> struct mul<A, Zero, false> : type_identity<Zero> {}; template<class A, class B> struct mul<A, B, false> : mul<typename shl<A>::type, typename shr<B>::type> {}; template<class A, class B> struct mul<A, B, true> : add<typename mul<typename shl<A>::type, typename shr<B>::type>::type, A> {}; // 计算阶乘 template<class T> struct greater_than_one : test<typename dec<T>::type, typename dec<T>::type> {}; template<class T> struct fact : shrink<typename mul<T, typename fact<typename shrink<typename dec<T>::type>::type>::type>::type> {}; template<> struct fact<One> : type_identity<One> {}; // 转换为bitset输出 template<bool...B, std::size_t...I> auto ToBitSet(std::integer_sequence<bool, B...> b, std::integer_sequence<std::size_t, I...>) {  std::bitset<sizeof...(B)> ret;  (..., ret.set(I, B));  return ret; } template<bool...B> auto ToBitSet(std::integer_sequence<bool, B...> b) {  return ToBitSet(b, std::make_index_sequence<sizeof...(B)>()); }  int main() {  using F20 = fact<std::integer_sequence<bool, false, false, true, false, true>>::type;  std::cout << ToBitSet(F20()).to_ullong() << std::endl;  //using F31 = fact<std::integer_sequence<bool, true, true, true, true, true>>::type;  //std::cout << ToBitSet(F31()).to_string() << std::endl; }

注：目前极限是计算到31的阶乘，使用MSVC编译31的阶乘需30G内存。

更新：

2020-1-12 将“历史学家”版本修改为void main(void)更具有历史气息

2020-1-16 将“快速”二分版本修改为「伪」递归调用

2020-1-18 并行版本

2020-2-22 宏元编程版本

2020-2-24 模板元编程版本（大整数）

2020-3-14 无人值守自动迭代版本

2021-10-12 模板元编程版本（二进制）

mai-wen-xue-67 网友的相关建议:

无所谓优雅。

       #include <stdio.h> int main() {          printf("%Lf 
", (long double)1.0*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20);     return 0; }

       2432902008176640000.000000  [wenxue@dad5600 _CPP_]$

在GNU C编译器中，long double 在x86处理器上是80位的扩展精度，而不考虑用于该类型的物理存储（可以是96位或128位），在其他一些架构上，long double 可以是 double

double（例如PowerPC）或128位四倍精度（例如SPARC[19]）。从gcc 4.3开始，四倍精度(quadruple precision )在x86上也被支持，但作为非标准类型 __float128 而不是long double。

虽然x86架构，特别是x86上的x87浮点指令，支持80位扩展精度的操作，但是可以配置处理器自动将操作四舍五入到 double 双精度（甚至是单精度）。相反，在扩展精度模式下，即使最终结果以较低的精度存储（即 FLT_EVAL_METHOD == 2），扩展精度也可用于中间编译器生成的计算。在Linux上的gcc，80位扩展精度是默认的；在几个BSD操作系统(FreeBSD和OpenBSD)上，double 双精度模式是默认的，long double 操作实际上被降低到双精度 (然而，NetBSD 7.0及以后的版本，默认为80位扩展精度)。

在单个程序中可以通过FLDCW "浮点加载控制字 "指令来覆盖这一点。在x86_64上，BSD默认为80位扩展精度。微软的 Windows 和 Visual C++ 也默认将处理器设置为 double 双精度模式，但是这也可以在单个程序中被覆盖（例如，通过Visual C++中的 _controlfp_s 函数）。另一方面，Intel C++ Compiler for x86默认启用扩展精度模式。在IA-32 OS X上，long double 数是80位扩展精度。

例二

       #include<iostream> // #include<math.h> using namespace std;  size_t factorial(size_t n);  int main() {     cout << "x! of " << 20 << " = " << factorial( (size_t)20 )  <<"
";     return 0; }  size_t factorial(size_t n) {     if(n > 1.0)         return n * factorial(n - 1);     else         return (size_t)1; }   x! of 20 = 2432902008176640000 [wenxue@dad5600 _CPP_]$

例三

       #include <iostream> using namespace std;  int main() {     size_t n;     size_t fact = 1;      cout << "Please enter a positive integer: 
";     cin >> n;      if (n < 0)         cout << "Crap! don't give me negative. 
";     else {         for(size_t i = 1; i <= n; ++i) {             fact *= i;         }         cout << "Factorial of " << n << " = " << fact <<" 
";         }      return 0; }   Please enter a positive integer:  20 Factorial of 20 = 2432902008176640000  [wenxue@dad5600 _CPP_]$

参考

       https://en.wikipedia.org/wiki/Long_double

godweiyang 网友的相关建议:

我来提供两个CUDA并行版本的。

方法1：

       #include <iostream>  typedef unsigned long long int ull; const int N = 20;  __device__ ull atomicMul(ull* address, ull val) {     ull *address_as_ull = (ull *)address;     ull old = *address_as_ull, assumed;     do {         assumed = old;         old = atomicCAS(address_as_ull, assumed, val * assumed);     } while (assumed != old);     return old; }  __global__ void mul(ull *x) {     ull i = threadIdx.x + 1;     atomicMul(x, i); }  int main() {     ull *x;     cudaMallocManaged(&x, sizeof(ull));     x[0] = 1;     mul<<<1, N>>>(x);     cudaDeviceSynchronize();     std::cout << x[0] << std::endl;     cudaFree(x);     return 0; }

利用原子乘操作，由于CUDA里没有原子乘这个操作（有原子加atomicAdd和原子减atomicSub），所以需要利用atomicCAS函数来手动实现一个原子乘atomicMul。

方法2：

       #include <iostream>  typedef unsigned long long int ull; const int N = 20; const int WARP_SIZE = 32;  __global__ void mul(ull *x) {     int i = threadIdx.x;     ull val = x[i];     for (int mask = WARP_SIZE / 2; mask > 0; mask >>= 1)         val *= __shfl_xor_sync(WARP_SIZE - 1, val, mask, WARP_SIZE);     x[i] = val; }  int main() {     ull *x;     cudaMallocManaged(&x, WARP_SIZE * sizeof(ull));     for (int i = 0; i < WARP_SIZE; ++i)         x[i] = i < N ? i + 1 : 1;     mul<<<1, WARP_SIZE>>>(x);     cudaDeviceSynchronize();     std::cout << x[0] << std::endl;     cudaFree(x);     return 0; }

利用warpReduce操作，在log时间内对warp内连续32个元素进行乘积。

感谢 @NekoDaemon 提供的方法2进一步优化版本，无需开辟数组存储元素，在计算时直接算出对应元素即可：

       #include <iostream>  typedef unsigned long long int ull; const int N = 20; const int WARP_SIZE = 32;  __global__ void mul(ull *x) {     int i = threadIdx.x;     ull val = i < N ? i + 1 : 1;     for (int mask = WARP_SIZE / 2; mask > 0; mask >>= 1)         val *= __shfl_xor_sync(WARP_SIZE - 1, val, mask, WARP_SIZE);     if (!i) x[i] = val; }  int main() {     ull *x;     cudaMallocManaged(&x, sizeof(ull));     mul<<<1, WARP_SIZE>>>(x);     cudaDeviceSynchronize();     std::cout << x[0] << std::endl;     cudaFree(x);     return 0; }

运行：

       nvcc run.cu -o run ./run

输出结果：

       2432902008176640000

pansz 网友的相关建议:

同意高票回答的结论。

但是，想讲日本人的起源，只看日本是不行的，本回答希望把视野放到广阔的东亚，把韩国人的起源，日本人与炎黄部落的关系等一并讲明。

历史隐藏在层层谜团中，谁都不能得出百分之百正确的结论，如有错误，欢迎指出。

结论先奉上

35％祖先为矮黑人

35％祖先为生活在中国东北的扶余部落（原本为炎帝部落的一支）

20％祖先为典型华夏汉人

以下是全文目录

（1）东亚的杀戮与征服

（2）伟大的东北大地

（3）日本的起源

（1）东亚的杀戮与征服

研究人种起源与变迁最准确的是Y染色体检测，有一个段子，表白时男生对女生说，我有一条祖传的染色体想送给你。这条染色体，就是男性独有的Y染色体。Y染色体只传男，突变少，易检测，而父系又代表着权利与支配，因此Y染色体检测祖先受到人们的认可。2001年，人类基因组计划基本完成，人类历史的大幕被揭开，人种的变迁呈现在人们眼前。

全部人类起源自非洲，10万年前，最古老的一支矮黑人，其基因标记为D，走出了非洲，最早在5万年前，就到达了亚洲，他们广泛分布在东南亚，过着采集与渔猎的悠闲生活。

纯种矮黑人长这样

但不久后，与其差不多同时期走出非洲的棕色人种C，也到达了亚洲，C立刻开始了对D的杀戮与征服，D或被同化，或被驱逐到亚洲的各个犄角旮旯，现在东亚D基因只集中存在于日本（35％），西藏（40％）。

C集团也并没能统治亚洲多久，3万年前，黄白种人的祖先走出非洲，一支向北，成为白种人，一支向东进入亚洲，他们就是华夏汉人的祖先—O集团。O集团具有良好的技术与文明，C与D根本不是其对手，O集团旗下的O1、O2，迅速占领了中原最肥沃的土地，开始农业耕作，人口爆炸增长，建立了灿烂的文化，而C集团则被驱赶到了北部，成为了蒙古，女真等族的祖先，值得一提的是，韩国也存在大量的C，这些C也构成了韩国本土文化的基础。

5000年前左右，生活在藏羌的另一个O集团—O3，大举东进，一举征服与同化了在中原进行农耕的兄弟集团O1,O2，占领中原，成为了现在汉族的主流。现今的河北，山东等都为O3的天下，O1则被赶到了中国南方，O2现在只集中存在于东北的满族和日本韩国等。这一时期中国已有了记载，皇帝炎帝战蚩尤、周武王伐纣等，是不是就在说的这一段历史呢？

至此，现代亚洲的雏形就已经显现，各个民族的构成也清晰起来，汉族的血缘最统一，70％以上的O基因，其中03占50％以上，可以说我们不仅是文化上的民族，还是地地道道血缘上的民族。日本人除了55％的O之外，还有35％的D，这也构成了大和民族的独特之处，韩国除了大量的O也有2成C，文化独树一帜也有相应的基础。蒙古有高达5成的C，并把其C基因传到了欧洲各地，足见蒙古帝国的伟大。值得一提的是，蒙古王氏基因C3（蒙古人20％），和日本本土基因D2（日本人35％），在汉族中完全没有出现，看来汉族对于侵略者的抵抗很彻底，而蒙古和日本，却各有20％的O3存在，汉民族强大的影响力可见一斑。

东亚各个民族的兴衰史，其实就是一部基因的兴衰史，基因战争远没有结束，以后的进程值得期待。

（2）伟大的东北大地

作为土生土长的吉林人，读书时，课本里全都是中原王朝的兴衰史，我对于东北大地的历史完全没有了解。

最近在翻阅了各种资料后，我不禁感到，原来这片土地这么牛○

东北大地上主要生存着三族人

东胡—蒙古的祖先

肃慎—女真，满族的祖先

夫余—创立高句丽，后被灭国，语言消失。其中，东胡，肃慎，结合我们之前的基因分析，都是被O集团赶到北部的C集团，游牧为生。而夫余不同，是O集团的一支，地地道道的农耕民族，其基因极有可能是现今已不存在与汉族O2b。

在这里援引李德山老师对于扶余历史的研究。

夫→番

余→徐

番国，与徐国，合并称夫余国，而番国与徐国都来自于共通的祖先——炎帝部落，该部落本来农耕于中原（一说于江南），战败后北上，于东北最终建立了自己的国家。势力遍及辽宁吉林朝鲜半岛，而起源与炎帝一说，又恰恰可以解释其O2基因与农耕文明的来源。朝鲜半岛三国鼎力时，百济与高句丽都为扶余后裔。而新罗则以韩国原住民C为主，文化与扶余不同。最终，新罗政权统一韩国，虽然他们后来建立了高丽王朝，但其本身与高丽没有任何关系，他们的新罗语言也成为了主流，也就是现今韩语的前身。扶余最终灭亡，但扶余的血统O2b,还大量留存在韩国（35％），中国满族（20％），日本（35％）。

（3）日本人的起源

讲到这里，大家也基本推测出日本人的起源了吧。

日本人的基因检测结果如下

35％D 矮黑人。

35％O2b ，汉民族基因O的兄弟，只大量存在日本，韩国，满族（满族是O2还是O2b目前还没有确切资料），上课追溯到炎帝部落。

20％O3 典型的汉民族基因。

其它还有一些棕色人种的C，不过和蒙古人的C也不相同

D与O3的来源已经不必说，但是O2b的来源是否是扶余还存在很多争论。

对此，语言上的分析为我们指明了方向。

语言种类上看，学者白桂思的研究指出，与日语最相近的语言就是古高句丽语，这是O2b旗下的扶余人的语言，也就是说，扶余人的语言在韩国被C集团的韩语取代，而在日本却被保存了下来，这正好解释了日语与韩语的不同之处，也佐证了基因研究的结果。

可以看到，他们的外貌有非常大的区别，某种程度上也代表着O系与D系基因的区别。

一直以来，日本都是绳文人的天下，弥生时代，来自朝鲜半岛的O2b与O3登陆日本九州，他们带着先进的农耕技术与文化，不断同化与驱逐着D集团，现在也能看到这种趋势，九州地区O较多，古代权力中心关西的O也比较多，北海道与冲绳则D比较多。

最后上一张平成天皇的照片，典型的弥生脸

天皇家是哪里来的？

大家猜猜看

是O3还是O2b呢？

参考：

图片百度百科

数据分子人类学论坛

复旦大学有很多相关研究，感兴趣的可以去围观

其他答案

日语有没有类似英语中词根的东西帮助记单词？ - 张铭的回答 - 知乎

如何优雅地利用c++编程从1乘到20？的其他答案点击这里

如何优雅地利用c++编程从1乘到20？第1页

方法1：

方法2：

相关话题

前一个讨论

下一个讨论

相关的话题

如何优雅地利用c++编程从1乘到20？ 第1页

方法1：

方法2：

相关话题

前一个讨论

下一个讨论

相关的话题

如何优雅地利用c++编程从1乘到20？第1页