提取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位字x, y, z和w表示128位的数字n，这样n = x*2^96 + y*2^64 + z*2^32 + w。然后，可以将对mul10add的调用串在一起，以执行与n = 10*n + digitToInt(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中，下面的存储在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)