LeetCode67(二进制求和[位运算,大数运算])

二进制求和

题目要求:
给你两个二进制字符串 a 和 b ,以二进制字符串的形式返回它们的和。

在这里插入图片描述
这道题其实有几种解法.我们先来介绍简单的方法.
我们可以将两个字符串的二进制转成十进制,获取对应值相加之后,我们可以不断对2取余,获取尾数拼接即可.也就是像我们平常求一个十进制的二进制数,可以递归调用,同样也可以迭代.官方题解当中给我们介绍了一种Java自带的API解法,如下所示

class Solution {
    public String addBinary(String a, String b) {
        return Integer.toBinaryString(
            Integer.parseInt(a, 2) + Integer.parseInt(b, 2)
        );
    }
}

但是这种解法具有局限性,官方提到:
如果 a 的位数是 n,b 的位数为 m,这个算法的渐进时间复杂度为 O(n+m)。但是这里非常简单的实现基于 Python 和 Java 本身的高精度功能,在其他的语言中可能并不适用,并且在 Java 中:

  • 如果字符串超过 33 位,不能转化为 Integer
  • 如果字符串超过 65 位,不能转化为 Long
  • 如果字符串超过 500000001 位,不能转化为 BigInteger

所以我们需要一个更加健全的解法
对于这两个字符串,我们可以对最末端,不断相加,若有进位,保留进位相加.一步步拼接字符串.由于是二进制的运算,我们很容易联系到位运算.

对于位运算来讲,十进制的相加我们可以模拟成(a b 相加)
无进位时: sum = a ^ b
有进位时: sum = a ^ b + (a & b) << 1

例如: a = 3 b = 1 时
我们将其转换为二进制
a: 11
b: 01

我们先进行异或运算可以求的没有进位的位相加的结果,这里我们可以得到
temp = 10;
其次我们来求得需要进位的位置,需要进位其实就是上下两端都等于1时,所以我们可以用&运算来实现我们的需求
求得 carry = 01;左移一位得到 carry = 10;
重复上述过程,直至(a & b) == 0即没有进位为止
temp ^ carry = 00;
temp & carry = 10;

左移相加得到 100;满足相加的结果.

而这里我们只需要对当前与进位数相加后,计算此时进位的值,循环往复即可,所以公式得到
sum = x ^ y ^ carry;
carry = (x & y) [这里是有点问题的,我们后面再讨论]

所以我们初步的解题步骤为

我们需要比较两个字符串长度最小值选取为第一次循环的终止条件,然后从字符串的最后面开始遍历,不断对最后一位进行异或运算.代码为

		int size = Math.min(aLength,bLength);
		int carry = 0;
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < size;i++){
            int x = a.charAt(--aLength)-'0';
            int y = b.charAt(--bLength)-'0';
            int sum = (x ^ y ^ carry);
            carry = ( x & y) ; 
            sb.append(sum);
        }

这段代码其实是有一点问题的,我们思考下面这种情形.
当x = 1 , y = 0 ,carry = 1时
我们的 carry 计算公式为 = x & y
这样将会错过进位的运算.
那会有人提出三个数做异或运算呗,像那个sum一样
注意:
我们sum求值概念为三数求值相加后余下来的值,所以我们对三个数做异或运算就可以满足此特性.
但是此时进位处和其不太一样
我们需要只要出现两个1,我们的进位就应该是1.
那我们先来思考x与y的取值有几种情形
x = 1 y = 0
x = 0 y = 1
x = 0 y = 0
x = 1 y = 1

我们讨论的情况当carry = 1时.属于x,y中最多只有一个数出现为1时,我们需要进位 置1.也就是我们进行xy的异或运算后再进行对carry的&运算.

而对于carry = 0而且x与y都等于1时,我们不需要carry进行对应的运算.
所以我们列出改进后的代码

		for(int i = 0;i < size;i++){
            int x = a.charAt(--aLength)-'0';
            int y = b.charAt(--bLength)-'0';
            int sum = (x ^ y ^ carry);
            //carry == 1 x==1 y==0 如果采用x&y 这里会错过进位
            if(carry == 1 && x!=1 && y!=1){
                carry = (x^y) & carry ;
            }
            else if(carry == 0) carry = ( x & y) ;
            sb.append(sum);
        }

此时我们已经完成了较短的字符串的二进制运算
而对于剩下的那个我们仍需要进行字符串的拼接,但我们需要注意的是
可能在第一次循环过后最后相加的那个结点处,我们产生了进位,所以我们依旧需要对进位进行处理.

		while (aLength > 0){
            int x = a.charAt(--aLength)-'0';
            int sum = (x ^ carry);
            carry = ((x&carry));
            sb.append(sum);
        }
        while (bLength > 0){
            int y = b.charAt(--bLength)-'0';
            int sum = (y ^ carry);
            carry = ((y&carry));
            sb.append(sum);
        }

