示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载type-challenges 仓库的questions/32532-hard-binary-addition是一道hard 难度的类型编程题目要求你纯粹在类型层面实现一个BinaryAdd类型工具接收两个等长的二进制位数组输出它们相加后的二进制位数组并且全程不得把二进制数翻译成十进制或普通数字字面量。读完本文你将掌握位数组 递归 进位这套类型级加法器的完整推导过程并能逐条对照仓库自带的测试用例验证自己的实现。题目速览要求与输入约束题目位于 questions/32532-hard-binary-addition/README.md原始需求只有两句话ImplementBinaryAddto add two binary numbers together. The numbers should not be translated out of binary at any point. Note the two inputs will always have the same length.翻译过来是实现BinaryAdd将两个二进制数相加在任何时刻都不能把二进制数转换为二进制以外的表示例如十进制数字、字符串数字两个输入数组长度一定相等实现时无需处理长度不一致的情况。该题由 Finley GartonGitHub 用户finleygn贡献。从 info.yml 可以确认它的元数据字段值difficultyhardtitleBinary Additiontagsrecursion, array「递归」与「数组」两个标签基本预告了解法的主线BinaryAdd必须是递归条件类型且运算载体是元组数组类型。起点模板与测试用例仓库为本题提供了两个关键文件。起点模板 template.ts 定义了类型边界type Bit 1 | 0 type BinaryAddA extends Bit[], B extends Bit[] anyBit限定为1 | 0即单个二进制位BinaryAdd接收两个Bit[]元组返回类型待实现当前为any占位。验证集在 test-cases.ts 中共 5 个用例全部使用type-challenges/utils提供的Equal与Expect做严格类型相等断言#输入 A输入 B期望输出1[1][1][1, 0]2[0][1][1]3[1, 1, 0][0, 0, 1][1, 1, 1]413 个113 个114 位[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]5[1, 0, 1, 0, 1, 1, 1, 0][1, 0, 0, 0, 1, 1, 0, 0][1, 0, 0, 1, 1, 1, 0, 1, 0]第 1 个用例是最经典的1 1 10二进制进位第 4 个用例用 13 个1相加验证链式进位传播第 5 个用例验证结果比输入多出一位发生最高位进位溢出。这些用例共同覆盖了无进位、单次进位、进位链、最高位溢出四种场景。核心约束为什么不许转出二进制是难点类型体操解题者最熟悉的捷径是把二进制数转成十进制再运算。仓库里恰好有一道姊妹题 06141-hard-binary-to-decimal它的任务是把10、11111111这样的二进制字符串转成十进制数字字面量如2、255其测试用例见 test-cases.ts。也就是说转出二进制在类型世界里是完全可行的——你可以借助[length]计数、字符串模板拼接等手段把位数组变成一个数字做数字加法再转回来。而本题目把这条路封死了The numbers should not be translated out of binaryat any point在任何时刻都不得翻译出二进制。这意味着你不能把[1, 0, 1]变成数字5或字符串101后再做运算所有运算必须始终停留在Bit[]这个位数组域内完成唯一的运算原语只能是位 位以及进位传播。这正是递归标签的真正含义加法必须被建模为逐位递归的进位加法而不是数值算术。理解了这一约束解法方向就自然浮现了——我们需要的是一台运行在类型系统里的全加器。前置知识位数组表示与全加器真值表在数字电路里两个二进制位相加会产生两个输出本位和sum与进位carry。一个完整的一位加法器全加器Full Adder还要吞入来自低位的进位Cin其真值表如下ABCinSumCout0000000110010100110110010101011100111111规律很好记三个输入里1 的个数为偶数 → Sum 0为奇数 → Sum 11 的个数 ≥ 2 → Cout 1否则 Cout 0。而本题的两个输入是Bit[]元组例如[1, 0, 1, 0, 1, 1, 1, 0]表示二进制数10101110下标越靠左越高位。要把这样两个元组相加我们只需要从**最低位数组尾部**开始逐位套用全加器把当前位的进位Cout传给下一位作为Cin若最后仍有进位在结果头部追加一个1。解法设计递归进位加法三步走因为元组类型只能从头部[Head, ...Tail]或尾部[...Init, Last]解构而二进制加法必须从最低位开始所以最直观的做法是先把数组反转从低位一路算到高位最后再把结果反转回来。整个实现分成三个纯类型工具分工清晰、可单独测试。第一步反转数组Reversetype ReverseT extends Bit[] T extends [...infer R extends Bit[], infer L extends Bit] ? [L, ...ReverseR] : []利用[...infer R, infer L]把除最后一个元素外的部分和最后一个元素分开把L挪到头部后递归处理剩余部分。例如Reverse[1, 0, 1]会得到[1, 0, 1]的反向[1, 0, 1]的反转[1, 0, 1]——实际上Reverse[1, 0, 1] [1, 0, 1]回文而Reverse[1, 1, 0] [0, 1, 1]最低位0被挪到了头部方便逐位消费。第二步三比特求和器SumBitSumBitA, B, C接收当前位A、B和来自低位的进位C返回[Sum, Cout]二元组。用穷举条件类型直接把上文的真值表翻译成代码零推导、零歧义type SumBitA extends Bit, B extends Bit, C extends Bit [A, B, C] extends [0, 0, 0] ? [0, 0] : [A, B, C] extends [0, 0, 1] ? [1, 0] : [A, B, C] extends [0, 1, 0] ? [1, 0] : [A, B, C] extends [1, 0, 0] ? [1, 0] : [A, B, C] extends [0, 1, 1] ? [0, 1] : [A, B, C] extends [1, 0, 1] ? [0, 1] : [A, B, C] extends [1, 1, 0] ? [0, 1] : [1, 1]注意这里把三元组[A, B, C]当作整体参与匹配因此不会触发联合类型的分发distributive行为当A、B、C都是确定的字面量1 | 0时这个穷举链必然命中且只命中一行。第三步递归逐位相加AddRev与入口BinaryAddtype AddRevA extends Bit[], B extends Bit[], C extends Bit A extends [infer HA extends Bit, ...infer TA extends Bit[]] ? B extends [infer HB extends Bit, ...infer TB extends Bit[]] ? SumBitHA, HB, C extends [infer S extends Bit, infer NC extends Bit] ? [S, ...AddRevTA, TB, NC] : never : never : C extends 1 ? [1] : [] type BinaryAddA extends Bit[], B extends Bit[] ReverseAddRevReverseA, ReverseB, 0AddRev的递归逻辑同时从两个反转后的数组头部取出当前位HA、HB连同进位C交给SumBit把算出的本位S放入结果头部进位NC作为下一轮递归的Cin当两个数组都被消费完时若还有残留进位C 1则返回[1]否则返回空元组[]——这一步对应最高位溢出第 4、5 号用例的 14 位 / 9 位结果入口BinaryAdd先反转输入、以0作为初始进位调用AddRev最后把结果再反转回高位在前的正常顺序。由于题目保证输入等长递归中A、B会同步耗尽不存在长度不一致分支。完整可运行实现把以下代码整体替换进 template.ts 即可通过全部测试type Bit 1 | 0 type ReverseT extends Bit[] T extends [...infer R extends Bit[], infer L extends Bit] ? [L, ...ReverseR] : [] type SumBitA extends Bit, B extends Bit, C extends Bit [A, B, C] extends [0, 0, 0] ? [0, 0] : [A, B, C] extends [0, 0, 1] ? [1, 0] : [A, B, C] extends [0, 1, 0] ? [1, 0] : [A, B, C] extends [1, 0, 0] ? [1, 0] : [A, B, C] extends [0, 1, 1] ? [0, 1] : [A, B, C] extends [1, 0, 1] ? [0, 1] : [A, B, C] extends [1, 1, 0] ? [0, 1] : [1, 1] type AddRevA extends Bit[], B extends Bit[], C extends Bit A extends [infer HA extends Bit, ...infer TA extends Bit[]] ? B extends [infer HB extends Bit, ...infer TB extends Bit[]] ? SumBitHA, HB, C extends [infer S extends Bit, infer NC extends Bit] ? [S, ...AddRevTA, TB, NC] : never : never : C extends 1 ? [1] : [] type BinaryAddA extends Bit[], B extends Bit[] ReverseAddRevReverseA, ReverseB, 0用仓库测试用例逐步验证下面把 test-cases.ts 的 5 个用例逐一走一遍确认实现行为与断言一致。用例 1BinaryAdd[1], [1]→[1, 0]反转后两边都是[1]AddRev[1], [1], 0SumBit1, 1, 0 [0, 1]本位0入结果进位1进入空数组分支返回[1]拼接得[0, 1]再反转得[1, 0]。与期望完全一致1 1 10。用例 2BinaryAdd[0], [1]→[1]SumBit0, 1, 0 [1, 0]无残留进位结果为[1]。✅用例 3BinaryAdd[1, 1, 0], [0, 0, 1]→[1, 1, 1]反转A 得[0, 1, 1]B 得[1, 0, 0]第 1 位原最低位0 1 0 1进位0第 2 位1 0 0 1进位0第 3 位1 0 0 1进位0反转结果[1, 1, 1]。✅用例 413 个1加 13 个1→ 14 位结果从最低位开始连续 13 次1 1每一位都是Sum 0, Cout 1进位像多米诺骨牌一样逐位传递最终溢出补出第 14 位[1, 0, 0, ...]反转后得到[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0]。这正是进位链用例验证了递归的终止条件C extends 1 ? [1] : []被正确触发。✅用例 510101110 10001100→[1, 0, 0, 1, 1, 1, 0, 1, 0]两个 8 位输入相加得 9 位结果10101110十进制 17410001100十进制 140100111010十进制 314。注意这里我们只是用十进制做交叉验算类型实现本身全程没有把二进制转出。✅五个用例全部命中说明反转 全加器 递归进位的骨架同时正确处理了无进位、单进位、进位链与最高位溢出四类情况。纵深本题在仓库类型体操地图中的位置把BinaryAdd放进整个 type-challenges 仓库的上下文中可以更清楚地看到它的设计意图。与BinaryToDecimal的对照关系。06141-hard-binary-to-decimal 训练的是二进制字符串 → 十进制数字的转换能力而本题刻意反向禁止这种转换强制你在位数组域内完成运算。两题一正一反正好把类型系统内的进制运算这个主题练全先学会转出去再学会不转出去也能算。与Sum大数加法的方法论一脉相承。00476-extreme-sum 要求实现SumA, B把任意大的十进制字符串相加测试覆盖了bigint、千亿级大数与进位见其 test-cases.ts。虽然载体从Bit[]换成了十进制字符但逐位求和 进位传递 递归的核心算法与BinaryAdd完全相同——先学会二进制版本的加法器再迁移到十进制大数加法复杂度只会来自字符映射而非算法骨架。与递归指南的呼应。仓库根目录的 guides/recursive.md 是专门为递归类题目准备的专题指南目前文件内仍标注为TODO:占位尚未填充正文。从源码结构看#recursion是题库中一个独立标签维度而BinaryAdd是其中最典型的状态穿越递归案例进位C作为递归参数在调用栈中流动这是理解所有带状态递归如Sum、FibonacciSequence、FizzBuzz的关键心智模型。边界与扩展思考递归深度。本实现每一次BinaryAdd求值大约产生 3 层嵌套递归调用链两次Reverse各约n层AddRev约n层合计约3n层。TypeScript 编译器对类型实例化有默认深度限制约 1000 层因此对300 位以内的二进制数都安全超出后可用// ts-expect-error之外的方案优化例如改用字符串模板替代元组反转以减少中间类型。仓库 13 位用例远在安全区无需担心。等长输入假设。题目明确two inputs will always have the same length因此AddRev中A、B同步耗尽。若自行扩展该工具需要补一个对齐分支——但那是超纲需求不在本题目测试范围内。另一种思路正向高位递归。也有社区方案尝试从高位向低位递归但高位加法需要知道低位是否产生进位这一信息在纯类型递归里无法提前获得通常要引入Reverse或先补零再递归的技巧实现更绕。反转法把从低位算起这一算法意图直接翻译成了类型代码可读性与正确性都更优。小结BinaryAdd是一道把数字电路知识与类型递归缝合起来的 hard 题它用Bit[]元组模拟二进制寄存器用SumBit穷举全加器真值表用AddRev驱动进位传播再用Reverse完成方向对齐。全程没有出现任何十进制数字完美兑现了 should not be translated out of binary at any point 的约束。配合 test-cases.ts 的 5 个用例你可以放心地把上面的完整实现粘贴进 template.ts 并运行tsc验证——这既是类型体操的练习题也是一堂可运行的软硬件协同设计课。赞分享示例工程【免费下载链接】type-challengesCollection of TypeScript type challenges with online judge项目地址https://gitcode.com/GitHub_Trending/ty/type-challenges点击查看免费下载相关推荐TypeScript 类型体操用纯类型系统实现大数乘法 Multiplytype-challenges 517TypeScript 类型体操用纯类型系统实现大数乘法 Multiplytype challenges 517 导读 本指南围绕 type challen示例工程TypeScript 类型体操实战用 Transpose 类型实现矩阵转置type-challenges 25270TypeScript 类型体操实战用 Transpose 类型实现矩阵转置type challenges 25270 本篇文章以 type challen示例工程TypeScript 类型体操实战实现 Zip 元组拉链类型type-challenges 4471TypeScript 类型体操实战实现 Zip 元组拉链类型type challenges 4471 本篇指南以 questions/04471 medi示例工程上一篇解决90%的redux-persist问题开发者必备调试指南下一篇深入AngularEditor源码核心组件设计与实现原理剖析创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考