通过查看最后一位来检查数字是否为偶数 - 还有其他像这样的“技巧”吗?

问题描述 投票:0回答:7

最近我发现,如果我需要查看变量是偶数(还是奇数),我可以只查看变量的最后一位是否等于 0。这个发现在实现时取代了一些 modulo 2 计算,从而取代了整个函数跑得更快了。

还有其他像这样的“技巧”吗?使用位可以代替其他计算,从而缩短函数执行时间?

c++ bit-manipulation
7个回答
22
投票

我怀疑用等效的按位运算替换模二计算的使用会产生更快的执行时间。任何有价值的 C++ 编译器都会将

n % 2
n & 1
编译为相同的机器指令。

谨防使用一些小技巧来进行优化。首先,并不总是清楚您正在优化的函数是否是瓶颈。其次,生成的代码通常更难维护,并且更可能不正确或存在细微的错误。这就是高德纳 (Knuth) 名言的含义:“我们应该忘记微小的效率,大约 97% 的情况下:过早的优化是万恶之源。”节省您的精力。

如果你确实必须研究这个主题,Bit Twiddling Hacks包含了一系列有趣的技巧。


4
投票

4
投票

嗯,有一本关于这个主题的好书:Hacker's Delight(Google 图书)。

在 Amazon.com 上:黑客之乐


3
投票

有很多。您可以从一个在线“集合”开始:http://www-graphics.stanford.edu/~seander/bithacks.html

我强烈建议不要在代码中使用位调整技巧,除非绝对、绝对、100% 需要性能提升。这些技巧非常难以理解,并且给他们一种“这不可能”的感觉,所以当你试图找出错误时,无论是谁试图调试代码,它们都是有效的时间浪费。


1
投票

值得注意的是,当 C++ 将

modulo 2
操作视为
%2
时,它通常会在不执行按位操作的情况下进行优化。

虽然理解所有这些技巧会很有启发,但应该令人高兴的是,编译器(或编译器编写者)付出了艰苦的努力来实现所有可能的优化。

您应该记住的是,如果您使用常量并以 2 的幂进行工作,则更有可能进行优化,因为编译器利用机器的二元运算符能力。


更进一步,我建议了解系统如何在低级别工作。

为此,学习您在这里提到的技巧将是非常有用
然而,神秘的编码与复杂的操作挤在一起
(也就是说,用更少的源代码字节来完成这一切)是不好的。

知道您可以“就地”交换两个 32 位变量,而不需要第三个临时变量——使用 XOR 运算,这可能是件好事。但是,了解 2/4 字节变量如何交叉编译需要大端和小端处理会更有用和位字段

谈论位字段,让我想起另一个 stackoverflow 关于其受欢迎程度的对话。也将是一本很好的读物(尽管与你的问题并不完全相关)。


总而言之,我完全同意你学习可以做什么技巧。我想使用它们来使我的代码性能更好 - 而且,我强烈认为这将是这样的概念,例如,程序员可以做什么来实现更好的缓存优化,这将有助于实现更好的实现。


1
投票

这是一个巧妙的技巧。 当在需要大量搜索的数据库字段中存储日期时,不要以日期格式存储日期,而是以 YYYYMMDD 格式将其存储为整数。 数据库搜索整数的速度比日期结构快得多。


1
投票

我第一次看到“按位标志”时觉得它们有点简洁: http://www.infernodevelopment.com/bitwise-and-flags

© www.soinside.com 2019 - 2024. All rights reserved.