考虑以下现代Intel或AMD x86_64硬件上的C代码，其中数据类型int具有32 bits：

// calc x times y for any two integers values of x and y (where the result can be stored by the int datatype)
int fastMult(int x, int y) {
    /*
     * Assuming the following operators take O(n) or O(1) time:
     * ==, <, >, &&, ||, &, |, >>, -, +, ?:
     */

    // x*0 == 0*y == 0
    if (y == 0 || x == 0) return 0;

    // (-x)(-y) == xn and (-x)y == x(-y)
    if (x < 0) return fastMult(-x, -y);

    int isNegative = y < 0; // x cannot be negative here

    // y*x is faster than x*y for bigger absolute y than x
    if (isNegative && x < -y || x < y) return fastMult(y, x);
    if (isNegative) y = -y; // handle y in a simpler way

    int res = fastMult(x, y >> 1); // called at max lb(y) times aka sizeof(y) times
    res = res + res; // one addition
    if (y & 1) res = x + res; // possible second addition

    // if y was negative, then the answer is negative
    return isNegative ? -res : res;
}

如果我们忽略递归步骤，除了if的分支操作外，这段代码中最慢的操作就是+操作。CPU仍然可以在一个时钟周期内执行此操作。因此，即使两个32 bit整数相加在硬件上基本上需要O(1)时间，对于bigint操作，我们仍然应该称之为O(n)，其中bigint是具有n-bits的int。
话虽如此，用于递归实现两个数相乘的base case在y == 0处停止。（除了当它可能切换x和y并改变一些符号的第一次之外）在最大32 times处，因为它用参数y将自己称为y >> 1，该操作将位向左移1，直到所有位都为0，对于32 bit int，最大值为y >> 32。
这是否意味着它是一个用于将两个整数相乘的O(n log n)算法（因为它也适用于具有相同时间复杂度的bigints）？
为什么是O(n log n)？当调用这个函数时，我们要进行多次O(1)和O(n)计算。因为我们调用这个函数最多O(log n)次，所以我们用O(log n)乘以O(n)，得到O(n log n)。至少这是我对这个的理解。

我不确定，因为所有常用的两个整数相乘的方法都需要O(n*n)步，只有很少的复杂算法比这更快，请参见：https://www.wikiwand.com/en/Multiplication_algorithm

此代码用于无符号整数的更简单版本：

// x * y for unsigned integers of x and y
int fastMult(int x, int y) {
    if (y == 0) return 0;

    int res = fastMult(x, y >> 1);
    res <<= 1; // O(1) or O(n), doesnt matter since O(n) is below this line and 2 times O(n) is still O(n)
    if (y & 1) res += x; // O(n)

    return res;
}