约 17 分钟9 张卡

整数运算

整数运算首先要区分数值和表示：数学上的整数没有固定上限，机器整数受位宽限制，十进制字符串则只保存一串数字字符。输入超过 uint64 时，把字符串转成浮点数再算，会把范围问题变成精度问题。可以使用大整数类型；需要自己实现时，则把运算拆到每个数字位。

算法题的重点也不只是算出一个值。需要说明进位和余数怎样传递，数字顺序能不能改变，结果是否必须严格小于上界，以及零、负数和越界怎样处理。这些约定直接决定实现。

1. 面试核心

先记住这几条，再读正文

整数的位宽、符号和语言规则共同决定运算结果；检查溢出应发生在危险运算之前，不能先溢出再比较。
整除与余数必须配套解释。Python 的整除向下取整，Go 的整数除法向零截断；对负数不能直接互换。卡 · 对二的幂求余
正整数是 2 的幂，当且仅当二进制只有一个 1；n > 0 与 n & (n-1) == 0 缺一不可。卡 · 判断二的幂
最大公约数满足 gcd(a,b)=gcd(b,a%b)，余数逐步缩小，直到除数为零。卡 · 最大公约数
大整数加乘把数值拆成数字位，每一步只处理当前数字和进位；长除法则从高位向低位维护余数。卡 · 十进制字符串加乘卡 · 长除法与小数位
十进制转二进制可以反复除以 2，倒序收集余数；输入是长字符串时，每次除法也要计入成本。卡 · 进制转换
受上界约束的数字构造要区分前缀相等和已经变小；数字是否可重复、能否有前导零、是否允许零，需要先约定。卡 · 受限数字构造
数位计数保存上界约束和数字是否开始；删除数字则保留原顺序，优先改善更高位。两类问题的状态与选择条件不同。卡 · 统计不含指定数字的整数卡 · 删除数字与顺序约束

2. 表示与输入约定

十进制字符串 "1203" 表示 1×10³ + 2×10² + 0×10 + 3。从左到右读一位 d，当前数值由 x 变为 10x+d；从右到左运算，则要把当前位超过 9 的部分进到左边。

本文的字符串算术使用非负十进制整数：字符只允许 ASCII 0 到 9，输入可以有前导零，输出统一去掉前导零，零写成 "0"。空串、符号、小数点和空格不在这个输入约定内。带符号的大整数需要另行管理符号，并补充绝对值比较、减法等操作。

规范化后，比较两个非负十进制字符串可以先比较长度；长度相等时，字典序就是数值顺序。不能直接用字典序比较不同长度的 "99" 和 "100"，也不能让前导零影响位数判断。

2.1 在运算前检查范围

假设要把非负数放进最大值为 M 的目标类型，已经读出的值为 x，准备接收数字 d。先确认 0 ≤ d ≤ M，再判断：

x <= (M-d) // 10

成立时才计算 10*x+d。这与检查 10*x+d <= M 数学等价，但后者可能在做比较前已经溢出。进制为 B 时，把 10 换成 B，且数字必须满足 0 ≤ d < B。

Python 的 int 可以随数值增长，不按固定机器字自动回绕，但仍受资源限制。Go 的机器整数则有固定范围。更完整的补码与语言差异见二进制数据表示。下面涉及大数的复杂度，以数字位数衡量；不能把任意长度整数的运算一律当成常数时间。

3. 商、余数与二进制位

卡 · 怎样求两个整数的最大公约数，零和负数怎样处理？卡 · 怎样判断一个整数是否为 2 的幂？卡 · 一个数对 1024 求余，可以直接用按位与吗？

对非负整数 a 和正整数 b，整除得到商 q 与余数 r，满足 a=q*b+r，且 0 ≤ r < b。这个关系既是长除法的不变量，也是进制转换和欧几里得算法的基础。

带负号时要看语言规则。Python 3.12 的 -5 // 3 是 -2，-5 % 3 是 1；Go 1.22 的 -5 / 3 是 -1，-5 % 3 是 -2。两者都保持商余关系，但选择的商不同。Go 最小有符号整数除以 -1 还有结果溢出的特例，不能用同位宽正数表示其数学结果。

3.1 对二的幂求余

对于非负整数，除以 2^k 的余数就是二进制低 k 位。因此，x % 1024 可以表示为 x & 1023，其中 1023 的低 10 位全是 1。

下面用 Go 展示适用条件：

package main

import "fmt"

func main() {
    for _, x := range []int64{1025, -1} {
        fmt.Println(x, x%1024, x&1023)
    }
}

