如何在C中优化这段代码

int number = 16;
int mask   = 1<<5;

if ((number & mask) == 0)
    printf("Bit is off");
else
    printf("its on");

也许面试官想看看你对一个简单挑战的反应.或者只是想知道你是否真的了解C,并坚持自己的立场？也许面试官想知道你是否知道非零是真的,因此测试你对C的理解深度？或者也许你是否可以在头脑中做二进制到十六进制？

恕我直言的采访不仅仅是代码.它们做起来很昂贵.我总是试图给人一个清晰的印象,通过书面沟通,甚至通过电话很难做到.毕竟,其中一些人将与新兵一起工作！

最紧凑,可能最快的可能是：

int number = 16;  // is this really what they gave?

printf((number & 0x20)?"its on":"Bit is off"); // did they mean 5th or bit 5?

编辑：

我编写了原始方法和我的替代方案,并为ARM Coretx-M3 / 4编译了它(这是我目前正在编写的处理器).它是用-O3编译的.然后我反汇编每个编译文件(使用objdump)来获取汇编程序.我是这样做的,因为gcc -S的输出很大;这包括汇编器和链接器的大量额外信息,这使得查找代码变得更加困难.

我用dummy_printf替换了printf以避免#including stdio.h,这增加了更多的噪音. dummy_printf与printf不完全相同,只需要一个参数,但它会使输出保持简短:-)

源(附加的所有7个文件使其更易于阅读)位于：
http://pastebin.com/PTeApu9n

得到的objdump连接输出(对于每个.o)位于：
http://pastebin.com/kHAmakE3

如您所见,原始编译为：

void original_bit5(int number) {
    int mask = 1<<5;

    if ((number & mask) == 0)
   0:   f010 0f20   tst.w   r0,#32
   4:   d005        beq.n   1a <original_bit5+0x1a>
        dummy_printf("Bit is off");
    else
        dummy_printf("its on"); 
   6:   f240 0000   movw    r0,#0
   a:   f2c0 0000   movt    r0,#0
   e:   f7ff bffe   b.w 0 <dummy_printf>

void original_bit5(int number) {
    int mask = 1<<5;

    if ((number & mask) == 0)
        dummy_printf("Bit is off");
  12:   f240 0000   movw    r0,#0
  16:   f2c0 0000   movt    r0,#0
  1a:   f7ff bffe   b.w 0 <dummy_printf>
  1e:   bf00        nop

我认为对dummy_printf的调用是使用尾调用链接,即dummy_printf不会返回此函数.效率很高！

没有函数入口代码,因为前四个函数参数在寄存器r0-r3中传递.

您无法在r0中看到正在加载的两个字符串的地址.那是因为这没有联系.

你可以看到：

int mask = 1<<5;    
if ((number & mask) == 0)

编译为：

0:   f010 0f20   tst.w   r0,#32
   4:   d005        beq.n   1a <original_bit5+0x1a>

因此1<<< 5和(... == 0)被编译成更直接和有效的指令序列.有一个分支到适当的dummy_printf调用. 我的代码编译为：

void my_bit5(int number) {
    dummy_printf((number & 0x20)?"its on":"Bit is off");    
   0:   f240 0200   movw    r2,#0
   4:   f240 0300   movw    r3,#0
   8:   f010 0f20   tst.w   r0,#32
   c:   f2c0 0200   movt    r2,#0
  10:   f2c0 0300   movt    r3,#0
  14:   bf14        ite ne
  16:   4610        movne   r0,r2
  18:   4618        moveq   r0,r3
  1a:   f7ff bffe   b.w 0 <dummy_printf>
  1e:   bf00        nop

这似乎也得到尾调用优化,即没有返回此函数,因为不需要一个,dummy_printf的返回将直接返回main()

你看不到的是两个寄存器,r2和r2将包含两个字符串的地址.那是因为这没有联系.

如您所见,有一个条件执行指令’ite’,它将寄存器r2或寄存器r3加载到参数寄存器r0中.所以这段代码中没有分支.

对于带流水线的简单处理器,这可能非常有效.在简单的流水线处理器上,分支可能会导致“管道”停顿,同时清除管道的某些部分.这因处理器而异.所以我假设gcc已经做对了,并且生成了比执行分支更好的代码序列.我没有检查过.

在伦丁的激励下,我想出了这个：

void union_bit5(int number) {
    union { int n; struct { unsigned :5; unsigned bit :1; }; } tester;
    tester.n = number;

    if (tester.bit)
        dummy_printf("Bit is on");
    else
        dummy_printf("its off");    
}

它没有明确地包括掩码或位移.它几乎肯定是编译器依赖的,你必须测试它以确保它的工作(glerk！ – (

ARM的gcc生成相同的代码(bne vs beq,但可以调整)作为OP的解决方案,因此没有优化,但它删除了掩码：

void union_bit5(int number) {
    union { int n; struct { unsigned :5; unsigned bit :1; }; } tester;
    tester.n = number;

    if (tester.bit)
   0:   f010 0f20   tst.w   r0,#32
   4:   d105        bne.n   1a <union_bit5+0x1a>
        dummy_printf("Bit is on");
    else
        dummy_printf("its off");    
   6:   f240 0000   movw    r0,#0
   e:   f7ff bffe   b.w 0 <dummy_printf>
void union_bit5(int number) {
    union { int n; struct { unsigned :5; unsigned bit :1; }; } tester;
    tester.n = number;

    if (tester.bit)
        dummy_printf("Bit is on");
  12:   f240 0000   movw    r0,#0
  1a:   f7ff bffe   b.w 0 <dummy_printf>
  1e:   bf00        nop

物有所值：

(number & 0x20)? dummy_printf("its on") : dummy_printf("Bit is off");

ARM的gcc生成与OP完全相同的代码.它生成分支,而不是条件指令.

摘要：

>原始代码被编译为非常有效的指令序列
>三元组……？…：…运算符可以编译为不涉及ARM Cortex-M3 / 4上的分支的代码,但也可以生成正常的分支指令.
>在这种情况下,编写比原始代码更高效的代码很困难:-)

我要补充一点,恕我直言,与一点测试相比,做一个printf的成本是如此巨大,担心优化一点测试的问题太小了;它是失败的Amdahl’s Law.比特测试的适当策略是确保使用-O3或-Os.

如果你想做一些有点不正常的事情(特别是对于这样一个微不足道的问题),但可能会让采访者想到的不同,那就为每个字节值创建一个查找表. (我不指望它会更快……)

#define BIT5(val) (((val)&0x20)?1:0)
const unsigned char bit5[256] = {
BIT5(0x00),BIT5(0x01),BIT5(0x02),BIT5(0x03),BIT5(0x04),BIT5(0x05),BIT5(0x06),BIT5(0x07),// ... you get the idea ...
BIT5(0xF8),BIT5(0xF9),BIT5(0xFA),BIT5(0xFB),BIT5(0xFC),BIT5(0xFD),BIT5(0xFE),BIT5(0xFF)
};

//...
if (bit5[(unsigned char)number]) {
    printf("its on");
} else {
    printf("Bit is off");
}

如果在例如外围寄存器中存在某些复杂的位模式(这需要转换为决策或开关),则这是一种方便的技术.它也是O(1)

你可以将两者结合起来！ – )