首页 文章

如何驱动C#,C或Java编译器在编译时计算1 2 3 ... 1000?

提问于
浏览
120

在最近的一次采访中,我被问到一个非常奇怪的问题 . 面试官问我如何使用编译器功能计算1 2 3 ... 1000 . 这意味着我不允许编写程序并执行它,但我应该编写一个程序,可以驱动编译器在编译时计算这个总和,并在编译完成时打印结果 . 作为提示,他告诉我,我可能会使用编译器的泛型和预处理器功能 . 可以使用C,C#或Java编译器 . 有任何想法吗???

这个问题与没有任何循环计算总和无关asked here . 另外,应该注意,总和应该在编译期间计算 . 使用C编译器指令仅打印结果是不可接受的 .


阅读有关已发布答案的更多信息,我发现使用C模板在编译期间解决问题称为 metaprogramming . 这是Erwin Unruh博士在标准化C语言过程中偶然发现的一种技术 . 您可以在wiki page of meta-programming上阅读有关此主题的更多信息 . 似乎可以使用Java注释在Java中编写程序 . 你可以看看下面的 maress's 答案 .

关于C中的元编程的一本好书是this one . 如果感兴趣,值得一看 .

一个有用的C元编程库是Boost的MPL this link .

13 回答

  • 116

    我觉得有义务提供这个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);
    }
    

    而我需要做的就是检查装配以找到答案!

    gcc -S compile_sum.c;
    grep "\$[0-9]*, *-4" compile_sum.s
    

    我明白了:

    movl    $500500, -4(%rbp)
    
  • 7

    从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'
    
  • 1

    您可以使用(并且主要是滥用)C宏/模板来执行metaprogramming . AFAIK,Java不允许同样的事情 .

  • 49

    Updated 现在改进了递归深度!适用于MSVC10和GCC而不会增加深度 . :)


    简单的编译时递归添加:

    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>'的声明

    Live example on Ideone .

    MSVC10的输出:

    error C2514: 'sum_from<Start>::to<Goal>::equals<Result>' : class has no constructors
          with
          [
              Start=1,
              Goal=1000,
              Result=500500
          ]
    
  • 30

    编译时出错的C#示例 .

    class Foo
    {
        const char Sum = (1000 + 1) * 1000 / 2;
    }
    

    产生以下编译错误:

    Constant value '500500' cannot be converted to a 'char'
    
  • 4

    我应该编写一个程序,可以驱动编译器在编译时计算这个总和,并在编译完成时打印结果 .

    在编译期间打印数字的一个流行技巧是尝试访问使用您要打印的数字实例化的模板的不存在的成员:

    template<int> struct print_n {};
    
    print_n<1000 * 1001 / 2>::foobar go;
    

    然后编译器说:

    error: 'foobar' in 'struct print_n<500500>' does not name a type
    

    有关此技术的更有趣示例,请参阅Solve the eight queens problem at compile-time .

  • 7

    由于在面试问题中既未指定编译器也未指定语言,我敢于使用GHC在Haskell中提交解决方案:

    {-# 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 ...
    

    我们也有一个工作计划 .

  • 0

    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的递归深度,因此它仍然需要避免线性递归深度 . 这是输出:

    $ 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");
    
  • 18

    在java中,我考虑过使用注释处理 . apt工具在将源文件实际解析为javac命令之前扫描源文件 .

    在编译源文件期间,输出将被打印出来:

    @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)));
                }
            }
        }
    }
    

    然后我们创建一个源文件 . 使用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
    
  • 88

    这是一个在VC 2010下工作的实现 . 由于编译器在模板递归500次时抱怨,我不得不将计算分为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>          ]
    
  • 2

    从理论上讲,你可以使用这个:

    #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:错误:模板实例化深度超过最大值500(使用-ftemplate-depth-NN增加最大值)实例化struct Triangle <500>

    加上一个巨大的伪堆栈跟踪 .

  • 1

    使用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 using peano numbers中执行此操作,因为您可以强制编译器执行递归,但我不认为您可以在c#/ java中执行相同的操作

    另一个解决方案不是使用-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),这个解决方案应该是可以接受的 .

    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
    
  • 12

    虽然这实际上适用于小数字,但如果我使用sum_first,则clang会返回编译器错误,其中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;
    }
    

相关问题