看样子好像已经挺完善啦,其实我们还是漏了一点.也就是当两个字符串都遍历完后.如果此时最高位产生了进位,我们是需要扩展原来的长度,即再加一位来存放最高处的进位.
所以完整代码为

class Solution {
    public String addBinary(String a, String b) {
        int aLength = a.length();
        int bLength = b.length();
        if(aLength < 1) return b;
        if(bLength < 1) return a;
        int carry = 0;
        int size = Math.min(aLength,bLength);
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < size;i++){
            int x = a.charAt(--aLength)-'0';
            int y = b.charAt(--bLength)-'0';
            int sum = (x ^ y ^ carry);
            //carry == 1 x==1 y==0 如果采用x&y 这里会错过进位
            if(carry == 1 && x!=1 && y!=1){
                carry = (x^y) & carry ;
            }
            else if(carry == 0) carry = ( x & y) ;
            sb.append(sum);
        }
        while (aLength > 0){
            int x = a.charAt(--aLength)-'0';
            int sum = (x ^ carry);
            carry = ((x&carry));
            sb.append(sum);
        }
        while (bLength > 0){
            int y = b.charAt(--bLength)-'0';
            int sum = (y ^ carry);
            carry = ((y&carry));
            sb.append(sum);
        }
        if(carry > 0) sb.append(carry);
        return sb.reverse().toString();
    }
}

结果为:

在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/790511.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

笔试算法刷题

猿辅导2021校园招聘笔试&#xff08;算法一&#xff09; 牛客网 - 找工作神器|笔试题库|面试经验|实习招聘内推&#xff0c;求职就业一站解决_牛客网 (nowcoder.com) 第一眼看到这个题想到的是蓝桥杯飞机降落&#xff0c;贪心题。但是这样算的是最大不相交区间数量&#xff0…

docker笔记2

docker笔记2 一、阿里云镜像配置二、docker基本原理1.docker是如何启动一个容器的2.docker的底层原理 三、镜像命令总结 一、阿里云镜像配置 配置镜像的目的 由于Docker Hub等公共镜像仓库的服务器可能位于国外&#xff0c;直接从中拉取镜像时可能会遇到网络延迟或不稳定的问…

MySQL Undo Log

总结自bojiangzhou undo log称为撤销日志或回滚日志。在一个事务中进行增删改操作时&#xff0c;都会记录对应的 undo log。在对数据库进行修改前&#xff0c;会先记录对应的 undo log&#xff0c;然后在事务失败或回滚的时候&#xff0c;就可以用这些 undo log 来将数据回滚到…

(2024,测试时训练(TTT),线性注意力,RNN,嵌套循环)学习(在测试时学习):具有表达性隐藏状态的 RNN

Learning to (Learn at Test Time): RNNs with Expressive Hidden States 公和众与号&#xff1a;EDPJ&#xff08;进 Q 交流群&#xff1a;922230617 或加 VX&#xff1a;CV_EDPJ 进 V 交流群&#xff09; 目录 0. 摘要 1. 简介 2. 方法 2.1 使用 TTT 更新隐藏状态 2.2 …

常用的JVM启动参数

JVM的启动参数有很多&#xff0c;但是我们平常能用上的并不是特别多&#xff0c;这里介绍几个我们常用的&#xff1a; 1. 堆设置&#xff1a; 。 -Xms&#xff1a;设置堆的初始大小。 。.-Xmx&#xff1a;设置堆的最大大小。 2. 栈设置&#xff1a; 。 -XsS&#xff1a;设置每个…

​​​防御第一次作业

1、拓扑图及实验要求&#xff1a; 2、配置&#xff1a; 配置终端及服务器IP地址&#xff1a; Pc2&#xff1a; Client1&#xff1a; Pc4&#xff1a; Client2&#xff1a; PC1&#xff1a; Server1&#xff1a; Server2&#xff1a; 防火墙基础配置&#xff1a; [fw1]int g …

光学、SAR卫星影像助力洞庭湖决堤抢险(附带数据下载)

​​ 点击下方全系列课程学习 点击学习—>ArcGIS全系列实战视频教程——9个单一课程组合系列直播回放 点击学习——>遥感影像综合处理4大遥感软件ArcGISENVIErdaseCognition 7月5日下午&#xff0c;湖南岳阳市华容县团洲乡团北村团洲垸洞庭湖一线堤防发生决口&#xff0…

怎样在 PostgreSQL 中优化对 UUID 数据类型的索引和查询?