输出为 1025 1 1 和 -1 -1 1023。负数的 Go 余数与低位掩码不同，不能直接替换。Python 对正除数使用向下取整，-1 % 1024 恰好是 1023，但这是另一套商余规则。

位运算写法也不保证实际程序更快。编译器可能已经把常量除法和求余优化为位运算；需要先保持语义，再讨论具体编译结果与性能。

3.2 判断二的幂

正整数 n 减 1，会把最低位的 1 变成 0，并把它右边的 0 变成 1。因此，n & (n-1) 会清掉最低位的一个 1；结果为零，说明原来只有这一个 1。

判断式是 n > 0 and (n & (n - 1)) == 0。零必须排除，1 则应接受，因为 1=2^0。在固定宽度机器整数上，这只需要固定次数的位运算；在任意精度整数上，处理成本还与表示长度有关。

3.3 最大公约数

最大公约数是同时整除两个整数的最大正整数。两者都是零时，没有最大的正公约数，本文按照 Python math.gcd 的接口约定返回零。欧几里得算法利用 a=q*b+r：能整除 a 和 b 的数，也能整除 r；能整除 b 和 r 的数，也能整除 a。因此，两组数的公约数集合相同。

def gcd(a: int, b: int) -> int:
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a


print(gcd(48, 18), gcd(-48, 18), gcd(0, 0))

输出 6 6 0。每次得到的非零余数都小于原除数，过程会终止。正数输入下，取余次数是对数级；大整数取余本身的成本仍需另算。Python 的 abs 不受固定字宽限制，移植到机器整数时，要特别处理最小负数无法在同一有符号类型中取正的情况。

4. 十进制字符串加乘

卡 · 不把整个输入转换成大整数，怎样实现十进制字符串乘法？

进位是当前位无法容纳、需要转到更高位的部分。十进制加法中，当前位总和除以 10 的余数留在本位，商传给下一位。例如 9+8+1=18，当前位写 8，进位为 1。

乘法可以照着竖式进行：一个数字与另一个数字相乘，再加上目标位已有值和进位。每一步都把目标位规范到 0—9，避免把大量乘积一直堆在同一机器整数里。

下面是可独立运行的 Python 3.12 程序。输入为两行非负十进制字符串，输出乘积；add_decimal 同时提供后续舍入需要的加一操作：

def canonical(text: str) -> str:
    if not text or any(c < "0" or c > "9" for c in text):
        raise ValueError("expected ASCII decimal digits")
    return text.lstrip("0") or "0"


def add_decimal(a: str, b: str) -> str:
    a, b = canonical(a), canonical(b)
    i, j, carry = len(a) - 1, len(b) - 1, 0
    result = []
    while i >= 0 or j >= 0 or carry:
        total = carry
        if i >= 0:
            total += ord(a[i]) - ord("0")
            i -= 1
        if j >= 0:
            total += ord(b[j]) - ord("0")
            j -= 1
        carry, digit = divmod(total, 10)
        result.append(chr(ord("0") + digit))
    return "".join(reversed(result))


def multiply_decimal(a: str, b: str) -> str:
    a, b = canonical(a), canonical(b)
    result = [0] * (len(a) + len(b))
    for i in range(len(a) - 1, -1, -1):
        carry = 0
        for j in range(len(b) - 1, -1, -1):
            k = i + j + 1
            total = result[k] + (ord(a[i]) - 48) * (ord(b[j]) - 48) + carry
            carry, result[k] = divmod(total, 10)
        result[i] = carry
    return "".join(chr(48 + d) for d in result).lstrip("0") or "0"


if __name__ == "__main__":
    a = input()
    b = input()
    print(multiply_decimal(a, b))

输入两行 00012、003，输出 36；add_decimal("999", "1") 返回 "1000"。程序没有把整个字符串转换成机器整数或 Python 大整数，只把单个 ASCII 字符转换为数字。

result[k] 和 carry 都不超过 9，单步 total 最大为 9+9×9+9=99。每轮内循环完成后，result[i] 是此前还没使用的更高位，可以直接写入剩余进位。长度分别为 m、n 的非零输入，竖式乘法需要 O(mn) 次数字运算、O(m+n) 额外空间；加法是 O(m+n)。这不代表所有大整数库都使用竖式乘法，库还可以按长度采用其他算法。

5. 长除法与小数位

卡 · 超过 uint64 的十进制字符串除以一个整数，怎样保留两位小数？

长除法从最高位开始处理，保留已经读过部分的余数。读到下一位 d 时，新的待除值是 10*remainder+d，它除以 divisor 的商就是当前商位。

