提取 ASCII 整数的前 32 位

Question

您有一个表示 128 位无符号整数 n 的 ASCII 字符串，即 0 <= n < 2^128。

给出一个算法来提取 n 的二进制表示的最高有效 32 位，并将它们作为它们编码的无符号 32 位整数返回。

有什么快速的方法可以做到这一点，即比实现自己的大数除法和模 2 运算更好的方法。 假设是 32 位机器，即没有 64 位内置类型。

示例： 为了简洁起见，我们采用 4 位整数并提取前 2 位：

2(0010) --> 0(00) 7(0111) --> 1(01) 8（1000） --> 2(10) 13(1101) --> 3(11)

这不是一个家庭作业问题。更新我的面试算法技能。

Answer 1

我没有看到比简单地模拟（有限形式）128 位算术更有效的方法。

假设我们有一个函数 mul10add(a, b)，它计算 10*a + b 并返回结果的低 32 位以及进位值。如果我们有 64 位算术，它可以实现为（以伪代码）：

(word32, word32) mul10add(word32 a, word32 b):
    word64 result = 10*a + b
    word32 carry  = result >> 32
    return (result, carry)

现在，我们采用正常的十进制到二进制算法并用四个 32- 表示 128 位数字 n位字 x、y、z 和 w 使得 n = x*2^96 + y*2^64 + z*2^32 + w。然后，我们可以将对 mul10add 的调用链接在一起，以执行 n = 10*n + digitalToInt(decimal[i]) 的等效操作。

word32 high32bits(string decimal):
    word32 x = 0, y = 0, z = 0, w = 0

    # carry
    word32 c = 0

    for i in 0..length(decimal)-1
       (w, c) = mul10add(w, digitToInt(decimal[i]))
       (z, c) = mul10add(z, c)
       (y, c) = mul10add(y, c)
       (x, _) = mul10add(x, c)

    return x

然而，我们实际上并不需要 64 位架构来实现 mul10add。在 x86 上，我们有 mul 指令，它将两个 32 位数字相乘，得到一个 64 位数字，其中高 32 位存储在 edx 中，低 32 位存储在 中>eax。还有 adc 指令，它将两个数字相加，但包含先前 add 中的进位。因此，在伪汇编中：

(word32, word32) mul10add(word32 a, word32 b):
    word32 result, carry
    asm:
        mov a, %eax
        mul 10
        add b, %eax
        adc 0, %edx
        mov %eax, result
        mov %edx, carry
    return (result, carry)