在 C 中使用移位运算符的乘法和除法实际上更快吗？

Question

例如可以使用位运算符

i*2 = i<<1
i*3 = (i<<1) + i;
i*10 = (i<<3) + (i<<1)

等来实现乘法和除法。

使用 (i<<3)+(i<<1) 乘以 10 实际上比直接使用 i*10 更快吗？是否有任何类型的输入不能以这种方式相乘或相除？

Answer 1

简短回答：不太可能。

长答案：
您的编译器中有一个优化器，它知道如何按照目标处理器架构的速度进行乘法运算。最好的选择是清楚地告诉编译器您的意图（即 i*2 而不是 i << 1），并让它决定最快的汇编/机器代码序列是什么。甚至有可能处理器本身已将乘法指令实现为一系列移位和乘法指令。添加微代码。

最重要的是——不要花太多时间担心这个。如果你想改变，那就改变吧。如果你想乘法，就乘法。做语义上最清晰的事情——你的同事稍后会感谢你。或者，更可能的是，如果你不这样做，稍后就会诅咒你。

Answer 2

只是一个具体的衡量标准：很多年前，我对两个指标进行了基准测试
我的哈希算法的版本：

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;
}

我对其进行基准测试的每台机器上，第一个至少与
第二个。有点令人惊讶的是，它有时会更快（例如在
太阳斯帕克）。当硬件不支持快速乘法时（并且
大多数人当时没有），编译器会转换乘法
转变为适当的班次和添加/子组合。又因为它
知道最终目标，有时可以用比
当您明确编写班次和添加/替换时。

请注意，这大约是 15 年前的事了。希望编译器
从那时起，情况才变得更好，所以你几乎可以信赖
编译器做了正确的事情，可能比你更好。 （还，
代码之所以看起来如此 C'ish，是因为它是 15 年前的事了。
我今天显然会使用 std::string 和迭代器。）

Answer 3

除了这里所有其他好的答案之外，让我指出当您指的是除法或乘法时不使用移位的另一个原因。我从未见过有人因忘记乘法和加法的相对优先级而引入错误。我见过一些错误，因为维护程序员忘记了通过移位进行“乘法”在逻辑上是乘法，但在语法上与乘法的优先级不同。 x * 2 + z 和 x << 1 + z 非常不同！

如果您正在处理数字，请使用算术运算符，例如+ - * / %。如果您正在处理位数组，请使用位旋转运算符，例如 & ^ | >> 。不要混合它们；同时具有位运算和算术运算的表达式是一个等待发生的错误。

Answer 4

这取决于处理器和编译器。一些编译器已经以这种方式优化代码，而另一些则没有。
因此，每次需要以这种方式优化代码时，您都需要进行检查。

除非您迫切需要优化，否则我不会仅仅为了节省汇编指令或处理器周期而扰乱我的源代码。

Answer 5

使用 (i<<3)+(i<<1) 乘以 10 实际上比直接使用 i*10 更快吗？

它可能在也可能不在您的机器上 - 如果您关心的话，请根据您的实际使用情况进行测量。

案例研究 - 从 486 到酷睿 i7 基准

测试很难进行有意义的测试，但我们可以看一些事实。来自http://www.penguin.cz/~literakl/intel/s.html#SAL和<一个href="http://www.penguin.cz/~literakl/intel/i.html#IMUL">http://www.penguin.cz/~literakl/intel/i.html#IMUL 我们了解算术移位和乘法所需的 x86 时钟周期。假设我们坚持使用“486”（列出的最新的）、32 位寄存器和立即数，IMUL 需要 13-42 个周期，IDIV 44。每个 SAL 需要 2，然后加 1，所以即使其中一些一起移位，表面上看起来也会发生变化。就像赢家一样。

如今，使用核心 i7：（

来自 http://software.intel.com/ en-us/forums/showthread.php?t=61481)