因为此前 0 ≤ remainder < divisor，所以新商位一定在 0—9。以下函数复用上一节的 canonical：

def divide_small(text: str, divisor: int) -> tuple[str, int]:
    text = canonical(text)
    if divisor <= 0:
        raise ValueError("divisor must be positive")
    quotient = []
    remainder = 0
    for c in text:
        digit, remainder = divmod(remainder * 10 + ord(c) - 48, divisor)
        quotient.append(chr(48 + digit))
    return "".join(quotient).lstrip("0") or "0", remainder


def decimal_quotient(text: str, divisor: int, round_half_up: bool = False) -> str:
    whole, remainder = divide_small(text, divisor)
    fraction = []
    for _ in range(2):
        digit, remainder = divmod(remainder * 10, divisor)
        fraction.append(chr(48 + digit))
    scaled = whole + "".join(fraction)
    if round_half_up and 2 * remainder >= divisor:
        scaled = add_decimal(scaled, "1")
    scaled = scaled.zfill(3)
    return canonical(scaled[:-2]) + "." + scaled[-2:]


print(divide_small("43242", 4))
print(decimal_quotient("1", 8), decimal_quotient("1", 8, True))
print(decimal_quotient("1999", 2000, True))

输出依次是 ('10810', 2)、0.12 0.13、1.00。补小数位相当于在被除数末尾继续读入零；保留两位之后，余数表示还没输出的部分。若它至少达到 divisor 的一半，非负数的四舍五入需要给已经保留的数值加一，进位可能一直进入整数部分。

“保留两位小数”本身不足以决定算法。上面明确提供截断和非负数四舍五入两种方式，不涉及负数舍入、银行家舍入或无限循环小数的完整输出。必须根据题目或接口约定选择，不能先转成浮点数再依赖格式化碰巧得到正确结果。

若 divisor 在机器整数范围内，也不代表 remainder*10 一定安全。移植到固定宽度语言时，需要更宽的中间类型、受限的 divisor 范围，或能报告进位的多字运算。本例的中间整数由 Python 保存；在 divisor 位宽固定的模型下，处理 L 个输入位是 O(L)，结果空间也是 O(L)。

6. 进制转换

卡 · 怎样把十进制大数字符串转换成二进制字符串？

将非负整数除以 2，余数就是最低二进制位；对商继续除以 2，可以依次得到更高位。字符串输入超过机器整数范围时，重复使用长除法即可：

def decimal_to_binary(text: str) -> str:
    text = canonical(text)
    if text == "0":
        return "0"
    bits = []
    while text != "0":
        text, remainder = divide_small(text, 2)
        bits.append(str(remainder))
    return "".join(reversed(bits))


print(decimal_to_binary("00013"))
print(decimal_to_binary("0"))

输出 1101 和 0。13 依次除以 2 得到余数 1、0、1、1，它们是从低位到高位取出的，所以最后要反转。

若输入有 L 个十进制位、输出有 K 个二进制位，算法进行 K 次长除法，每次最多扫描 L 位，总时间上界 O(LK)。十进制与二进制位数成比例，因此这是 O(L²) 的简单转换方案，不能因为只看到一个 while 就说是线性时间。当前商和输出占 O(L+K) 空间。

7. 受限数字构造

卡 · 用给定数字构造严格小于 S 的最大整数，怎样处理回退？卡 · 怎样统计 1 到 n 中不含数字 4 和 7 的整数数量？

给定上界 S 和可用数字集合，构造严格小于 S 的最大整数，需要先确认：数字能否重复使用，是否必须使用全部数字，能否有前导零，是否允许零，以及无解怎样表示。

这里选择一个明确的版本：每个数字可重复使用，不要求全部使用；结果无前导零，但允许单独的零；无解返回 None。 输入上界是非负十进制字符串，数字集合是 0—9 中的整数。这些条件是参考实现的约定，不能从一句“用给定数字构造最大数”中自动推出来。

7.1 相等前缀与回退

同样位数的非负整数，先由最高不同位决定大小。只要已选前缀和 S 相同，下一位就不能超过 S 的对应位；一旦某位选得更小，后面全部填最大可用数字，就是这个前缀下的最大结果。

如果某位没有合法数字，或者最后拼出的数恰好等于 S，就向前回退：把最靠后的可降低数字换成更小的可用数字，再把后缀填满。越晚降低，保留的高位越大，所以优先从末尾回退。整个同长度方案失败后，再尝试少一位的最大数。

