c - 如何在 C 中优化这段代码

Question

昨天，在一次采访中，我被要求测试一个数字中的第 5 位(以测试它是否打开和关闭)，下面是我是如何做到的。

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

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

但随后他让我优化这段代码，并且在不使用这个特定掩码的情况下进行。

所以我的问题是我可以在这段代码中使用什么其他掩码？

Answer 1

也许面试官想看看你对一个简单的挑战有何 react 。或者只是想知道您是否真的了解 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 以避免 #include 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 做对了，并且生成了比执行分支更好的代码序列。我没查过。

在 Lundin 的刺激下，我想出了这个:

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 生成与 OP 解决方案相同的代码(bne vs beq，但可以调整)，因此没有优化，但它删除了掩码:

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
   a:   f2c0 0000   movt    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
  16:   f2c0 0000   movt    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)

你可以把两者结合起来!-)