整数加法的延迟为 1 个周期，整数乘法的延迟为 3 个周期。您可以在“英特尔® 64 和 IA-32 架构优化参考手册”的附录 C 中找到延迟和吞吐量，该手册位于 http://www.intel.com/products/processor/manuals/。

（来自一些英特尔简介）

使用 SSE，Core i7 可以同时发出加法和乘法指令，从而实现每个时钟周期 8 次浮点运算 (FLOP) 的峰值速率

这让您了解事情已经取得了多大进展。优化琐事（例如位移与 *）甚至在 90 年代就被认真对待，但现在已经过时了。位移仍然更快，但对于非 2 乘方/除法，当您完成所有移位并添加结果时，它又变慢了。然后，更多的指令意味着更多的缓存故障、更多的流水线潜在问题、更多地使用临时寄存器可能意味着更多地从堆栈中保存和恢复寄存器内容……它很快就会变得太复杂，无法明确量化所有影响，但它们是主要是负面的。

源代码中的功能与实现

更一般地说，您的问题被标记为 C 和 C++。作为第三代语言，它们专门设计用于隐藏底层 CPU 指令集的细节。为了满足他们的语言标准，他们必须支持乘法和移位操作（以及许多其他操作）即使底层硬件不支持。在这种情况下，他们必须使用许多其他指令来综合所需的结果。同样，如果 CPU 缺乏浮点运算并且没有 FPU，它们也必须提供对浮点运算的软件支持。现代 CPU 都支持 * 和 <<，因此这可能看起来荒谬的理论和历史，但重要的是选择实现的自由是双向的：甚至如果 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...............

像exclusive or (xor) 这样的指令与源代码没有关系，但是与自身进行异或运算会清除所有位，因此它可以用于设置某些内容到 0。暗示内存地址的源代码可能不需要任何使用。

自从计算机出现以来，此类黑客技术就一直被使用。在 3GL 的早期，为了确保开发人员采用，编译器输出必须满足现有的硬核手动优化汇编语言开发。社区认为生成的代码并没有更慢、更冗长或更糟糕。编译器很快采用了许多伟大的优化 - 它们成为比任何单独的汇编语言程序员更好的集中存储，尽管它们总是有可能错过在特定情况下恰好至关重要的特定优化 - 人类有时可以胡言乱语，摸索出更好的东西，而编译器只是按照他们被告知的去做，直到有人将经验反馈给他们。

因此，即使移位和添加在某些特定硬件上仍然更快，那么编译器编写者很可能已经准确地计算出何时既安全又有益。

可维护性

如果您的硬件发生变化，您可以重新编译，它会查看目标 CPU 并做出另一个最佳选择，而您不太可能想要重新访问您的“优化”或列出哪些编译环境应该使用乘法，哪些应该改变。想想 10 多年前编写的所有非二次方位移“优化”，现在它们在现代处理器上运行时正在减慢它们所在的代码......！

值得庆幸的是，当启用任何优化时，像 GCC 这样的优秀编译器通常可以用直接乘法替换一系列位移和算术（即 ...main(...) { return (argc << 4) + ( argc << 2) + argc; } -> imull $21, 8(%ebp), %eax) 因此重新编译可能会有所帮助修复代码，但这并不能保证。

实现乘法或除法的奇怪位移代码远不能表达您在概念上试图实现的目标，因此其他开发人员会对此感到困惑，而困惑的程序员更有可能引入错误或删除一些重要的内容，以努力恢复看似理智的状态。如果你只在真正有实际好处的时候做一些不明显的事情，然后很好地记录它们（但不要记录其他直观的东西），每个人都会更高兴。

通用解决方案与部分解决方案

如果您有一些额外的知识，例如您的 int 实际上只会存储值 x、y 和 z，那么您也许能够制定出一些适用于这些值的指令，并比编译器没有这种洞察力并需要适用于所有 的实现更快地获得结果int 值。例如，考虑您的问题：

可以使用位运算符来实现乘法和除法...

