LeetCode67. 二进制求和
题目描述
/**
*
* 给你两个二进制字符串,返回它们的和(用二进制表示)。
*
* 输入为 非空 字符串且只包含数字 1 和 0。
*
*/
思路分析
- 二进制求和算法思路和十进制求和完全一致
- 二进制是逢2进一,而十进制是逢10进1,其他进制也类似
- 从最低位到最高位依次遍历两个字符串,将遍历到的字符转换为数字,并在较短的字符串高位依次补零
- 定义变量carry保存进位,初始为零
- 定义可变字符串保存计算的结果,每次计算都判断是否有进位
- 源码及分析如下
源码及分析
/**
* @param a 二进制字符串a
* @param b 二进制字符串b
* @return 返回计算的结果
*/
public String addBinary(String a, String b) {
//定义变量carry保存进位
int carry = 0;
//定义StringBuffer保存计算的结果
StringBuffer resStr = new StringBuffer();
for (int i = a.length() - 1, j = b.length() - 1; i >= 0 || j >= 0; i--, j--) {
//定义变量 x , y 保存字符串的每一位
//并在较短的字符串高位补零,用于辅助计算
int x = i >= 0 ? a.charAt(i) - '0' : 0;
int y = j >= 0 ? b.charAt(j) - '0' : 0;
//定义临时变量保存各个为相加的结果
int tmp = x + y + carry;
//通过取模和除法处理相加的结果
resStr.append(tmp % 2);
carry = tmp / 2;
}
//计算完所有的二进制位后,判断是否还有进位,如果有进位,再将进位加到结果中
if (carry != 0){
resStr.append(carry);
}
//返回结果
return resStr.reverse().toString();
}