如何驱动C＃，C ++或Java编译器来计算1 + 2 + 3 + … + 1000？
在最近的一次采访中，我被问到一个非常奇怪的问题。 面试官问我如何使用编译器function来计算1 + 2 + 3 + … + 1000。 这意味着我不允许编写程序并执行它，但是我应该编写一个程序，它可以在编译时驱动编译器计算总和，并在编译完成时输出结果。 作为一个暗示，他告诉我可以使用编译器的generics和预处理器特性。 可以使用C ++，C＃或Java编译器。 有任何想法吗？？？
这个问题是不相关的计算总和没有任何循环问这里 。 另外，应该注意的是，这个总和应该在编译时计算。 使用C ++编译器指令打印结果是不可接受的。
阅读更多关于已发布的答案，我发现使用C ++模板编译期间解决问题称为元编程 。 这是Erwin Unruh博士在标准化C ++语言的过程中偶然发现的一种技术。 您可以在元编程的wiki页面上阅读更多关于此主题的内容。 看来有可能使用Java注释在Java中编写程序。 你可以看看下面的女士的答案。
一本关于C ++元编程的好书就是这个 。 值得一看，如果感兴趣。
一个有用的C ++元编程库是Boost的MPL 这个链接 。
现在更新recursion深度！ 在MSVC10和GCC上工作时不会增加深度。 🙂
简单的编译时recursion+加法：
template<unsigned Cur, unsigned Goal> struct adder{ static unsigned const sub_goal = (Cur + Goal) / 2; static unsigned const tmp = adder<Cur, sub_goal>::value; static unsigned const value = tmp + adder<sub_goal+1, Goal>::value; }; template<unsigned Goal> struct adder<Goal, Goal>{ static unsigned const value = Goal; };
Testcode：
template<unsigned Start> struct sum_from{ template<unsigned Goal> struct to{ template<unsigned N> struct equals; typedef equals<adder<Start, Goal>::value> result; }; }; int main(){ sum_from<1>::to<1000>::result(); }
GCC的输出：
错误：声明'struct sum_from <1u> :: to <1000u> :: equals <500500u>'
在Ideone上的生动的例子 。
MSVC10的输出：
error C2514: 'sum_from<Start>::to<Goal>::equals<Result>' : class has no constructors with [ Start=1, Goal=1000, Result=500500 ]
C＃示例在编译时出错。
class Foo { const char Sum = (1000 + 1) * 1000 / 2; }
产生以下编译错误：
Constant value '500500' cannot be converted to a 'char'
我应该编写一个程序，可以在编译时驱动编译器计算总和，并在编译完成时输出结果。
在编译期间打印一个数字的一个常用技巧是尝试访问一个模板的不存在的成员，这个成员是用你想打印的数字实例化的：
template<int> struct print_n {}; print_n<1000 * 1001 / 2>::foobar go;
编译器然后说：
error: 'foobar' in 'struct print_n<500500>' does not name a type
有关这种技术的更有趣的例子，请参阅在编译时解决八皇后问题 。
由于在面试问题中都没有指定编译器和语言，所以我敢用GHC提交Haskell的解决scheme：
{-# LANGUAGE TemplateHaskell #-} {-# OPTIONS_GHC -ddump-splices #-} module Main where main :: IO () main = print $(let x = sum [1 :: Int .. 1000] in [| x |])
编译它：
$ ghc compsum.hs [1 of 1] Compiling Main ( compsum.hs, compsum.o ) Loading package ghc-prim ... linking ... done. <snip more "Loading package ..." messages> Loading package template-haskell ... linking ... done. compsum.hs:6:16-56: Splicing expression let x = sum [1 :: Int .. 1000] in [| x |] ======> 500500 Linking compsum ...
而且我们也有一个工作程序。
使用C ++ 11可以让编译时间计算增加constexpr函数，但是目前只能使用gcc 4.6或更高版本支持，所以生活会更容易。
constexpr unsigned sum(unsigned start, unsigned end) { return start == end ? start : sum(start, (start + end) / 2) + sum((start + end) / 2 + 1, end); } template <int> struct equals; equals<sum(1,1000)> x;
该标准只要求编译器支持512的recursion深度，所以它仍然需要避免线性recursion深度。 这是输出：
$ g++-mp-4.6 --std=c++0x test.cpp -c test.cpp:8:25: error: aggregate 'equals<500500> x' has incomplete type and cannot be defined
当然，你可以使用公式：
constexpr unsigned sum(unsigned start, unsigned end) { return (start + end) * (end - start + 1) / 2; } // static_assert is a C++11 assert, which checks // at compile time. static_assert(sum(0,1000) == 500500, "Sum failed for 0 to 1000");
在Java中，我想过使用注释处理。 在将源文件parsing到javac命令之前，apt工具会扫描源文件。
在编译源文件的过程中，输出将被打印出来：
@Documented @Retention(RetentionPolicy.RUNTIME) @Target({ElementType.TYPE, ElementType.METHOD}) public @interface MyInterface { int offset() default 0; int last() default 100; }
处理器工厂：
public class MyInterfaceAnnotationProcessorFactory implements AnnotationProcessorFactory { public Collection<String> supportedOptions() { System.err.println("Called supportedOptions............................."); return Collections.EMPTY_LIST; } public Collection<String> supportedAnnotationTypes() { System.err.println("Called supportedAnnotationTypes..........................."); return Collections.singletonList("practiceproject.MyInterface"); } public AnnotationProcessor getProcessorFor(Set<AnnotationTypeDeclaration> set, AnnotationProcessorEnvironment ape) { System.err.println("Called getProcessorFor................"); if (set.isEmpty()) { return AnnotationProcessors.NO_OP; } return new MyInterfaceAnnotationProcessor(ape); } }
实际的注释处理器：
public class MyInterfaceAnnotationProcessor implements AnnotationProcessor { private AnnotationProcessorEnvironment ape; private AnnotationTypeDeclaration atd; public MyInterfaceAnnotationProcessor(AnnotationProcessorEnvironment ape) { this.ape = ape; atd = (AnnotationTypeDeclaration) ape.getTypeDeclaration("practiceproject.MyInterface"); } public void process() { Collection<Declaration> decls = ape.getDeclarationsAnnotatedWith(atd); for (Declaration dec : decls) { processDeclaration(dec); } } private void processDeclaration(Declaration d) { Collection<AnnotationMirror> ams = d.getAnnotationMirrors(); for (AnnotationMirror am : ams) { if (am.getAnnotationType().getDeclaration().equals(atd)) { Map<AnnotationTypeElementDeclaration, AnnotationValue> values = am.getElementValues(); int offset = 0; int last = 100; for (Map.Entry<AnnotationTypeElementDeclaration, AnnotationValue> entry : values.entrySet()) { AnnotationTypeElementDeclaration ated = entry.getKey(); AnnotationValue v = entry.getValue(); String name = ated.getSimpleName(); if (name.equals("offset")) { offset = ((Integer) v.getValue()).intValue(); } else if (name.equals("last")) { last = ((Integer) v.getValue()).intValue(); } } //find the sum System.err.println("Sum: " + ((last + 1 - offset) / 2) * (2 * offset + (last - offset))); } } } }
然后我们创build一个源文件。 使用MyInterface注释的简单类：
@MyInterface(offset = 1, last = 1000) public class Main { @MyInterface void doNothing() { System.out.println("Doing nothing"); } /** * @param args the command line arguments */ public static void main(String[] args) { // TODO code application logic here Main m = new Main(); m.doNothing(); MyInterface my = (MyInterface) m.getClass().getAnnotation(MyInterface.class); System.out.println("offset: " + my.offset()); System.out.println("Last: " + my.last()); } }
注释处理器被编译成jar文件，然后使用apt工具编译源文件：
apt -cp "D:\Variance project\PracticeProject\dist\practiceproject.jar" -factory practiceproject.annotprocess.MyInterfaceAnnotationProcessorFactory "D:\Variance project\PracticeProject2\src\practiceproject2\Main.java"
该项目的产出：
Called supportedAnnotationTypes........................... Called getProcessorFor................ Sum: 5000 Sum: 500500
这是一个在VC ++ 2010下工作的实现。自从编译器在模板recursion500次以后，抱怨，我不得不将计算分成3个阶段。
template<int t_startVal, int t_baseVal = 0, int t_result = 0> struct SumT { enum { result = SumT<t_startVal - 1, t_baseVal, t_baseVal + t_result + t_startVal>::result }; }; template<int t_baseVal, int t_result> struct SumT<0, t_baseVal, t_result> { enum { result = t_result }; }; template<int output_value> struct Dump { enum { value = output_value }; int bad_array[0]; }; enum { value1 = SumT<400>::result, // [1,400] value2 = SumT<400, 400, value1>::result, // [401, 800] value3 = SumT<200, 800, value2>::result // [801, 1000] }; Dump<value3> dump;
当你编译这个时，你应该看到编译器的输出如下所示：
1>warning C4200: nonstandard extension used : zero-sized array in struct/union 1> Cannot generate copy-ctor or copy-assignment operator when UDT contains a zero-sized array 1> templatedrivensum.cpp(33) : see reference to class template instantiation 'Dump<output_value>' being compiled 1> with 1> [ 1> output_value=500500 1> ]
我觉得有义务给这个C代码，因为没有人还没有：
#include <stdio.h> int main() { int x = 1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+ 21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+ 41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+ 61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+ 81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99+100+ 101+102+103+104+105+106+107+108+109+110+111+112+113+114+115+116+117+118+119+120+ 121+122+123+124+125+126+127+128+129+130+131+132+133+134+135+136+137+138+139+140+ 141+142+143+144+145+146+147+148+149+150+151+152+153+154+155+156+157+158+159+160+ 161+162+163+164+165+166+167+168+169+170+171+172+173+174+175+176+177+178+179+180+ 181+182+183+184+185+186+187+188+189+190+191+192+193+194+195+196+197+198+199+200+ 201+202+203+204+205+206+207+208+209+210+211+212+213+214+215+216+217+218+219+220+ 221+222+223+224+225+226+227+228+229+230+231+232+233+234+235+236+237+238+239+240+ 241+242+243+244+245+246+247+248+249+250+251+252+253+254+255+256+257+258+259+260+ 261+262+263+264+265+266+267+268+269+270+271+272+273+274+275+276+277+278+279+280+ 281+282+283+284+285+286+287+288+289+290+291+292+293+294+295+296+297+298+299+300+ 301+302+303+304+305+306+307+308+309+310+311+312+313+314+315+316+317+318+319+320+ 321+322+323+324+325+326+327+328+329+330+331+332+333+334+335+336+337+338+339+340+ 341+342+343+344+345+346+347+348+349+350+351+352+353+354+355+356+357+358+359+360+ 361+362+363+364+365+366+367+368+369+370+371+372+373+374+375+376+377+378+379+380+ 381+382+383+384+385+386+387+388+389+390+391+392+393+394+395+396+397+398+399+400+ 401+402+403+404+405+406+407+408+409+410+411+412+413+414+415+416+417+418+419+420+ 421+422+423+424+425+426+427+428+429+430+431+432+433+434+435+436+437+438+439+440+ 441+442+443+444+445+446+447+448+449+450+451+452+453+454+455+456+457+458+459+460+ 461+462+463+464+465+466+467+468+469+470+471+472+473+474+475+476+477+478+479+480+ 481+482+483+484+485+486+487+488+489+490+491+492+493+494+495+496+497+498+499+500+ 501+502+503+504+505+506+507+508+509+510+511+512+513+514+515+516+517+518+519+520+ 521+522+523+524+525+526+527+528+529+530+531+532+533+534+535+536+537+538+539+540+ 541+542+543+544+545+546+547+548+549+550+551+552+553+554+555+556+557+558+559+560+ 561+562+563+564+565+566+567+568+569+570+571+572+573+574+575+576+577+578+579+580+ 581+582+583+584+585+586+587+588+589+590+591+592+593+594+595+596+597+598+599+600+ 601+602+603+604+605+606+607+608+609+610+611+612+613+614+615+616+617+618+619+620+ 621+622+623+624+625+626+627+628+629+630+631+632+633+634+635+636+637+638+639+640+ 641+642+643+644+645+646+647+648+649+650+651+652+653+654+655+656+657+658+659+660+ 661+662+663+664+665+666+667+668+669+670+671+672+673+674+675+676+677+678+679+680+ 681+682+683+684+685+686+687+688+689+690+691+692+693+694+695+696+697+698+699+700+ 701+702+703+704+705+706+707+708+709+710+711+712+713+714+715+716+717+718+719+720+ 721+722+723+724+725+726+727+728+729+730+731+732+733+734+735+736+737+738+739+740+ 741+742+743+744+745+746+747+748+749+750+751+752+753+754+755+756+757+758+759+760+ 761+762+763+764+765+766+767+768+769+770+771+772+773+774+775+776+777+778+779+780+ 781+782+783+784+785+786+787+788+789+790+791+792+793+794+795+796+797+798+799+800+ 801+802+803+804+805+806+807+808+809+810+811+812+813+814+815+816+817+818+819+820+ 821+822+823+824+825+826+827+828+829+830+831+832+833+834+835+836+837+838+839+840+ 841+842+843+844+845+846+847+848+849+850+851+852+853+854+855+856+857+858+859+860+ 861+862+863+864+865+866+867+868+869+870+871+872+873+874+875+876+877+878+879+880+ 881+882+883+884+885+886+887+888+889+890+891+892+893+894+895+896+897+898+899+900+ 901+902+903+904+905+906+907+908+909+910+911+912+913+914+915+916+917+918+919+920+ 921+922+923+924+925+926+927+928+929+930+931+932+933+934+935+936+937+938+939+940+ 941+942+943+944+945+946+947+948+949+950+951+952+953+954+955+956+957+958+959+960+ 961+962+963+964+965+966+967+968+969+970+971+972+973+974+975+976+977+978+979+980+ 981+982+983+984+985+986+987+988+989+990+991+992+993+994+995+996+997+998+999+1000; printf("%d\n", x); }
而我所需要做的是检查大会find我的答案！
gcc -S compile_sum.c; grep "\$[0-9]*, *-4" compile_sum.s
我看到：
movl $500500, -4(%rbp)
从Carl Walsh的回答扩展到在编译过程中实际打印结果：
#define VALUE (1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19+20+\ 21+22+23+24+25+26+27+28+29+30+31+32+33+34+35+36+37+38+39+40+\ 41+42+43+44+45+46+47+48+49+50+51+52+53+54+55+56+57+58+59+60+\ 61+62+63+64+65+66+67+68+69+70+71+72+73+74+75+76+77+78+79+80+\ 81+82+83+84+85+86+87+88+89+90+91+92+93+94+95+96+97+98+99+100+\ 101+102+103+104+105+106+107+108+109+110+111+112+113+114+115+116+117+118+119+120+\ 121+122+123+124+125+126+127+128+129+130+131+132+133+134+135+136+137+138+139+140+\ 141+142+143+144+145+146+147+148+149+150+151+152+153+154+155+156+157+158+159+160+\ 161+162+163+164+165+166+167+168+169+170+171+172+173+174+175+176+177+178+179+180+\ 181+182+183+184+185+186+187+188+189+190+191+192+193+194+195+196+197+198+199+200+\ 201+202+203+204+205+206+207+208+209+210+211+212+213+214+215+216+217+218+219+220+\ 221+222+223+224+225+226+227+228+229+230+231+232+233+234+235+236+237+238+239+240+\ 241+242+243+244+245+246+247+248+249+250+251+252+253+254+255+256+257+258+259+260+\ 261+262+263+264+265+266+267+268+269+270+271+272+273+274+275+276+277+278+279+280+\ 281+282+283+284+285+286+287+288+289+290+291+292+293+294+295+296+297+298+299+300+\ 301+302+303+304+305+306+307+308+309+310+311+312+313+314+315+316+317+318+319+320+\ 321+322+323+324+325+326+327+328+329+330+331+332+333+334+335+336+337+338+339+340+\ 341+342+343+344+345+346+347+348+349+350+351+352+353+354+355+356+357+358+359+360+\ 361+362+363+364+365+366+367+368+369+370+371+372+373+374+375+376+377+378+379+380+\ 381+382+383+384+385+386+387+388+389+390+391+392+393+394+395+396+397+398+399+400+\ 401+402+403+404+405+406+407+408+409+410+411+412+413+414+415+416+417+418+419+420+\ 421+422+423+424+425+426+427+428+429+430+431+432+433+434+435+436+437+438+439+440+\ 441+442+443+444+445+446+447+448+449+450+451+452+453+454+455+456+457+458+459+460+\ 461+462+463+464+465+466+467+468+469+470+471+472+473+474+475+476+477+478+479+480+\ 481+482+483+484+485+486+487+488+489+490+491+492+493+494+495+496+497+498+499+500+\ 501+502+503+504+505+506+507+508+509+510+511+512+513+514+515+516+517+518+519+520+\ 521+522+523+524+525+526+527+528+529+530+531+532+533+534+535+536+537+538+539+540+\ 541+542+543+544+545+546+547+548+549+550+551+552+553+554+555+556+557+558+559+560+\ 561+562+563+564+565+566+567+568+569+570+571+572+573+574+575+576+577+578+579+580+\ 581+582+583+584+585+586+587+588+589+590+591+592+593+594+595+596+597+598+599+600+\ 601+602+603+604+605+606+607+608+609+610+611+612+613+614+615+616+617+618+619+620+\ 621+622+623+624+625+626+627+628+629+630+631+632+633+634+635+636+637+638+639+640+\ 641+642+643+644+645+646+647+648+649+650+651+652+653+654+655+656+657+658+659+660+\ 661+662+663+664+665+666+667+668+669+670+671+672+673+674+675+676+677+678+679+680+\ 681+682+683+684+685+686+687+688+689+690+691+692+693+694+695+696+697+698+699+700+\ 701+702+703+704+705+706+707+708+709+710+711+712+713+714+715+716+717+718+719+720+\ 721+722+723+724+725+726+727+728+729+730+731+732+733+734+735+736+737+738+739+740+\ 741+742+743+744+745+746+747+748+749+750+751+752+753+754+755+756+757+758+759+760+\ 761+762+763+764+765+766+767+768+769+770+771+772+773+774+775+776+777+778+779+780+\ 781+782+783+784+785+786+787+788+789+790+791+792+793+794+795+796+797+798+799+800+\ 801+802+803+804+805+806+807+808+809+810+811+812+813+814+815+816+817+818+819+820+\ 821+822+823+824+825+826+827+828+829+830+831+832+833+834+835+836+837+838+839+840+\ 841+842+843+844+845+846+847+848+849+850+851+852+853+854+855+856+857+858+859+860+\ 861+862+863+864+865+866+867+868+869+870+871+872+873+874+875+876+877+878+879+880+\ 881+882+883+884+885+886+887+888+889+890+891+892+893+894+895+896+897+898+899+900+\ 901+902+903+904+905+906+907+908+909+910+911+912+913+914+915+916+917+918+919+920+\ 921+922+923+924+925+926+927+928+929+930+931+932+933+934+935+936+937+938+939+940+\ 941+942+943+944+945+946+947+948+949+950+951+952+953+954+955+956+957+958+959+960+\ 961+962+963+964+965+966+967+968+969+970+971+972+973+974+975+976+977+978+979+980+\ 981+982+983+984+985+986+987+988+989+990+991+992+993+994+995+996+997+998+999+1000) char tab[VALUE]; int main() { tab = 5; }
gcc输出：
test.c: In function 'main': test.c:56:9: error: incompatible types when assigning to type 'char[500500]' fro m type 'int'
你可以使用（而且主要是滥用）C ++macros/模板来进行元编程 。 AFAIK，Java不允许有同样的事情。
从理论上讲，你可以使用这个：
#include <iostream> template<int N> struct Triangle{ static int getVal() { return N + Triangle<N-1>::getVal(); } }; template<> struct Triangle<1>{ static int getVal() { return 1; } }; int main(){ std::cout << Triangle<1000>::getVal() << std::endl; return 0; }
（根据Xeo发布的代码）。 但GCC给了我这个错误：
triangle.c++:7: error: template instantiation depth exceeds maximum of 500 (use -ftemplate-depth-NN to increase the maximum) instantiating struct Triangle<500>
加上一个巨大的伪堆栈跟踪。
使用java，你可以做一个类似的事情的C＃答案：
public class Cheat { public static final int x = (1000 *1001/2); } javac -Xprint Cheat.java public class Cheat { public Cheat(); public static final int x = 500500; }
你可以在scala中使用peano数字来做到这一点，因为你可以强制编译器做recursion，但我不认为你可以在c＃/ java中做同样的事情
另一种解决scheme不使用-Xprint，但更加狡猾
public class Cheat { public static final int x = 5/(1000 *1001/2 - 500500); } javac -Xlint:all Cheat.java Cheat.java:2: warning: [divzero] division by zero public static final int x = 5/(1000 *1001/2 - 500500); ^ 1 warning
而不使用任何编译器标志。 因为你可以检查任意数量的常量（不只是500500），这个解决scheme应该是可以接受的。
public class Cheat { public static final short max = (Short.MAX_VALUE - 500500) + 1001*1000/2; public static final short overflow = (Short.MAX_VALUE - 500500 + 1) + 1001*1000/2; } Cheat.java:3: error: possible loss of precision public static final short overflow = (Short.MAX_VALUE - 500500 + 1) + 1001*1000/2; ^ required: short found: int 1 error
虽然这实际上使用小数字，铿锵+ +返回我编译器错误，如果我使用sum_first其中N> 400。
#include <iostream> using namespace std; template <int N> struct sum_first { static const int value = N + sum_first<N - 1>::value; }; template <> struct sum_first<0> { static const int value = 0; }; int main() { cout << sum_first<1000>::value << endl; }