您说明了乘法，但是除法怎么样？

int x;
x >> 1;   // divide by 2?

根据 C++ 标准 5.8：

-3-E1的值>> E2是E1右移E2位的位置。如果 E1 具有无符号类型，或者 E1 具有有符号类型和非负值，则结果值是 E1 的商除以 2 的 E2 次方的商的整数部分。如果 E1 具有有符号类型和负值，则结果值是实现定义的。

因此，当x为负数时，您的位移位具有实现定义的结果：它在不同机器上的工作方式可能不同。但是，/ 的工作方式更加可预测。（它也可能不完全一致，因为不同的机器可能有不同的负数表示，因此范围也不同即使组成表示的位数相同。）

您可能会说“我不在乎... int 正在存储员工的年龄，它永远不会是负数” 。如果您有这种特殊的洞察力，那么是的 - 您的 >> 安全优化可能会被编译器忽略，除非您在代码中明确执行此操作。但是，这是有风险的，而且很少有用，因为很多时候你不会有这种洞察力，而其他处理相同代码的程序员不会知道你已经把赌注押在了某些东西上。对您将要处理的数据的不寻常的期望...对它们来说看似完全安全的更改可能会因为您的“优化”而适得其反。

是否有任何类型的输入不能以这种方式相乘或除法？

是的......如上所述，负数在被位移“除”时具有实现定义的行为。

Answer 6

刚刚在我的机器上尝试编译这个：

int a = ...;
int b = a * 10;

当反汇编时，它会产生输出：

MOV EAX,DWORD PTR SS:[ESP+1C] ; Move a into EAX
LEA EAX,DWORD PTR DS:[EAX+EAX*4] ; Multiply by 5 without shift !
SHL EAX, 1 ; Multiply by 2 using shift

这个版本比您手动优化的纯移位和加法代码更快。

你真的永远不知道编译器会产生什么，所以最好简单地编写一个正常乘法并让他按照他想要的方式进行优化，除非在非常精确的情况下知道编译器无法优化。

Answer 7

在指令级别，移位通常比乘法快得多，但您很可能会浪费时间进行过早的优化。编译器可以在编译时很好地执行这些优化。自己做会影响可读性，并且可能对性能没有影响。如果您已经分析并发现这是一个瓶颈，那么这样做可能才值得。

实际上，被称为“魔法除法”的除法技巧实际上可以产生巨大的回报。同样，您应该首先进行分析，看看是否需要。但是，如果您确实使用它，那么周围有一些有用的程序可以帮助您弄清楚相同的除法语义需要哪些指令。这是一个示例：http://www.masm32.com/board/index。 php?topic=12421.0

我从 MASM32 上的 OP 线程中提取的示例：

include ConstDiv.inc
...
mov eax,9999999
; divide eax by 100000
cdiv 100000
; edx = quotient

将生成：

mov eax,9999999
mov edx,0A7C5AC47h
add eax,1
.if !CARRY?
    mul edx
.endif
shr edx,16

Answer 8

移位和整数乘法指​​令在大多数现代 CPU 上具有相似的性能 - 整数乘法指​​令在 20 世纪 80 年代相对较慢，但通常情况已不再如此。整数乘法指​​令可能具有较高的延迟，因此仍然可能存在移位更可取的情况。对于可以让更多执行单元忙碌的情况也是如此（尽管这可能是双向的）。

不过，整数除法仍然相对较慢，因此使用移位而不是除以 2 的幂仍然是一种胜利，并且大多数编译器都会将其实现为优化。 但请注意，要使此优化有效，股息必须是无符号的或必须已知为正数。对于负被除数，移位和除法并不等价！

#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;
}

输出：

