20

好吧,至少有两种低级方法可以确定给定数字是否为偶数:

 1. if (num%2 == 0) { /* even */ } 
 2. if ((num&1) == 0) { /* even */ }

我认为第二种选择更加优雅和有意义,这是我通常使用的一种。但这不仅仅是品味问题。实际性能可能会有所不同:通常按位运算(例如这里的逻辑与)比 mod(或 div)运算效率更高。当然,您可能会争辩说某些编译器无论如何都能够优化它,我同意……但有些不会。

另一点是,对于经验不足的程序员来说,第二个可能更难理解。关于这一点,我会回答说,如果这些程序员花那么短的时间来理解这种陈述,它可能只会使每个人受益。

你怎么看?

仅当给定的两个片段是num无符号整数或具有二进制补码表示的负数时才是正确的。- 正如一些评论所说的那样。

4

12 回答 12

76

我首先为可读性编写代码,所以我的选择是num % 2 == 0. 这远比num & 1 == 0. 我会让编译器担心为我优化,并且只有在分析显示这是一个瓶颈时才进行调整。其他任何事情都为时过早。

我认为第二种选择更加优雅和有意义

我强烈不同意这一点。一个数字是偶数是因为它的模二的同余性为零,而不是因为它的二进制表示以某个位结尾。二进制表示是一个实现细节。依赖实现细节通常是一种代码味道。正如其他人指出的那样,在使用补码表示的机器上测试 LSB 会失败。

另一点是,对于经验不足的程序员来说,第二个可能更难理解。关于这一点,我会回答说,如果这些程序员花那么短的时间来理解这种陈述,它可能只会使每个人受益。

我不同意。我们都应该编码以使我们的意图更清晰。如果我们正在测试均匀性,代码应该表达出来(并且注释应该是不必要的)。同样,测试模 2 的一致性比检查 LSB 更清楚地表达了代码的意图。

