在C中使用移位运算符的乘法和除法实际上更快吗？
|
例如，可以使用位运算符来实现乘法和除法
i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)
没有找到相关结果
已邀请:
19 个回复
芭隘的盘石
了驳
unsigned hash( char const* s ) { unsigned h = 0; while ( *s != \'\\0\' ) { h = 127 * h + (unsigned char)*s; ++ s; } return h; }unsigned hash( char const* s ) { unsigned h = 0; while ( *s != \'\\0\' ) { h = (h << 7) - h + (unsigned char)*s; ++ s; } return h; }和迭代器。）骂狮淋唐便
和有很大的不同！ 如果您正在处理数字，请使用算术运算符，例如。如果您正在处理位数组，请使用像这样的位旋转运算符。不要混在一起；一个既有点摇摆又有算术的表达式是一个等待发生的错误。容淑阔九
仿普
和，因此这在理论上和历史上似乎都是荒谬的，但重要的是选择实现的自由是双向的：即使CPU的指令实现了源代码中所请求的操作，一般情况下，编译器可以自由选择其喜欢的其他内容，因为它对于编译器所面对的特定情况更好。 示例（假设的汇编语言）source literal approach optimised approach #define N 0 int x; .word x xor registerA, registerA x *= N; move x -> registerA move x -> registerB A = B * immediate(0) store registerA -> x ...............do something more with x...............）之类的指令与源代码无关，但对其自身进行异或运算会清除所有位，因此可以将其设置为0。源代码暗示内存地址可能不需要使用任何内容。 。 只要计算机存在，这类黑客就一直被使用。在3GL的早期，为了确保开发人员的使用，编译器的输出必须满足现有的核心手动优化汇编语言开发人员的要求。社区认为所生成的代码并不会更慢，更冗长或更糟。编译器迅速采用了许多重大优化措施-尽管它们总是有可能错过了在特定情况下至关重要的特定优化程序，但它们却成为比任何单个汇编语言程序员都可能更好的集中存储程序。有时，人们可以胡思乱想，寻求更好的东西，而编译器只是按照被告知的方式工作，直到有人将经验反馈给他们。 因此，即使在某些特定的硬件上转移和添加仍然更快，那么编译器编写者在安全和有益的前提下也可能会得出准确的结果。 可维护性 如果您的硬件发生了变化，则可以重新编译，它会查看目标CPU并做出另一个最佳选择，而您不太可能希望重新访问“优化”或列出哪些编译环境应使用乘法以及哪些编译环境应该使用乘法应该转变。想想10年前写的所有非2幂次移位的“优化”，它们现在在现代处理器上运行时正在减慢它们的代码速度！！ 值得庆幸的是，启用任何优化后（例如...main(...) { return (argc << 4) + (argc << 2) + argc; }），良好的编译器（如GCC）通常可以使用直接乘法替换一系列移位和算术运算，因此即使不修复代码也可以帮助重新编译，但这不能保证。 实现乘法或除法的奇怪的移位代码无法充分表达您在概念上想要实现的目标，因此其他开发人员将对此感到困惑，并且困惑的程序员更有可能引入错误或删除一些必要的东西以进行恢复看起来很理智。如果您仅在非显而易见的事情真正受益时才做，然后很好地记录下来（但无论如何也不要记录其他直观的事情），那么每个人都会更加快乐。 一般解决方案与部分解决方案 如果您有一些额外的知识，例如您的ѭ17really实际上仅存储值，和ѭ20may，那么您可能能够得出一些适用于这些值的指令，并且比编译器更快地得到结果。 \'s没有这种洞察力，需要一个适用于所有值的实现。例如，考虑您的问题： 可以使用位运算符来实现乘法和除法... 您说明了乘法，但是除法又如何呢？根据C ++标准5.8： -3- E1 >> E2的值是E1右移E2位的位置。如果E1具有无符号类型，或者E1具有带符号类型且非负值，则结果的值是E1商的整数部分除以乘以幂E2的数量2。如果E1具有带符号的类型和负值，则结果值是实现定义的。 因此，当为负数时，您的移位具有实现定义的结果：在不同的机器上，它的工作方式可能不同。但是，的工作原理更可预测。 （这也可能不是完全一致的，因为不同的机器可能具有不同的负数表示形式，因此即使在组成表示的位数相同的情况下，范围也不同。） 您可能会说：“我不在乎...ѭ17正在存储员工的年龄，它永远不会是负数”。如果您有这种特殊的见识，那么可以-编译器可能会将您的安全优化传递给您，除非您在代码中明确进行了优化。但是，这是冒险的，并且很少会有用，因为在很多时候您不会有这种洞察力，并且其他使用同一代码工作的程序员不会知道您将赌注押在了一些不寻常的地方对您将要处理的数据的期望……由于“优化”，看起来完全安全的更改可能适得其反。 是否存在无法以这种方式相乘或除法的输入？ 是的...如上所述，当通过位移位“除”时，负数具有实现定义的行为。素汞读
拆卸时会产生输出：该版本比纯手工移位和加法的手动优化代码要快。 您实际上永远都不知道编译器将要提出什么，因此最好编写一个普通的乘法并让他优化他想要的方式，除非在非常精确的情况下，您知道编译器无法优化。谷靛
会产生：mov eax,9999999 mov edx,0A7C5AC47h add eax,1 .if !CARRY? mul edx .endif shr edx,16超可林
#include <stdio.h> int main(void) { int i; for (i = 5; i >= -5; --i) { printf(\"%d / 2 = %d, %d >> 1 = %d\\n\", i, i / 2, i, i >> 1); } return 0; }因此，如果要帮助编译器，请确保被除数中的变量或表达式是显式无符号的。涸坍饺
蹄渭信妥扳
结乳
搂腹时
草票
河饶办斜施
因此，在python中进行移位而不是乘以2的乘积/除法时，会略有改善（除法约为10％；乘法约为1％）。如果其非2的幂，则可能会出现相当大的减速。 同样，这些＃号将根据您的处理器，您的编译器（或解释器-为简单起见在python中执行）而更改。 与其他所有人一样，请勿过早优化。编写易读的代码，如果速度不够快，则进行概要分析，然后尝试优化慢速部分。请记住，您的编译器在优化方面比您要好得多。涸坍饺
#include <stdio.h> #include <chrono> static const unsigned s_bc = 32; static const unsigned long long s_p = 1ULL << s_bc; static const unsigned long long s_hp = s_p / 2; static unsigned long long s_f; static unsigned long long s_fr; static void fastDivInitialize(const unsigned d) { s_f = s_p / d; s_fr = s_f * (s_p - (s_f * d)); } static unsigned fastDiv(const unsigned n) { return (s_f * n + ((s_fr * n + s_hp) >> s_bc)) >> s_bc; } static bool fastDivCheck(const unsigned n, const unsigned d) { // 32 to 64 cycles latency on modern cpus const unsigned expected = n / d; // At least 10 cycles latency on modern cpus const unsigned result = fastDiv(n); if (result != expected) { printf(\"Failed for: %u/%u != %u\\n\", n, d, expected); return false; } return true; } int main() { unsigned result = 0; // Make sure to verify it works for your expected set of inputs const unsigned MAX_N = 65535; const unsigned MAX_D = 40000; const double ONE_SECOND_COUNT = 1000000000.0; auto t0 = std::chrono::steady_clock::now(); unsigned count = 0; printf(\"Verifying...\\n\"); for (unsigned d = 1; d <= MAX_D; ++d) { fastDivInitialize(d); for (unsigned n = 0; n <= MAX_N; ++n) { count += !fastDivCheck(n, d); } } auto t1 = std::chrono::steady_clock::now(); printf(\"Errors: %u / %u (%.4fs)\\n\", count, MAX_D * (MAX_N + 1), (t1 - t0).count() / ONE_SECOND_COUNT); t0 = t1; for (unsigned d = 1; d <= MAX_D; ++d) { fastDivInitialize(d); for (unsigned n = 0; n <= MAX_N; ++n) { result += fastDiv(n); } } t1 = std::chrono::steady_clock::now(); printf(\"Fast division time: %.4fs\\n\", (t1 - t0).count() / ONE_SECOND_COUNT); t0 = t1; count = 0; for (unsigned d = 1; d <= MAX_D; ++d) { for (unsigned n = 0; n <= MAX_N; ++n) { result += n / d; } } t1 = std::chrono::steady_clock::now(); printf(\"Normal division time: %.4fs\\n\", (t1 - t0).count() / ONE_SECOND_COUNT); getchar(); return result; }久坡
膏焦凑
谷起
push rbp mov rbp, rsp mov DWORD PTR [rbp-4], edi mov eax, DWORD PTR [rbp-4] add eax, eax pop rbp ret蜗仓馈
#include <stdio.h> #include <time.h> #define MULTIPLYINTBYMINUS(X,Y) (-((X >> 30) & 1)&(Y<<30))+(-((X >> 29) & 1)&(Y<<29))+(-((X >> 28) & 1)&(Y<<28))+(-((X >> 27) & 1)&(Y<<27))+(-((X >> 26) & 1)&(Y<<26))+(-((X >> 25) & 1)&(Y<<25))+(-((X >> 24) & 1)&(Y<<24))+(-((X >> 23) & 1)&(Y<<23))+(-((X >> 22) & 1)&(Y<<22))+(-((X >> 21) & 1)&(Y<<21))+(-((X >> 20) & 1)&(Y<<20))+(-((X >> 19) & 1)&(Y<<19))+(-((X >> 18) & 1)&(Y<<18))+(-((X >> 17) & 1)&(Y<<17))+(-((X >> 16) & 1)&(Y<<16))+(-((X >> 15) & 1)&(Y<<15))+(-((X >> 14) & 1)&(Y<<14))+(-((X >> 13) & 1)&(Y<<13))+(-((X >> 12) & 1)&(Y<<12))+(-((X >> 11) & 1)&(Y<<11))+(-((X >> 10) & 1)&(Y<<10))+(-((X >> 9) & 1)&(Y<<9))+(-((X >> 8) & 1)&(Y<<8))+(-((X >> 7) & 1)&(Y<<7))+(-((X >> 6) & 1)&(Y<<6))+(-((X >> 5) & 1)&(Y<<5))+(-((X >> 4) & 1)&(Y<<4))+(-((X >> 3) & 1)&(Y<<3))+(-((X >> 2) & 1)&(Y<<2))+(-((X >> 1) & 1)&(Y<<1))+(-((X >> 0) & 1)&(Y<<0)) #define MULTIPLYINTBYSHIFT(X,Y) (((((X >> 30) & 1)<<31)>>31)&(Y<<30))+(((((X >> 29) & 1)<<31)>>31)&(Y<<29))+(((((X >> 28) & 1)<<31)>>31)&(Y<<28))+(((((X >> 27) & 1)<<31)>>31)&(Y<<27))+(((((X >> 26) & 1)<<31)>>31)&(Y<<26))+(((((X >> 25) & 1)<<31)>>31)&(Y<<25))+(((((X >> 24) & 1)<<31)>>31)&(Y<<24))+(((((X >> 23) & 1)<<31)>>31)&(Y<<23))+(((((X >> 22) & 1)<<31)>>31)&(Y<<22))+(((((X >> 21) & 1)<<31)>>31)&(Y<<21))+(((((X >> 20) & 1)<<31)>>31)&(Y<<20))+(((((X >> 19) & 1)<<31)>>31)&(Y<<19))+(((((X >> 18) & 1)<<31)>>31)&(Y<<18))+(((((X >> 17) & 1)<<31)>>31)&(Y<<17))+(((((X >> 16) & 1)<<31)>>31)&(Y<<16))+(((((X >> 15) & 1)<<31)>>31)&(Y<<15))+(((((X >> 14) & 1)<<31)>>31)&(Y<<14))+(((((X >> 13) & 1)<<31)>>31)&(Y<<13))+(((((X >> 12) & 1)<<31)>>31)&(Y<<12))+(((((X >> 11) & 1)<<31)>>31)&(Y<<11))+(((((X >> 10) & 1)<<31)>>31)&(Y<<10))+(((((X >> 9) & 1)<<31)>>31)&(Y<<9))+(((((X >> 8) & 1)<<31)>>31)&(Y<<8))+(((((X >> 7) & 1)<<31)>>31)&(Y<<7))+(((((X >> 6) & 1)<<31)>>31)&(Y<<6))+(((((X >> 5) & 1)<<31)>>31)&(Y<<5))+(((((X >> 4) & 1)<<31)>>31)&(Y<<4))+(((((X >> 3) & 1)<<31)>>31)&(Y<<3))+(((((X >> 2) & 1)<<31)>>31)&(Y<<2))+(((((X >> 1) & 1)<<31)>>31)&(Y<<1))+(((((X >> 0) & 1)<<31)>>31)&(Y<<0)) int main() { int randomnumber=23; int randomnumber2=23; int checknum=23; clock_t start, diff; srand(time(0)); start = clock(); for(int i=0;i<1000000;i++) { randomnumber = rand() % 10000; randomnumber2 = rand() % 10000; checknum=MULTIPLYINTBYMINUS(randomnumber,randomnumber2); if (checknum!=randomnumber*randomnumber2) { printf(\"s %i and %i and %i\",checknum,randomnumber,randomnumber2); } } diff = clock() - start; int msec = diff * 1000 / CLOCKS_PER_SEC; printf(\"MULTIPLYINTBYMINUS Time %d milliseconds\", msec); start = clock(); for(int i=0;i<1000000;i++) { randomnumber = rand() % 10000; randomnumber2 = rand() % 10000; checknum=MULTIPLYINTBYSHIFT(randomnumber,randomnumber2); if (checknum!=randomnumber*randomnumber2) { printf(\"s %i and %i and %i\",checknum,randomnumber,randomnumber2); } } diff = clock() - start; msec = diff * 1000 / CLOCKS_PER_SEC; printf(\"MULTIPLYINTBYSHIFT Time %d milliseconds\", msec); start = clock(); for(int i=0;i<1000000;i++) { randomnumber = rand() % 10000; randomnumber2 = rand() % 10000; checknum= randomnumber*randomnumber2; if (checknum!=randomnumber*randomnumber2) { printf(\"s %i and %i and %i\",checknum,randomnumber,randomnumber2); } } diff = clock() - start; msec = diff * 1000 / CLOCKS_PER_SEC; printf(\"normal * Time %d milliseconds\", msec); return 0; }