文章目录 一、UUID 数据类型概述二、UUID 索引和查询的性能问题三、优化方案&#xff08;一&#xff09;选择合适的索引类型&#xff08;二&#xff09;压缩 UUID&#xff08;三&#xff09;拆分 UUID&#xff08;四&#xff09;使用覆盖索引&#xff08;五&#xff09;优化查询…

Meta发布Llama 2驱动的AI代码生成器:Code Llama,开源来袭!

Meta 刚刚了号称是编程领域 “最先进的大语言模型”—— Code Llama &#xff0c;可根据 代码和自然语言提示 生成代码和有关代码的自然语言&#xff0c;支持多种主流编程语言&#xff0c; 包括 Python、C、Java、PHP、Typescript (Javascript)、C# 和 Bash 。 Code Llama 完全…

“Pandas数据处理与分析:实用技巧与应用“

目录 # 开篇 1. pandas的series的了解 1.1 pd.Series 创建 1.2 pd.series 的索引使用 1.3 pd.series 之字典/索引 1.4 pandas 转换数据类型 1.5 pandas 通过索引或者通过位置来取值 1.6 pandas 指定行取值 1.7 pands之Series 切片和索引 1.8 pands之Series 的索引和值…

vue2/3代码格式化问题,看着太难受了

1.原本的代码&#xff1a; 格式化后的代码&#xff1a; 太难受了&#xff01; 2.原本的代码 格式化后的代码 格式化跟有病似的&#xff0c;看着非常难受&#xff01; 有没有什么插件解决&#xff01;&#xff1f;

C++ //练习 14.44 编写一个简单的桌面计算器使其能处理二元运算。

C Primer&#xff08;第5版&#xff09; 练习 14.44 练习 14.44 编写一个简单的桌面计算器使其能处理二元运算。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim 代码块 /**********************************************************…

Cesium中实现全球体积云效果的一种方案

原生 Cesium 提供了一种积云的效果&#xff0c;云的物理特征和渲染性能都还不错&#xff0c;这种方案适合表达小范围相对离散的云朵&#xff0c;但是用来实现全球范围下相对连续、柔和渐变的云层比较困难。本文在体渲染的基础上&#xff0c;参考了开源社区中 shadertoy 和 thre…

java数组之线性查找、二分法查找

一、线性查找 思想&#xff1a;如果想在一个数组中查找是否有某个元素&#xff0c;最容易想到的办法就是遍历数组&#xff0c;将数组中元素与想要查找的元素逐个对比&#xff0c;如果相等表示找到了&#xff0c;如果不等&#xff0c;则表示没找到。这就是线性查找的思想。 案例…

如何在微信小程序中对接微信支付

个人名片 &#x1f393;作者简介&#xff1a;java领域优质创作者 &#x1f310;个人主页&#xff1a;码农阿豪 &#x1f4de;工作室&#xff1a;新空间代码工作室&#xff08;提供各种软件服务&#xff09; &#x1f48c;个人邮箱&#xff1a;[2435024119qq.com] &#x1f4f1…

流模型flow

流模型 Flow 超详解&#xff0c;基于 Flow 的生成式模型&#xff0c;从思路到基础到公式推导到模型理解与应用&#xff08;Flow-based Generative Model&#xff09;_generative flows-CSDN博客

软考《信息系统运行管理员》-3.1信息系统设施运维的管理体系

3.1信息系统设施运维的管理体系 1 信息系统设施运维的对象 基础环境 主要包括信息系统运行环境(机房、设备间、配线室、基站、云计算中心 等)中的空调系统、供配电系统、通信应急设备系统、防护设备系统(如消防系统、安全系统) 等&#xff0c;能维持系统安全正常运转&#xf…

食物链之带权并查集解法

直接看题&#xff1a;https://www.acwing.com/problem/content/description/242/ 下面就是代码的实现了&#xff0c;因为自己与自己肯定是同类我们初始化为0. 下面是AC代码&#xff1a; #include<bits/stdc.h> using namespace std; int n,k; int fk,x,y; int fa[10001…

C++ STL IO流介绍

目录 一&#xff1a;IO流的继承关系&#xff1a; 二&#xff1a;输入输出功能 1. 基本用法 2. 格式化输入 3.非格式化输入 4. 格式化输出 三&#xff1a;流 1. 字符流 2. 向字符流中写入数据 3. 从字符流中读出数据 4. 清空字符流 5.完整的例子 四&#xff1a;文件…

RISC-V异常处理流程概述(2):异常处理机制

RISC-V异常处理流程概述(2):异常处理机制 一、异常处理流程和异常委托1.1 异常处理流程1.2 异常委托二、RISC-V异常处理中软件相关内容2.1 异常处理准备工作2.2 异常处理函数2.3 Opensbi系统调用的注册一、异常处理流程和异常委托 1.1 异常处理流程 发生异常时,首先需要执…