1. 项目概述为什么用位运算做四则运算刚接触C/C那会儿老师讲到加减乘除大家用的都是、-、*、/这些运算符直观又方便。后来学到位运算知道了、|、^、、这些操作符感觉它们离硬件很近能直接操作比特位效率很高但总觉得和日常的数学计算隔着一层。直到有一次我在一个嵌入式项目的底层驱动里看到前辈用纯粹的位操作实现了一个简单的加法器用来处理某些特定寄存器的值当时就觉得很酷。后来在准备一些对性能要求极高的场景或者在一些不支持标准算术运算的极简环境中这种“用位运算实现四则运算”的技巧就成了一种必备的底层思维。这个项目标题“C/C位运算实现四则运算”听起来像是一个纯粹的学术练习或者面试题但它背后的价值远不止于此。它本质上是在探讨计算机最底层的运算逻辑是如何构建的。我们日常写的a b在编译器层面最终也会被翻译成一系列的机器指令而这些指令在CPU的算术逻辑单元ALU中执行时其核心就是基于与、或、非、异或等逻辑门电路也就是位运算的物理实现。通过自己用代码模拟这个过程你能深刻理解整数在计算机中如何以补码形式存储加法如何通过半加器、全加器链实现减法如何转化为加法乘法如何通过移位和累加完成甚至除法那略显复杂的试商过程。这适合谁呢如果你是C/C的初学者这会是一次绝佳的、深入理解数据表示和运算本质的练习能帮你打下坚实的底层基础。如果你正在准备技术面试尤其是那些偏向底层、嵌入式或对算法效率有苛刻要求的岗位这类问题是常客。即便你已经是经验丰富的开发者重温这些基础也能在优化关键代码路径、编写可移植的底层库或者进行某些安全编码如避免溢出时提供更清晰的思路。接下来我们就抛开高级语言提供的便利从比特的视角重新搭建一遍加减乘除的运算体系。2. 核心原理二进制、补码与位操作基础在动手用位运算搭建四则运算之前我们必须把“地基”打牢。这个地基就是二进制数的表示方法特别是负数的表示——补码以及我们手中的工具六种位运算符。2.1 二进制与补码计算机的语言计算机只认识0和1。一个int类型的变量在32位系统上就是32个连续的比特位。对于正整数其二进制表示非常直观就是其值的二进制形式。例如十进制5的32位二进制表示为00000000 00000000 00000000 00000101。难点在于负数。C/C标准规定整数采用补码形式存储。补码的定义对于理解后续的运算至关重要正数的补码与其原码二进制表示相同。负数的补码将其对应正数的原码按位取反得到反码然后加1。 例如求-5的补码5的原码00000101按位取反11111010这就是反码加111111011这就是-5的补码补码有一个极其重要的特性可以将减法运算统一为加法运算。A - B等价于A (-B)而-B就是B的补码。这使得CPU的ALU只需要加法器就能同时处理加法和减法大大简化了硬件设计。我们后续用位运算实现减法时正是利用了这一特性。2.2 位运算工具箱六种利器C/C提供了六种位运算符它们直接对整数的每一个比特位进行操作按位与 ()两个位都为1时结果才为1。1010 1100 1000常用场景掩码操作取出特定位、判断奇偶x 1。按位或 (|)两个位有一个为1时结果就为1。1010 | 1100 1110常用场景将特定位设置为1。按位异或 (^)两个位不同时结果为1。1010 ^ 1100 0110重要特性任何数与自身异或结果为0a ^ a 0与0异或结果不变a ^ 0 a。异或是实现加法的核心。按位取反 (~)将每一位取反0变11变0。~1010 0101这里假设是4位实际会取反所有位包括高位注意这是得到反码的关键操作但要注意操作数的类型和位数。左移 ()将各二进制位全部左移若干位高位丢弃低位补0。0010 2 1000相当于乘以4注意对于有符号数左移可能改变符号位导致溢出或未定义行为。右移 ()将各二进制位全部右移若干位。对于无符号数低位丢弃高位补0。对于有符号数低位丢弃高位补符号位算术右移。1010 1 1101假设为4位有符号数算术右移相当于除以2并向下取整注意位运算符的优先级通常低于算术运算符在复杂表达式中务必使用括号来明确运算顺序避免难以察觉的错误。有了二进制、补码的概念和这六种位运算符我们就具备了从零开始构建四则运算的全部基础材料。接下来的每一步我们都会看到这些基础材料是如何被组合成复杂功能的。3. 加法实现从半加器到完整加法器加法是所有运算的基础。在数字电路里加法器是由更基本的逻辑门与、或、非、异或构成的。我们用位运算来模拟这个过程。3.1 核心思路模拟硬件加法器观察两个二进制位相加0 0 0(和0 进位0)0 1 1(和1 进位0)1 0 1(和1 进位0)1 1 0(和0 进位1)你会发现“和”的结果正好是“异或(^)”运算而**“进位”的结果正好是“与()”运算**。一个能计算两个一位二进制数相加并产生“和”与“进位”的电路叫做半加器。但是实际的加法是多位一起算的每一位在计算时除了要加两个加数对应的位还要加上来自低位的进位。所以我们需要全加器输入是加数位A、加数位B、低位进位Cin输出是和S、向高位的进位Cout。通过逻辑推导或观察真值表可以得出当前位和 S A ^ B ^ Cin当前位进位 Cout (A B) | ((A ^ B) Cin)这个Cout的表达式可以理解为要么A和B同时为1产生进位要么A和B中有一个为1即A^B1并且低位有进位(Cin1)。3.2 迭代实现算法对于两个32位整数a和b我们不能一次性算出所有位因为高位需要低位的进位。我们可以迭代处理计算无进位和sum a ^ b。这相当于把所有不考虑进位的位先加起来。计算进位carry (a b) 1。因为只有两个位都为1时才产生进位并且这个进位是作用在更高一位上的所以需要左移一位。现在问题变成了计算sum carry。这又回到了加法本身。将sum赋值给acarry赋值给b重复步骤1-3。当carry即b为0时说明所有进位都已处理完毕此时的sum即a就是最终结果。这个过程就像是在手动处理竖式加法从低位开始计算当前位的和与进位把进位加到下一位依次进行。int add(int a, int b) { while (b ! 0) { // 计算无进位和 int sum a ^ b; // 计算进位并左移一位准备加到高位 int carry (a b) 1; // 将问题转化为 sum carry a sum; b carry; } return a; }3.3 递归实现与注意事项上面的迭代逻辑很容易改写成递归形式更加简洁int add_recursive(int a, int b) { if (b 0) { return a; } return add_recursive(a ^ b, (a b) 1); }实操心得与避坑指南溢出处理我们这个算法模拟的是硬件加法器的行为它本身不检测溢出。对于有符号整数如果两个正数相加结果为负或两个负数相加结果为正就发生了溢出。在实际应用中如果需要应在调用此函数前后进行检查。负数支持这个算法完美支持负数因为我们已经基于补码表示。a ^ b和(a b) 1这些位操作对补码形式的数据是完全正确的。性能思考虽然这是一个展示原理的算法但在最坏情况下如0xFFFFFFFF 1循环或递归次数等于整数位数如32次。现代CPU的加法指令只需1个时钟周期所以绝对不要在生产代码中用此函数替代运算符。它的价值在于理解和教学。递归深度对于32位整数递归深度最大为32通常不会导致栈溢出。但对于64位整数或某些嵌入式环境迭代版本是更安全的选择。通过加法器的实现我们掌握了用位运算模拟进位传递这一核心思想。接下来减法就可以利用加法轻松实现。4. 减法实现转化为补码加法有了可靠的加法函数add实现减法就变得异常简单这完全得益于补码系统的精妙设计。回顾一下在补码体系中A - B等价于A (-B)。所以我们只需要求出B的相反数-B然后调用加法函数即可。4.1 原理求相反数与补码加法如何用位运算求一个整数b的相反数-b呢根据补码定义-b ~b 1。~b按位取反得到反码。 1再加1得到补码即相反数。因此a - b的位运算实现就是a (~b 1)。4.2 代码实现我们可以直接利用之前实现的add函数。// 假设 add 函数已经正确定义 int subtract(int a, int b) { // -b 等于 ~b 1 int negative_b add(~b, 1); // a - b a (-b) return add(a, negative_b); }如果你追求极致的“纯位运算”也可以不调用add而是将add的逻辑内联展开但那样代码会冗长且重复。模块化的设计更清晰。4.3 深入理解一个具体例子让我们以 4 位有符号数为例取值范围 -8 到 7计算5 - 3。a 5二进制补码0101b 3二进制补码0011求-b~b 1100~b 1 1101这正是 -3 的补码计算a (-b)0101 1101无进位和0101 ^ 1101 1000进位(0101 1101) 1 (0101) 1 1010下一轮1000 1010无进位和1000 ^ 1010 0010进位(1000 1010) 1 (1000) 1 10000(5位超出4位)由于我们只考虑4位高位的1溢出丢弃所以有效进位为0000。最终a 0010即十进制2。结果正确。这个例子也展示了在有限位数下进位溢出的情况它恰好得到了正确的结果。注意事项减法与溢出和加法一样这个减法实现也不包含溢出检查。例如在32位系统中INT_MIN - 1会导致溢出产生未定义行为在我们的模拟中可能会得到一个错误结果。一致性只要你的add函数能正确处理补码加法这个subtract函数就能正确工作。这体现了底层构建的优雅性——用简单的基石搭建复杂的功能。加法和减法的实现展示了位运算如何通过模拟硬件逻辑来完成基本算术。接下来我们将挑战更复杂的乘法和除法。5. 乘法实现移位与累加乘法在硬件上可以通过一系列加法和移位操作来实现我们常用的笔算竖式乘法就是这个原理的体现。例如计算13 * 9二进制1101 * 10011101 (13) * 1001 (9) --------- 1101 (1101 * 1) 0000 (1101 * 0左移一位) 0000 (1101 * 0左移两位) 1101 (1101 * 1左移三位) ------------ 1110101 (117)观察发现如果乘数的某一位是1我们就把被乘数左移相应的位数后加到结果上如果是0则加0。这就是移位累加算法的核心。5.1 算法步骤解析初始化结果result 0。循环检查乘数的每一位如果乘数当前最低位为1 (b 1)则将当前的被乘数a加到结果result上。无论最低位是什么都将被乘数a左移一位相当于乘以2将乘数b右移一位逻辑右移准备检查下一位。循环条件当乘数b不为0时继续。处理符号以上步骤默认处理的是无符号数的乘法。对于有符号数我们需要先记录结果的符号然后取绝对值进行无符号乘法最后根据符号调整结果。5.2 无符号乘法实现我们先实现一个无符号整数乘法的核心逻辑使用之前实现的add函数。// 无符号乘法假设输入为非负整数 int multiply_unsigned(int a, int b) { int result 0; while (b ! 0) { // 检查乘数b的最低位 if (b 1) { result add(result, a); // 使用我们的加法函数 } // 被乘数左移一位乘数右移一位 a 1; b 1; // 对于无符号数应使用逻辑右移C中对于无符号数是逻辑右移 } return result; }5.3 完整的有符号乘法实现为了处理负数我们需要在计算前提取符号并将操作数转换为正数。int multiply(int a, int b) { // 判断结果符号同号为正异号为负 // 使用异或最高位符号位相同则结果为0正不同则为1负 // 但更安全的方法是直接判断 int sign 1; if ((a 0 b 0) || (a 0 b 0)) { sign -1; } // 取绝对值注意对INT_MIN取绝对值会溢出这里假设环境安全或使用更大类型 // 一个简单的取绝对值方法判断是否为负然后使用我们的减法函数 0 - a int abs_a a; int abs_b b; // 由于我们还没有实现比较这里用简单判断。实际中需注意INT_MIN。 if (abs_a 0) abs_a subtract(0, abs_a); // 0 - a if (abs_b 0) abs_b subtract(0, abs_b); // 计算无符号乘积 int unsigned_product multiply_unsigned(abs_a, abs_b); // 应用符号 if (sign -1) { return subtract(0, unsigned_product); // 取反 } else { return unsigned_product; } }5.4 优化与边界情况效率这个算法的循环次数等于乘数b的二进制有效位数。对于较大的乘数可以优化为检查b的每一个为1的位但最坏情况b的所有位都是1复杂度仍是 O(n)n为位数。溢出和加减法一样这个乘法函数不检测溢出。两个很大的正数相乘结果可能超出int范围导致高位截断得到错误结果。INT_MIN 处理代码中取绝对值部分对INT_MIN处理不当因为-INT_MIN在标准补码表示中会溢出。在生产代码中需要将参数提升到更宽的类型如long long再进行计算和检查。实操心得移位 vs 乘法在明确乘以2的幂次方时直接用左移运算符比调用这个乘法函数或使用*运算符效率高得多因为编译器通常能将其优化为一条指令。例如a * 8写成a 3。符号处理陷阱判断符号时避免使用a * b 0因为这本身就用到了乘法。我们采用分支判断是安全的。取绝对值时abs函数可能不是纯位运算所以我们用0 - a来模拟。测试用例务必测试正数×正数、正数×负数、负数×负数、乘以0、乘以1等边界情况。乘法通过分解为加法和移位让我们看到了复杂运算如何回归到基本操作。最后我们来看最复杂的运算——除法。6. 除法实现恢复余数法与试商除法是四则运算中最复杂的其位运算实现模拟的是计算机硬件的除法算法常见的有“恢复余数法”和“不恢复余数法加减交替法”。这里我们讲解更直观的恢复余数法。6.1 算法原理模拟竖式除法我们计算A / B整除忽略余数或同时求余数。以二进制为例过程类似于十进制竖式除法从被除数的高位开始取与除数相同数量的位作为“部分余数”。比较部分余数和除数。如果部分余数 除数则商的对应位为1并用部分余数减去除数得到新的部分余数。否则商的对应位为0。从被除数中取下一位移入部分余数的最低位重复步骤2直到处理完被除数的所有位。由于我们是在二进制下操作步骤2可以简化因为除数左移后与部分余数比较等价于判断“部分余数是否大于等于除数”。而商的每一位只能是0或1。6.2 无符号除法实现同时求余数我们实现一个返回商和余数的函数。算法从被除数的最高位开始“试探”。typedef struct { int quotient; // 商 int remainder; // 余数 } DivResult; DivResult divide_unsigned(int dividend, int divisor) { if (divisor 0) { // 除零错误这里简单处理实际应做错误处理 DivResult err {0, 0}; // 可以设置一个错误标志 return err; } int quotient 0; int remainder 0; // 假设是32位整数 for (int i 31; i 0; i--) { // 1. 将余数左移一位空出最低位 remainder 1; // 2. 取出被除数的当前最高位放入余数的最低位 // 方法将被除数左移i位后与1进行与操作判断该位是1还是0 int bit (dividend i) 1; remainder | bit; // 设置余数最低位 // 3. 比较余数和除数 if (remainder divisor) { // 4. 如果余数 除数则商的当前位设为1 quotient | (1 i); // 设置商对应位为1 // 5. 余数减去除数 remainder subtract(remainder, divisor); // 使用我们的减法函数 } // 否则商的当前位保持为0已初始化余数不变 } // 循环结束后quotient中是商remainder中是余数 DivResult result {quotient, remainder}; return result; }6.3 完整的有符号除法实现有符号除法需要额外处理符号并转换为无符号除法。整数除法的规则是商的符号由被除数和除数的符号决定同号为正异号为负余数的符号与被除数相同。DivResult divide(int dividend, int divisor) { DivResult result; // 处理除数为0的情况 if (divisor 0) { // 错误处理此处略 result.quotient 0; result.remainder 0; return result; } // 确定商的符号 int sign_quotient 1; if ((dividend 0 divisor 0) || (dividend 0 divisor 0)) { sign_quotient -1; } // 余数的符号与被除数相同 int sign_remainder (dividend 0) ? 1 : -1; // 简化处理注意0的情况 // 取被除数和除数的绝对值 int abs_dividend dividend; int abs_divisor divisor; if (abs_dividend 0) abs_dividend subtract(0, abs_dividend); if (abs_divisor 0) abs_divisor subtract(0, abs_divisor); // 调用无符号除法 DivResult unsigned_result divide_unsigned(abs_dividend, abs_divisor); // 应用符号 if (sign_quotient -1) { result.quotient subtract(0, unsigned_result.quotient); } else { result.quotient unsigned_result.quotient; } if (sign_remainder -1) { result.remainder subtract(0, unsigned_result.remainder); } else { result.remainder unsigned_result.remainder; } return result; }6.4 算法细节与边界讨论循环方向for (int i 31; i 0; i--)是从最高位第31位向最低位第0位处理模拟除法从高位开始计算的过程。取位操作(dividend i) 1将dividend右移i位使我们要检查的位移动到最低位然后与1进行与操作从而得到该位的值0或1。设置商位quotient | (1 i)将商quotient的第i位设置为1。比较操作算法中使用了比较符这并非纯位运算。要实现纯位运算的比较需要另外编写函数通过计算差值判断符号位这会使代码更复杂。此处为清晰起见使用了比较。效率恢复余数法在余数小于除数时做了一次无效的比较和移位。更优的“不恢复余数法”会减少操作但逻辑更复杂。边界情况除以零必须处理。被除数为INT_MIN除数为-1这是唯一会导致有符号整数溢出的除法情况因为结果-INT_MIN超出了int的正数范围。我们的代码没有处理这个溢出。符号处理C/C标准中整数除法的舍入方向是“向零取整”。我们通过先取绝对值计算再应用符号的方式实现了这一标准。常见问题与排查结果全为零检查循环变量i的起始值和终止条件是否正确。确保是从最高位开始。商或余数符号错误仔细核对符号确定逻辑。记住规则商 (被除数符号) XOR (除数符号)余数符号 被除数符号。对于负数绝对值转换出错特别是INT_MIN其绝对值无法用相同类型的正整数表示。一个常见的技巧是使用无符号类型进行中间计算。例如unsigned int abs_a (a 0) ? (unsigned int)(-a) : (unsigned int)a;但-a对INT_MIN仍是问题。最安全的方法是先用更大类型long long转换。7. 综合测试、边界与进阶思考将加、减、乘、除四个函数组合在一起我们就完成了一套完整的、基于位运算的四则运算库。让我们设计一些测试用例来验证其正确性并讨论一些边界情况和进阶话题。7.1 综合测试用例一个好的测试应覆盖正常情况、边界情况和异常情况。#include stdio.h #include limits.h // 用于INT_MAX, INT_MIN // 这里插入之前定义的 add, subtract, multiply, divide 函数... void test_basic() { printf( 基础功能测试 \n); printf(5 3 %d (预期: 8)\n, add(5, 3)); printf(-5 3 %d (预期: -2)\n, add(-5, 3)); printf(5 - 3 %d (预期: 2)\n, subtract(5, 3)); printf(3 - 5 %d (预期: -2)\n, subtract(3, 5)); printf(5 * 3 %d (预期: 15)\n, multiply(5, 3)); printf(-5 * 3 %d (预期: -15)\n, multiply(-5, 3)); DivResult d divide(10, 3); printf(10 / 3 商: %d, 余数: %d (预期: 3, 1)\n, d.quotient, d.remainder); d divide(-10, 3); printf(-10 / 3 商: %d, 余数: %d (预期: -3, -1)\n, d.quotient, d.remainder); } void test_edge() { printf(\n 边界情况测试 \n); printf(0 0 %d\n, add(0, 0)); printf(INT_MAX 0 %d\n, add(INT_MAX, 0)); printf(INT_MIN - 0 %d\n, subtract(INT_MIN, 0)); // 溢出测试不检查结果可能奇怪 printf(INT_MAX 1 %d (溢出)\n, add(INT_MAX, 1)); printf(INT_MIN - 1 %d (溢出)\n, subtract(INT_MIN, 1)); printf(5 * 0 %d\n, multiply(5, 0)); printf(0 * -5 %d\n, multiply(0, -5)); // 注意INT_MIN * -1 会溢出我们的函数不处理 // printf(INT_MIN * -1 %d\n, multiply(INT_MIN, -1)); // 危险 DivResult d divide(0, 5); printf(0 / 5 商: %d, 余数: %d\n, d.quotient, d.remainder); d divide(5, 1); printf(5 / 1 商: %d, 余数: %d\n, d.quotient, d.remainder); // 除零测试 d divide(5, 0); printf(5 / 0 商: %d, 余数: %d (除零错误结果无意义)\n, d.quotient, d.remainder); } int main() { test_basic(); test_edge(); return 0; }运行这些测试对比结果与预期可以快速定位函数中的逻辑错误。7.2 常见问题排查表问题现象可能原因排查方法加法/减法结果错误尤其是涉及负数时1. 补码求反操作错误。2. 加法循环终止条件或进位计算有误。1. 单步调试查看~b 1是否正确得到-b。2. 用小的正负数如2 -3测试手动演算每一步。乘法结果为0或很小1. 移位方向错误应是a 1,b 1。2. 符号处理逻辑错误将正数误判为负。1. 检查multiply_unsigned循环内的移位操作。2. 打印出sign,abs_a,abs_b的值进行验证。除法死循环或结果巨大1. 循环变量i初始值或条件错误导致无限循环。2. 比较remainder divisor逻辑错误或使用了未初始化的变量。1. 确认for (int i31; i0; i--)正确。2. 在循环内打印i,remainder,divisor,quotient的值观察变化。除法商正确但余数符号错误余数符号应用逻辑错误。标准是余数符号与被除数相同。检查divide函数中sign_remainder的判断和赋值逻辑。处理INT_MIN时出错对INT_MIN取绝对值时发生溢出。-INT_MIN超出int表示范围。在取绝对值前将参数提升到long long或unsigned int类型进行计算和判断。7.3 进阶思考与优化方向性能极限我们实现的算法是教学性质的性能远低于硬件指令。但在某些禁止使用算术运算符的极端场景如某些面试题、或硬件描述语言初学这些代码是可行的。真正的优化需要深入到汇编和硬件层面。纯位运算比较我们的除法函数中使用了比较。要实现纯位运算比较可以写一个isGreaterOrEqual(int a, int b)函数通过计算a - b并判断结果的符号位最高位来实现这又需要用到减法函数和位操作来提取符号位。浮点数支持浮点数的位运算表示IEEE 754标准完全不同。加减乘除涉及符号位、阶码和尾数的复杂操作远非整数位运算这么直观通常由专门的浮点运算单元FPU完成。应用场景嵌入式与底层开发在极少数没有硬件乘法器或除法器的低成本微控制器MCU上软件实现的乘除法例程是必要的。算法与密码学某些加密算法或哈希函数会刻意使用位操作来实现特定的数学变换以避免时序攻击或利用其特性。面试与基础考察这是考察对计算机基础、二进制和位操作理解程度的经典题目。从理解到应用理解这些原理的最大好处不是让你自己写一个四则运算库而是让你在看到(x 3) - (x 1)时能立刻反应过来这是在计算x * 6让你在需要优化一个乘以常数的操作时能想到是否可以用移位和加减的组合来替代让你对代码底层发生的事情有更清晰的图景。写完这一套代码调试通过所有测试用例你对整数在计算机中的表示、运算以及位操作的力量应该会有一种全新的、更深刻的认识。这就像亲手用齿轮和杠杆搭建了一座钟表虽然比不上电子表的精准高效但其中获得的机械美感与洞察力是单纯看时间无法比拟的。