5 / 2 = 2, 5 >> 1 = 2
4 / 2 = 2, 4 >> 1 = 2
3 / 2 = 1, 3 >> 1 = 1
2 / 2 = 1, 2 >> 1 = 1
1 / 2 = 0, 1 >> 1 = 0
0 / 2 = 0, 0 >> 1 = 0
-1 / 2 = 0, -1 >> 1 = -1
-2 / 2 = -1, -2 >> 1 = -1
-3 / 2 = -1, -3 >> 1 = -2
-4 / 2 = -2, -4 >> 1 = -2
-5 / 2 = -2, -5 >> 1 = -3

因此，如果您想帮助编译器，请确保被除数中的变量或表达式显式无符号。

Answer 9

它完全取决于目标设备、语言、用途等。

视频卡驱动程序中的像素处理？很有可能，是的！

.NET 业务应用程序适合您的部门吗？绝对没有理由去研究它。

对于移动设备的高性能游戏来说，这可能值得研究，但前提是进行了更简单的优化。

Answer 10

除非您绝对需要并且您的代码意图需要移位而不是乘法/除法，否则不要这样做。

在典型的一天中 - 您可能会节省几个机器周期（或宽松，因为编译器更好地知道要优化什么），但成本不值得 - 您将时间花在次要细节上而不是实际工作上，维护代码变得更加困难并且你的同事会咒骂你。

您可能需要为高负载计算执行此操作，其中每个保存的周期意味着运行时间的分钟数。但是，您应该一次优化一个地方，并每次都进行性能测试，看看是否真的让它变得更快或破坏了编译器逻辑。

Answer 11

据我所知，在某些机器上，乘法可能需要多达 16 到 32 个机器周期。所以是的，根据机器类型，位移运算符比乘法/除法更快。

然而，某些机器确实有数学处理器，其中包含乘法/除法的特殊指令。

Answer 12

在有符号整数和右移与除法的情况下，它可以产生影响。对于负数，移位向负无穷大舍入，而除法向零舍入。当然，编译器会将除法更改为更便宜的东西，但它通常会将其更改为与除法具有相同舍入行为的东西，因为它要么无法证明变量不会为负数，要么根本就不会关心。
因此，如果您可以证明一个数字不会为负数，或者您不关心它的舍入方式，那么您可以以更有可能产生影响的方式进行优化。

Answer 13

我同意德鲁·霍尔的标记答案。不过，答案可能需要一些额外的注释。

对于绝大多数软件开发人员来说，处理器和编译器不再与问题相关。我们大多数人都远远超出了 8088 和 MS-DOS。它可能只与那些仍在开发嵌入式处理器的人相关......

在我的软件公司，数学（加/减/乘/除）应该用于所有数学。
而在数据类型之间转换时应使用 Shift，例如。 ushort 为字节，如 n>>8 而不是 n/256。

Answer 14

Python 测试对相同的随机数执行 1 亿次相同的乘法。

>>> from timeit import timeit
>>> setup_str = 'import scipy; from scipy import random; scipy.random.seed(0)'
>>> N = 10*1000*1000
>>> timeit('x=random.randint(65536);', setup=setup_str, number=N)
1.894096851348877 # Time from generating the random #s and no opperati

>>> timeit('x=random.randint(65536); x*2', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); x << 1', setup=setup_str, number=N)
2.2616429328918457

>>> timeit('x=random.randint(65536); x*10', setup=setup_str, number=N)
2.2799630165100098
>>> timeit('x=random.randint(65536); (x << 3) + (x<<1)', setup=setup_str, number=N)
2.9485139846801758

>>> timeit('x=random.randint(65536); x // 2', setup=setup_str, number=N)
2.490908145904541
>>> timeit('x=random.randint(65536); x / 2', setup=setup_str, number=N)
2.4757170677185059
>>> timeit('x=random.randint(65536); x >> 1', setup=setup_str, number=N)
2.2316000461578369

因此，在 python 中进行移位而不是乘以 2 的幂时，有轻微的改进（除法约为 10%；乘法约为 1%）。如果它不是 2 的幂，则可能会出现相当大的减速。

