LeetCode-Book 位运算专题LCR 190「加密运算」用异或与进位循环实现无加减号加法【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文是《图解算法数据结构》leetbook_ioa专栏中 LCR 190. 加密运算 的深度技术解析。该题的核心考点是「不使用加减乘除运算符实现整数加法」本质是灵活运用位运算中的**异或无进位和与与运算 左移进位**来模拟 CPU 加法器的运算过程。读完本文你将掌握二进制加法的真值表推导、无进位和与进位的位运算表达、循环收敛条件以及 Python 无定长整数下处理负数补码的关键细节并能在仓库的 Python / Java / C 三语言源码中找到可直接运行的对照实现。题目背景为什么「加密运算」本质是加法LCR 190. 加密运算要求在不使用、-、*、/四则运算符的前提下对两个整数dataA、dataB完成求和。这与经典题 LeetCode 371. 两整数之和 以及剑指 Offer 65「不用加减乘除做加法」是同一知识点的三种考法本仓库均收录了对应实现leetbook_ioa/docs/LCR 190. 加密运算.md本文主体剑指 Offer 65. 不用加减乘除做加法.md 及其三语言源码selected_coding_interview 下的lc_371_sum_of_two_integers系列文件。解法之所以成立是因为加法在二进制层面可以分解为「无进位和」与「进位」两个独立部分而这两部分恰好分别对应两个最基础的位运算于是可以用位运算循环迭代替代四则运算。核心原理从真值表到位运算公式设两数字的二进制形式为dataA, dataB其求和s dataA dataB用dataA(i)表示dataA的二进制第i位。逐位相加时第i位只有四种组合对应的无进位和n(i)与进位c(i1)如下表dataA(i)dataB(i)无进位和n(i)进位c(i1)0000011010101101观察该表可以发现两个关键规律无进位和与异或运算规律相同只有两比特不同0,1或1,0时结果才为1恰好是dataA(i) ^ dataB(i)进位与与运算规律相同且需左移一位只有两比特同为1时才产生进位即dataA(i) dataB(i)由于进位要作用到高一位所以再左移一位。于是无进位和n与进位c的计算公式为$$ \begin{cases} n dataA \oplus dataB 非进位和异或运算 \ c dataA \space \space dataB 1 进位与运算 左移一位 \end{cases} $$由于「和s 非进位和n 进位c」原式可转化为$$ s dataA dataB \Rightarrow s n c $$n与c相加时仍可能产生新的进位因此需要循环求n和c直至进位c 0此时s n返回n即可。整个过程完全由位运算驱动没有使用任何四则运算符。三语言实现与仓库源码印证Java 实现class Solution { public int encryptionCalculate(int dataA, int dataB) { while(dataB ! 0) { // 当进位为 0 时跳出 int c (dataA dataB) 1; // c 进位 dataA ^ dataB; // dataA 非进位和 dataB c; // dataB 进位 } return dataA; } }C 实现class Solution { public: int encryptionCalculate(int dataA, int dataB) { while(dataB ! 0) { int c (unsigned int)(dataA dataB) 1; dataA ^ dataB; dataB c; } return dataA; } };C 版本中(unsigned int)(dataA dataB) 1先将按位与的结果转为无符号整型再左移是为了规避有符号整数左移可能产生的未定义行为负数的符号位左移。仓库中的可运行对照实现在 sword_for_offer/codes/cpp/sfo_65_implement_addition_operation_without_arithmetic_operators_s1/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.cpp其main()中以a 1, b 1为测试用例并输出结果2。Python 实现class Solution: def encryptionCalculate(self, dataA: int, dataB: int) - int: x 0xffffffff dataA, dataB dataA x, dataB x while dataB ! 0: dataA, dataB (dataA ^ dataB), (dataA dataB) 1 x return dataA if dataA 0x7fffffff else ~(dataA ^ x)Python 版本额外多了两步 0xffffffff掩码操作与末尾的补码还原原因详见下文「Python 负数的存储」一节。仓库中的可运行对照实现在 sword_for_offer/codes/python/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.py文件头部通过from include import *引入仓库公共模块Driver Code中直接构造Solution()并打印add(1, 1)的结果同类实现的 LeetCode 371 版本见 selected_coding_interview/codes/python/lc_371_sum_of_two_integers.py。复杂度分析时间复杂度 O(1)最差情况下例如dataA 0x7fffffffdataB 1时需循环 32 次使用 O(1) 时间每轮中的常数次位操作使用 O(1) 时间。循环次数与操作数的二进制位数相关32 位整数最多迭代 32 轮不随数值大小增长因此整体仍是常数时间。空间复杂度 O(1)只使用c等常数个临时变量使用常数大小的额外空间。负数的处理补码让加法与减法统一Q若数字dataA和dataB中有负数则变成了减法如何处理A在计算机系统中数值一律用补码来表示和存储。补码的优势是加法、减法可以统一处理CPU 只有加法器。因此以上方法同时适用于正数和负数的加法。这正是本题敢用「位运算循环」通吃所有整数输入的底层原因补码编码下a - b等价于a (-b 的补码)减法被折叠进同一套加法流程。所以上面的循环无需对符号做任何分支判断。深入细节Python 负数的存储与掩码还原Python、Java、C 等语言中的数字都以补码形式存储但 Python 没有int、long等不同长度的变量即编程时没有变量位数的概念——Python 整数是任意精度的。这导致两个需要特殊处理的点1. 获取负数的补码将数字与十六进制数0xffffffff相与可理解为舍去该数字 32 位以上的部分将 32 位以上都变为0从而把无限长度的 Python 整数截断为一个 32 位整数。这就是循环体里dataA, dataB dataA x, dataB x与(dataA dataB) 1 x中掩码x 0xffffffff的用途保证每一步运算都在 32 位范围内进行。2. 返回前数字还原若补码dataA为负数0x7fffffff是最大的正数的补码补码最高位为 1 即代表负数需执行~(dataA ^ x)操作将补码还原至 Python 的存储格式。拆解其原理dataA ^ x将第 1 至 32 位按位取反~将整个数字取反因此~(dataA ^ x)的效果是第 32 位以上的位取反第 1 至 32 位保持不变从而把 32 位补码还原成 Python 的负数表示。可以用下面的交互式 Python 代码直观验证补码行为print(hex(1)) # 0x1 补码 print(hex(-1)) # -0x1 负号 原码 Python 特色Java 会直接输出补码 print(hex(1 0xffffffff)) # 0x1 正数补码 print(hex(-1 0xffffffff)) # 0xffffffff 负数补码 print(-1 0xffffffff) # 4294967295 Python 将其认为正数注意print(hex(-1))输出-0x1这是 Python 独有的显示习惯负号加原码而 Java 会直接输出补码-1 0xffffffff结果为4294967295即 Python 将截断后的 32 位补码当作了正数——这正是返回前必须用~(dataA ^ x)还原的原因。小结一条可复用的位运算加法模板本题的解法可以抽象为一条通用模板适用于任何「禁用四则运算符做加法」的题目用异或求无进位和n a ^ b用「与 左移一位」求进位c (a b) 1将(n, c)作为新的(a, b)循环迭代直到进位为0Python 需额外用0xffffffff掩码约束 32 位范围并在返回前用~(a ^ x)还原负数。从仓库的三份对照实现Java、C、Python可以看出同一算法在不同语言下的差异仅在类型系统的边界处理C 的强制无符号左移、Python 的掩码与还原核心的「异或 与左移」循环完全一致。理解了真值表推导与补码机制后这道题也就真正掌握了。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode-Book 位运算专题：LCR 190「加密运算」用异或与进位循环实现无加减号加法
LeetCode-Book 位运算专题LCR 190「加密运算」用异或与进位循环实现无加减号加法【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本文是《图解算法数据结构》leetbook_ioa专栏中 LCR 190. 加密运算 的深度技术解析。该题的核心考点是「不使用加减乘除运算符实现整数加法」本质是灵活运用位运算中的**异或无进位和与与运算 左移进位**来模拟 CPU 加法器的运算过程。读完本文你将掌握二进制加法的真值表推导、无进位和与进位的位运算表达、循环收敛条件以及 Python 无定长整数下处理负数补码的关键细节并能在仓库的 Python / Java / C 三语言源码中找到可直接运行的对照实现。题目背景为什么「加密运算」本质是加法LCR 190. 加密运算要求在不使用、-、*、/四则运算符的前提下对两个整数dataA、dataB完成求和。这与经典题 LeetCode 371. 两整数之和 以及剑指 Offer 65「不用加减乘除做加法」是同一知识点的三种考法本仓库均收录了对应实现leetbook_ioa/docs/LCR 190. 加密运算.md本文主体剑指 Offer 65. 不用加减乘除做加法.md 及其三语言源码selected_coding_interview 下的lc_371_sum_of_two_integers系列文件。解法之所以成立是因为加法在二进制层面可以分解为「无进位和」与「进位」两个独立部分而这两部分恰好分别对应两个最基础的位运算于是可以用位运算循环迭代替代四则运算。核心原理从真值表到位运算公式设两数字的二进制形式为dataA, dataB其求和s dataA dataB用dataA(i)表示dataA的二进制第i位。逐位相加时第i位只有四种组合对应的无进位和n(i)与进位c(i1)如下表dataA(i)dataB(i)无进位和n(i)进位c(i1)0000011010101101观察该表可以发现两个关键规律无进位和与异或运算规律相同只有两比特不同0,1或1,0时结果才为1恰好是dataA(i) ^ dataB(i)进位与与运算规律相同且需左移一位只有两比特同为1时才产生进位即dataA(i) dataB(i)由于进位要作用到高一位所以再左移一位。于是无进位和n与进位c的计算公式为$$ \begin{cases} n dataA \oplus dataB 非进位和异或运算 \ c dataA \space \space dataB 1 进位与运算 左移一位 \end{cases} $$由于「和s 非进位和n 进位c」原式可转化为$$ s dataA dataB \Rightarrow s n c $$n与c相加时仍可能产生新的进位因此需要循环求n和c直至进位c 0此时s n返回n即可。整个过程完全由位运算驱动没有使用任何四则运算符。三语言实现与仓库源码印证Java 实现class Solution { public int encryptionCalculate(int dataA, int dataB) { while(dataB ! 0) { // 当进位为 0 时跳出 int c (dataA dataB) 1; // c 进位 dataA ^ dataB; // dataA 非进位和 dataB c; // dataB 进位 } return dataA; } }C 实现class Solution { public: int encryptionCalculate(int dataA, int dataB) { while(dataB ! 0) { int c (unsigned int)(dataA dataB) 1; dataA ^ dataB; dataB c; } return dataA; } };C 版本中(unsigned int)(dataA dataB) 1先将按位与的结果转为无符号整型再左移是为了规避有符号整数左移可能产生的未定义行为负数的符号位左移。仓库中的可运行对照实现在 sword_for_offer/codes/cpp/sfo_65_implement_addition_operation_without_arithmetic_operators_s1/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.cpp其main()中以a 1, b 1为测试用例并输出结果2。Python 实现class Solution: def encryptionCalculate(self, dataA: int, dataB: int) - int: x 0xffffffff dataA, dataB dataA x, dataB x while dataB ! 0: dataA, dataB (dataA ^ dataB), (dataA dataB) 1 x return dataA if dataA 0x7fffffff else ~(dataA ^ x)Python 版本额外多了两步 0xffffffff掩码操作与末尾的补码还原原因详见下文「Python 负数的存储」一节。仓库中的可运行对照实现在 sword_for_offer/codes/python/sfo_65_implement_addition_operation_without_arithmetic_operators_s1.py文件头部通过from include import *引入仓库公共模块Driver Code中直接构造Solution()并打印add(1, 1)的结果同类实现的 LeetCode 371 版本见 selected_coding_interview/codes/python/lc_371_sum_of_two_integers.py。复杂度分析时间复杂度 O(1)最差情况下例如dataA 0x7fffffffdataB 1时需循环 32 次使用 O(1) 时间每轮中的常数次位操作使用 O(1) 时间。循环次数与操作数的二进制位数相关32 位整数最多迭代 32 轮不随数值大小增长因此整体仍是常数时间。空间复杂度 O(1)只使用c等常数个临时变量使用常数大小的额外空间。负数的处理补码让加法与减法统一Q若数字dataA和dataB中有负数则变成了减法如何处理A在计算机系统中数值一律用补码来表示和存储。补码的优势是加法、减法可以统一处理CPU 只有加法器。因此以上方法同时适用于正数和负数的加法。这正是本题敢用「位运算循环」通吃所有整数输入的底层原因补码编码下a - b等价于a (-b 的补码)减法被折叠进同一套加法流程。所以上面的循环无需对符号做任何分支判断。深入细节Python 负数的存储与掩码还原Python、Java、C 等语言中的数字都以补码形式存储但 Python 没有int、long等不同长度的变量即编程时没有变量位数的概念——Python 整数是任意精度的。这导致两个需要特殊处理的点1. 获取负数的补码将数字与十六进制数0xffffffff相与可理解为舍去该数字 32 位以上的部分将 32 位以上都变为0从而把无限长度的 Python 整数截断为一个 32 位整数。这就是循环体里dataA, dataB dataA x, dataB x与(dataA dataB) 1 x中掩码x 0xffffffff的用途保证每一步运算都在 32 位范围内进行。2. 返回前数字还原若补码dataA为负数0x7fffffff是最大的正数的补码补码最高位为 1 即代表负数需执行~(dataA ^ x)操作将补码还原至 Python 的存储格式。拆解其原理dataA ^ x将第 1 至 32 位按位取反~将整个数字取反因此~(dataA ^ x)的效果是第 32 位以上的位取反第 1 至 32 位保持不变从而把 32 位补码还原成 Python 的负数表示。可以用下面的交互式 Python 代码直观验证补码行为print(hex(1)) # 0x1 补码 print(hex(-1)) # -0x1 负号 原码 Python 特色Java 会直接输出补码 print(hex(1 0xffffffff)) # 0x1 正数补码 print(hex(-1 0xffffffff)) # 0xffffffff 负数补码 print(-1 0xffffffff) # 4294967295 Python 将其认为正数注意print(hex(-1))输出-0x1这是 Python 独有的显示习惯负号加原码而 Java 会直接输出补码-1 0xffffffff结果为4294967295即 Python 将截断后的 32 位补码当作了正数——这正是返回前必须用~(dataA ^ x)还原的原因。小结一条可复用的位运算加法模板本题的解法可以抽象为一条通用模板适用于任何「禁用四则运算符做加法」的题目用异或求无进位和n a ^ b用「与 左移一位」求进位c (a b) 1将(n, c)作为新的(a, b)循环迭代直到进位为0Python 需额外用0xffffffff掩码约束 32 位范围并在返回前用~(a ^ x)还原负数。从仓库的三份对照实现Java、C、Python可以看出同一算法在不同语言下的差异仅在类型系统的边界处理C 的强制无符号左移、Python 的掩码与还原核心的「异或 与左移」循环完全一致。理解了真值表推导与补码机制后这道题也就真正掌握了。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考