当前位置: 首页 > article >正文

使用位运算实现加法、减法、乘法和除法

使用位运算实现加法、减法、乘法和除法是一个经典的计算机科学问题。位运算通常用于低级程序设计和性能优化中,以下是如何用位运算实现这些基本数学运算。

加法

加法可以通过以下步骤实现:

def add(a, b):
    while b != 0:
        # 使用异或得到不考虑进位的加法结果
        sum_without_carry = a ^ b
        # 计算进位
        carry = (a & b) << 1
        # 更新 a 和 b
        a = sum_without_carry
        b = carry
    return a

减法

减法可以通过构造负数并使用加法来实现:

def subtract(a, b):
    # 通过补码法实现 a - b,即计算 a + (-b)
    while b != 0:
        # 使用异或获得不考虑借位的减法结果
        subtract_without_borrow = a ^ b
        # 计算借位,注意这里与加法中的进位不同,需要借位补偿
        borrow = (~a & b) << 1
        # 更新 a 和 b
        a = subtract_without_borrow
        b = borrow
    return a

# 或者使用add计算
def subtract(a, b):
    # 利用按位取反和加 1 获取 b 的补码,进而变为加法
    return add(a, add(~b, 1))

乘法

使用位运算实现乘法主要依赖于移位和加法。基本思想是默认为右移逐位提取因子:

def multiply(a, b):
    result = 0
    negative = (a < 0) ^ (b < 0)  # 判断结果符号
    a, b = abs(a), abs(b)

    while b > 0:
        if b & 1:  # 如果 b 的最低位是 1
            result = add(result, a)
        a <<= 1  # 左移 a,相当于 a * 2
        b >>= 1  # 右移 b,相当于 b // 2

    return -result if negative else result

除法

除法相对复杂,因为我们需要不断减去被除数直到不能再继续,同时记录减去了多少次:

def divide(dividend, divisor):
    if divisor == 0:
        raise ValueError("Cannot divide by zero")
        
    negative = (dividend < 0) ^ (divisor < 0)  # 判断结果符号
    dividend, divisor = abs(dividend), abs(divisor)
    result = 0

    # 试图将除数不断左移,通过以更大的尺度进行减法以提高效率
    while dividend >= divisor:
        temp, multiple = divisor, 1
        while dividend >= (temp << 1):
            temp <<= 1
            multiple <<= 1
        dividend -= temp
        result = add(result, multiple)

    return -result if negative else result

注意事项

这些操作假定整数可以表现为带符号或无符号的较大范围。如果在有限位宽的情况下,比如 32 位有符号整数需要特别注意溢出的处理。

代码较为基础与简化,未加入复杂错误处理,特别是在实际应用中,请根据需要添加错误处理。

实现效率上,使用 Python 原生运算符通常更为高效,但对于理解位级别操作上述实现具有学习价值。


http://www.kler.cn/a/585350.html

相关文章:

  • Ray|RLLib|Tune学习笔记
  • stm32 L432KC(mbed)入门第一课
  • 蓝桥杯省赛:幸运数字
  • 5.编译链接和宏**
  • Redis的持久化-RDB
  • Netflix 技术栈和alibaba技术栈比较
  • 【推荐项目】049-物流系统技术管理平台
  • 【通缩螺旋的深度解析与科技破局路径】
  • 【训练细节解读】文本智能混合分块(Mixtures of Text Chunking,MoC)引领RAG进入多粒度感知智能分块阶段
  • 【C++项目】从零实现RPC框架「二」:项⽬设计
  • 【React】useState及底层处理机制
  • 一篇博客搞定时间复杂度
  • Pytorch的入门
  • Java 8 + Tomcat 9.0.102 的稳定环境搭建方案,适用于生产环境
  • 使用curl随机间隔访问URL-使用curl每秒访问一次URL-nginx
  • Vue配置和安装教程(2025最新)
  • CGI程序处理每一帧VDEC视频数据并输出到HTML页面
  • 【Unity】TextMesh Pro显示中文部分字体异常
  • Cascadeur-3D关键帧动画软件
  • Redis--zset类型