同样，这些 # 会根据您的处理器、编译器（或解释器——为了简单起见，在 python 中执行）而改变。

与其他人一样，不要过早优化。编写非常可读的代码，分析其速度是否不够快，然后尝试优化缓慢的部分。请记住，您的编译器在优化方面比您要好得多。

Answer 15

有些优化是编译器无法执行的，因为它们仅适用于减少的输入集。

下面是 C++ 示例代码，可以通过 64 位“倒数乘法”进行更快的除法。分子和分母都必须低于某个阈值。请注意，必须将其编译为使用 64 位指令，才能真正比普通除法更快。

#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;
}

Answer 16

我认为在一种情况下，您想要乘以或除以 2 的幂，使用位移运算符不会出错，即使编译器将它们转换为 MUL/DIV，因为某些处理器微代码（实际上，宏）无论如何，所以对于这些情况，您将实现改进，特别是如果移位大于 1。或者更明确地说，如果 CPU 没有位移运算符，那么无论如何它都将是 MUL/DIV，但如果 CPU 有位移位运算符，您可以避免微代码分支，这少了一些指令。

我现在正在编写一些代码，需要大量的加倍/减半操作，因为它正在处理密集的二叉树，并且我怀疑还有一个操作可能比加法更优化 - 左（两个乘法的幂） ) 通过加法进行移位。如果移位比要添加的位数更宽，则可以用左移和异或来替换，简单的示例是 (i<<1)^1，它将 1 添加到双倍值。这当然不适用于右移（二除法的幂），因为只有左移（小端）才能用零填充间隙。

在我的代码中，这些乘/除二和二次幂运算被非常频繁地使用，并且由于公式已经很短，因此可以消除的每条指令都可以带来巨大的收益。如果处理器不支持这些位移运算符，则不会产生增益，但也不会产生损失。

此外，在我正在编写的算法中，它们直观地表示了发生的运动，因此从这个意义上说，它们实际上更清晰。二叉树的左侧较大，右侧较小。除此之外，在我的代码中，奇数和偶数具有特殊的意义，树中的所有左手孩子都是奇数，所有右手孩子和根都是偶数。在某些情况下，我还没有遇到过，但是可能，哦，实际上，我什至没有想到这一点，与x%2相比，x&1可能是一个更优化的操作。 x&1 在偶数上将产生 0，但在奇数上将产生 1。

比奇数/偶数识别更进一步，如果 x&3 的结果为零，我就知道 4 是我们数字的因数，对于 8 的 x%7 也是如此，依此类推。我知道这些情况的实用性可能有限，但很高兴知道您可以避免模数运算并改用按位逻辑运算，因为按位运算几乎总是最快的，并且最不可能对编译器产生歧义。

我几乎发明了密集二叉树领域，所以我预计人们可能无法理解这个评论的价值，因为很少有人只想只对二的幂进行因式分解，或者只对二的幂进行乘法/除法。

Answer 17

它是否实际上更快取决于实际使用的硬件和编译器。

Answer 18

如果您在 gcc 编译器上比较 x+x 、 x*2 和 x<<1 语法的输出，那么您将在 x86 程序集中得到相同的结果： https://godbolt.org/z/JLpp0j

        push    rbp
        mov     rbp, rsp
        mov     DWORD PTR [rbp-4], edi
        mov     eax, DWORD PTR [rbp-4]
        add     eax, eax
        pop     rbp
        ret

所以你可以认为 gcc 足够聪明，足以确定自己的最佳状态解决方案独立于您输入的内容。

Answer 19

我也想看看我是否能击败众议院。这是任意数乘任意数的更通用的按位运算。我制作的宏比普通 * 乘法慢大约 25% 到两倍。正如其他人所说，如果它接近 2 的倍数或由几个 2 的倍数组成，您可能会获胜。像由 (X<<4)+(X<<2)+(X<<1)+X 组成的 X*23 会比由 (X<<6) 组成的 X*65 慢)+X。

#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;
}