def max_below(bound: str, digits: set[int]) -> str | None:
    bound = canonical(bound)
    if any(type(d) is not int or not 0 <= d <= 9 for d in digits):
        raise ValueError("digits must be integers from 0 to 9")
    allowed = sorted(str(d) for d in digits)
    if not allowed or bound == "0":
        return None
    prefix = []
    for i, limit in enumerate(bound):
        choices = [d for d in allowed if d <= limit and (i > 0 or d != "0")]
        if not choices:
            break
        chosen = choices[-1]
        prefix.append(chosen)
        if chosen < limit:
            return "".join(prefix) + allowed[-1] * (len(bound) - i - 1)

    while prefix:
        i = len(prefix) - 1
        previous = prefix.pop()
        choices = [d for d in allowed if d < previous and (i > 0 or d != "0")]
        if choices:
            return "".join(prefix) + choices[-1] + allowed[-1] * (len(bound) - i - 1)

    nonzero = [d for d in allowed if d != "0"]
    if len(bound) > 1 and nonzero:
        return nonzero[-1] + allowed[-1] * (len(bound) - 2)
    return "0" if "0" in allowed else None


print(max_below("23256", {2, 3, 9}))
print(max_below("1200", {1, 2}))
print(max_below("1000", {0, 1}))

输出 23239、1122、111。第二个例子在第三位遇到无法匹配的 0，回退降低第二位；第三个例子无法找到同长度的合法结果，改用三位数。

数字集合最多 10 个，每一位只被前进、回退有限次，选择成本 O(10L)，即 O(L)，额外空间 O(L)。如果每个数字只能使用有限次，后缀不能随意填最大数字，需要维护剩余次数；上面的代码和证明不能直接套用。

7.2 统计不含指定数字的整数

要统计 [1,n] 中不含 4 和 7 的整数，逐个枚举可以作为小输入的核对方法，但 n 很大时，可以按位统计。数位动态规划保存已经选到哪一位，以及此前选择对后续造成的约束。

这个问题只需要两个状态：

tight：当前前缀是否仍等于 n 的前缀；为真时，下一位不能超过 n 的对应位。
started：是否已经选过第一个非零数字；为假时，当前零只是用来把短数字补到相同长度，不算实际数字的一部分。

下面按位更新状态数量，复用 canonical：

def count_without_4_7(bound: str) -> int:
    bound = canonical(bound)
    states = {(True, False): 1}
    for c in bound:
        limit = ord(c) - 48
        next_states = {}
        for (tight, started), ways in states.items():
            for digit in range((limit if tight else 9) + 1):
                new_started = started or digit != 0
                if new_started and digit in (4, 7):
                    continue
                key = (tight and digit == limit, new_started)
                next_states[key] = next_states.get(key, 0) + ways
        states = next_states
    return sum(ways for (_, started), ways in states.items() if started)


print(count_without_4_7("20"))
print(count_without_4_7("0"))

输出 16 和 0。全程都没开始的路径代表数字零，最后排除，才能得到 [1,n] 而不是 [0,n] 的数量。不同前缀只要剩余约束相同，就可以合并计数；动态规划的状态设计原则见动态规划。

每位至多 4 个状态、每个状态至多 10 种选择，转移次数是 O(L)。计数结果可能很大，若计算实际位运算成本，还要计入大整数加法；不能把“常数个状态”说成无限大的结果只占常数个字节。

8. 删除数字与顺序约束

卡 · 从数字序列删除 k 位，怎样让剩余数最大？

从一个数字序列中删除 k 位，剩余顺序必须保持不变。目标是得到最大的剩余数，所以遇到更大的新数字时，可以优先删除它前面较小的数字，把大数字放到更高位。

栈保存当前保留的前缀。只要还有删除额度，且栈顶小于新数字，就弹出栈顶；扫描完成后仍有额度，则从末尾删除。新数字相等时不必删除前面的相同数字，应把额度留给后续更有用的位置。

def max_after_removals(text: str, k: int) -> str:
    if not text or any(c < "0" or c > "9" for c in text):
        raise ValueError("expected ASCII decimal digits")
    if not 0 <= k <= len(text):
        raise ValueError("invalid deletion count")
    stack = []
    remaining = k
    for digit in text:
        while remaining and stack and stack[-1] < digit:
            stack.pop()
            remaining -= 1
        stack.append(digit)
    if remaining:
        del stack[-remaining:]
    return "".join(stack).lstrip("0") or "0"


print(max_after_removals("31452", 2))
print(max_after_removals("987", 1))
print(max_after_removals("001", 1))