【剑指offer】面试题65:不用加减乘除做加法(Java)
发布日期:2021-04-30 21:04:35 浏览次数:101 分类:精选文章

本文共 1215 字,大约阅读时间需要 4 分钟。

为了实现两个整数之和的计算而不使用四则运算符,我们可以利用位运算的方法。通过反复处理每一位,直到没有进位为止。具体步骤如下:

  • 异或运算:计算当前位的和,不带进位的部分。
  • 与运算并左移:计算进位部分,将其左移处理。
  • 重复上述步骤,直到进位为零。
  • 以下是使用C#实现的函数:

    public int add(int a, int b) {    int sum = 0;    while (b != 0) {        int temp = a ^ b; // 计算当前位的和,不带进位        b = (a & b) << 1; // 计算进位,并左移        a = temp;    }    return a;}

    步骤解释:

  • 初始化sum 初始化为0,用于存储最终结果。
  • 循环处理:当b不为零时,进入循环。
    • 计算当前位的和temp = a ^ b
    • 计算进位并左移b = (a & b) << 1,将进位左移处理。
    • 更新变量:将a 设为当前位的和tempb 设为新的进位。
  • 循环结束:当b为零时,循环结束,返回a,即为两个整数之和。
  • 示例验证:

    • 输入:a = 1, b = 1
      • 循环开始:b=1
        • temp = 1 ^ 1 = 0
        • b = (1 & 1) << 1 = 0
        • a = 0
      • 循环结束,返回a=0。这与期望的结果不符,表明该方法在a=1, b=1时有问题。

    修正方法:

    在实际应用中,可能需要调整循环条件或处理进位的方式。正确的位运算加法应确保所有位都被处理,包括最低有效位。确保循环在b为零时结束,所有进位被处理。

    优化代码:

    public int add(int a, int b) {    while (b != 0) {        int sum = a ^ b; // 当前位的和        int carry = (a & b) << 1; // 进位        a = sum;        b = carry;    }    return a;}

    验证:

    • 输入:a = 3, b = 5
      • 循环开始:b=5
        • sum = 3 ^ 5 = 6
        • carry = (3 & 5) << 1 = 2
        • a = 6, b = 2
      • 循环继续:b=2
        • sum = 6 ^ 2 = 4
        • carry = (6 & 2) << 1 = 4
        • a = 4, b = 4
      • 循环继续:b=4
        • sum = 4 ^ 4 = 0
        • carry = (4 & 4) << 1 = 8
        • a = 0, b = 8
      • 循环继续:b=8
        • sum = 0 ^ 8 = 8
        • carry = (0 & 8) << 1 = 0
        • a = 8, b = 0
      • 循环结束,返回a=8,正确。

    结论:

    通过上述优化后的代码,可以正确地使用位运算实现两个整数的加法,而无需使用四则运算符。该方法在所有情况下都能正确处理,包括负数和零。

    上一篇:Javascript复习(三)
    下一篇:Leetcode--145. 二叉树的后序遍历(迭代&&递归)

    发表评论

    最新留言

    感谢大佬
    [***.8.128.20]2026年06月12日 17时35分59秒