而且,更重要的是,细节应该隐藏在isEven方法中。所以我们应该在 的定义中看到if(isEven(someNumber)) { // details }并且只看到一次。num % 2 == 0isEven

于 2009-12-22T21:27:26.300 回答
24

如果您要说某些编译器不会优化%2,那么您还应该注意某些编译器对有符号整数使用一个补码表示。在该表示中,给出负数&1 的错误答案。

那么你想要什么 - “某些编译器”上的代码很慢,或者“某些编译器”上的代码错误?不一定在每种情况下都使用相同的编译器,但这两种编译器都极为罕见。

当然,如果num它是无符号类型,或者是 C99 固定宽度整数类型之一(int8_t等等,它们必须是 2 的补码),那么这不是问题。在这种情况下,我认为%2它更优雅、更有意义,并且&1是一种可以想象有时对性能来说是必要的 hack。例如,我认为 CPython 没有进行这种优化,完全解释的语言也是如此(尽管解析开销可能会使两个机器指令之间的差异相形见绌)。但是,如果遇到 C 或 C++ 编译器在可能的情况下没有这样做,我会感到有些惊讶,因为如果不是以前,它在发出指令时是不费吹灰之力的。

一般来说,我会说在 C++ 中你完全受制于编译器的优化能力。标准容器和算法有 n 级间接,当编译器完成内联和优化时,大部分都会消失。一个像样的 C++ 编译器可以在早餐前处理带有常量值的算术运算,而一个不像样的 C++ 编译器无论你做什么都会产生垃圾代码。

于 2009-12-22T21:32:43.880 回答
12

您关于性能的结论是基于流行的错误前提。

出于某种原因,您坚持将语言操作翻译成“显而易见的”机器对应物,并根据该翻译得出性能结论。在这种特殊情况下,您得出结论,&C++ 语言的按位与运算必须由按位与机器运算来实现,而模%运算必须以某种方式涉及机器除法,据称这更慢。如果有的话,这种方法的用途非常有限。

首先,我无法想象现实生活中的 C++ 编译器会以这种“字面”方式解释语言操作,即将它们映射到“等效”机器操作。主要是因为人们通常认为等效的机器操作根本不存在。

当涉及到以直接常量作为操作数的基本操作时,任何自尊的编译器都会立即“理解”两者num & 1num % 2forintegralnum做完全相同的事情,这将使编译器为这两个表达式生成完全相同的代码。自然,性能将完全相同。

顺便说一句,这不称为“优化”。根据定义,优化是编译器决定偏离抽象 C++ 机器的标准行为以生成更高效的代码(保留程序的可观察行为)。在这种情况下没有偏差,这意味着没有优化。

此外,很有可能在给定的机器上实现两者的最佳方式既不是按位与也不是除法,而是一些其他专用的机器特定指令。最重要的是,很可能根本不需要任何指令,因为特定值的偶数/奇数可能通过处理器状态标志或类似的东西“免费”公开那。

换句话说,效率论证是无效的。

其次,回到最初的问题,确定值的偶数/奇数的更可取的方法当然是num % 2方法,因为它从字面上实现了所需的检查(“按定义”),并清楚地表达了事实检查是纯数学的。也就是说,它清楚地表明我们关心数字的属性,而不是它的表示的属性(就像num & 1变体的情况一样)。

num & 1当您想要访问数字的值表示的位时,应保留该变体。使用此代码进行偶数/奇数检查是一种非常值得怀疑的做法。

于 2009-12-22T22:07:17.167 回答
12

我定义并使用了一个“IsEven”函数,所以我不必考虑它,然后我选择了一种方法或另一种方法,忘记了我如何检查某事是否是偶数。

只有 nitpick/caveat 是我只想说,通过按位运算,你假设一些关于二进制数字表示的东西,而你不是模数。您正在将该数字解释为十进制值。这几乎可以保证与整数一起使用。但是考虑到模数适用于双精度数,但按位运算不会。

于 2009-12-22T21:26:22.583 回答
9

多次提到任何现代编译器都会为这两个选项创建相同的程序集。这让我想起了前几天在某个地方看到的LLVM 演示页面,所以我想我应该试一试。我知道这只是轶事,但它确实证实了我们的期望:x%2并且x&1实现方式相同。

我还尝试使用 gcc-4.2.1 ( ) 编译这两者,gcc -S foo.c并且生成的程序集是相同的(并粘贴在此答案的底部)。

编程第一个:

int main(int argc, char **argv) {
  return (argc%2==0) ? 0 : 1;
}

结果:

; ModuleID = '/tmp/webcompile/_27244_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

编程第二个:

int main(int argc, char **argv) {
  return ((argc&1)==0) ? 0 : 1;
}

结果:

; ModuleID = '/tmp/webcompile/_27375_0.bc'
target datalayout = "e-p:32:32:32-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:32:64-f32:32:32-f64:32:64-v64:64:64-v128:128:128-a0:0:64-f80:32:32"
target triple = "i386-pc-linux-gnu"

define i32 @main(i32 %argc, i8** nocapture %argv) nounwind readnone {
entry:
    %0 = and i32 %argc, 1       ; <i32> [#uses=1]
    ret i32 %0
}

海合会输出:

.text
.globl _main
_main:
LFB2:
  pushq %rbp
LCFI0:
  movq  %rsp, %rbp
LCFI1:
  movl  %edi, -4(%rbp)
  movq  %rsi, -16(%rbp)
  movl  -4(%rbp), %eax
  andl  $1, %eax
  testl %eax, %eax
  setne %al
  movzbl  %al, %eax
  leave
  ret
LFE2:
  .section __TEXT,__eh_frame,coalesced,no_toc+strip_static_syms+live_support
EH_frame1:
  .set L$set$0,LECIE1-LSCIE1
  .long L$set$0
LSCIE1:
  .long 0x0
  .byte 0x1
  .ascii "zR\0"
  .byte 0x1
  .byte 0x78
  .byte 0x10
  .byte 0x1
  .byte 0x10
  .byte 0xc
  .byte 0x7
  .byte 0x8
  .byte 0x90
  .byte 0x1
  .align 3
LECIE1:
.globl _main.eh
_main.eh:
LSFDE1:
  .set L$set$1,LEFDE1-LASFDE1
  .long L$set$1
ASFDE1:
  .long LASFDE1-EH_frame1
  .quad LFB2-.
  .set L$set$2,LFE2-LFB2
  .quad L$set$2
  .byte 0x0
  .byte 0x4
  .set L$set$3,LCFI0-LFB2
  .long L$set$3
  .byte 0xe
  .byte 0x10
  .byte 0x86
  .byte 0x2
  .byte 0x4
  .set L$set$4,LCFI1-LCFI0
  .long L$set$4
  .byte 0xd
  .byte 0x6
  .align 3
LEFDE1:
  .subsections_via_symbols
于 2009-12-22T22:40:29.753 回答
7

这一切都取决于上下文。如果它是低级别的系统上下文,我实际上更喜欢 &1 方法。在许多此类上下文中,“偶数”对我来说基本上意味着低位为零,而不是可被 2 整除。

然而:你的一个班轮有一个错误。

你必须去

if( (x&1) == 0 )

不是

if( x&1 == 0 )

后者与 x 与 1==0,即它与 x 与 0,产生 0,这当然总是评估为假。

因此,如果您完全按照您的建议进行操作,那么所有数字都是奇数!

于 2009-12-22T21:45:09.737 回答
3

任何现代编译器都会优化模运算,因此速度不是问题。

我想说使用模数会使事情更容易理解,但是创建一个is_even使用该x & 1方法的函数可以让你两全其美。

于 2009-12-22T21:28:57.543 回答
3

它们都非常直观。

我会给 一点优势num % 2 == 0,但我真的没有偏好。当然,就性能而言,它可能是一个微优化,所以我不会担心。

于 2009-12-22T21:29:16.570 回答
2

我花了数年时间坚持认为,任何值得它在磁盘上消耗的空间的合理编译器都会优化num % 2 == 0num & 1 == 0. 然后,出于不同的原因分析反汇编,我有机会实际验证我的假设。

事实证明,我错了。Microsoft Visual Studio一直到 2013 版,为 生成以下目标代码num % 2 == 0

    and ecx, -2147483647        ; the parameter was passed in ECX
    jns SHORT $IsEven
    dec ecx
    or  ecx, -2
    inc ecx
$IsEven:
    neg ecx
    sbb ecx, ecx
    lea eax, DWORD PTR [ecx+1]

确实是的。这是在发布模式下,启用了所有优化。无论是为 x86 还是 x64 构建,您都会得到几乎相同的结果。你可能不会相信我;我自己几乎不相信。

它基本上可以满足您的期望num & 1 == 0

not  eax                        ; the parameter was passed in EAX
and  eax, 1

相比之下,GCC(早于 v4.4)和Clang(早于 v3.2)可以满足人们的期望,为两种变体生成相同的目标代码。然而,根据Matt Godbolt 的交互式编译器ICC 13.0.1 也出乎我的意料。

当然,这些编译器没有。这不是一个错误。有很多技术原因(正如其他答案中充分指出的那样)为什么这两个代码片段不相同。这里肯定有一个“过早的优化是邪恶的”的论点。诚然,我花了数年时间才注意到这一点是有原因的,即便如此,我也只是错误地偶然发现了它。

但是,就像 Doug T. 所说的那样,最好IsEven在库中的某个地方定义一个函数,使所有这些小细节都正确,这样您就不必再考虑它们了——并保持您的代码可读。如果你经常以 MSVC 为目标,也许你会像我一样定义这个函数:

bool IsEven(int value)
{
    const bool result = (num & 1) == 0;
    assert(result == ((num % 2) == 0));
    return result;   
}
于 2014-08-10T16:14:41.147 回答
0

这两种方法都不是很明显,尤其是对于刚接触编程的人来说。您应该定义一个inline具有描述性名称的函数。您在其中使用的方法无关紧要(微优化很可能不会以明显的方式使您的程序更快)。

无论如何,我相信 2) 更快,因为它不需要除法。

于 2009-12-22T21:28:17.310 回答
0

我认为模数不会使事情更具可读性。两者都有意义,并且两个版本都是正确的。计算机以二进制形式存储数字,因此您可以只使用二进制版本。

编译器可以用有效的版本替换模版本。但这听起来像是偏爱模数的借口。

在这种非常特殊的情况下,两个版本的可读性是相同的。刚接触编程的读者可能甚至不知道您可以使用模 2 来确定数字的偶数。读者必须推断它。他可能连模运算符都不知道

在推断语句背后的含义时,阅读二进制版本甚至会更容易:

if( ( num & 1 ) == 0 ) { /* even */ }
if( ( 00010111b & 1 ) == 0 ) { /* even */ }
if( ( 00010110b & 1 ) == 0 ) { /* odd */ }

(我使用“b”后缀只是为了澄清,它不是 C/C++)

对于模数版本,您必须仔细检查操作是如何在其详细信息中定义的(例如,检查文档以确保这0 % 2是您所期望的)。

二进制AND更简单,没有歧义!

只有运算符优先级可能是二元运算符的陷阱。但这不应该成为避免它们的理由(总有一天,即使是新程序员也会需要它们)。

于 2009-12-22T21:52:12.673 回答
-2

在这一点上,我可能只是增加了噪音,但就可读性而言,模选项更有意义。如果您的代码不可读,那么它实际上是无用的。

此外,除非这是要在资源非常紧张的系统上运行的代码(我在想微控制器),否则不要尝试针对编译器的优化器进行优化。

于 2009-12-22T22:19:32.343 回答