添加 n 个二进制字符串?

1. 引言

在程序设计中,经常需要处理二进制字符串。例如,有可能需要将多个二进制字符串相加,求它们的和。本文将介绍一种实现该功能的方法,以及该方法的代码实现。

2. 添加两个二进制字符串

2.1 思路

要实现将两个二进制字符串相加,可以先将它们补齐成同样的长度,然后按位相加,如果某一位的和为2,则需要向高位进1。

以下是具体的操作步骤:

计算两个二进制字符串的长度,找出长度较大的一个,将另一个字符串前面补0,使得两个字符串长度相等。

从字符串的末尾开始,依次取出每一位,并将它们转换成数字相加。如果两个数字之和小于2,则直接将它们的和写入结果字符串中。如果两个数字之和等于2,则写入0,并将进位标志设为1。如果两个数字之和等于3,则写入1,并将进位标志设为1。

在当前位的操作结束后,如果进位标志为1,则需要将进位加到下一位的计算中。

2.2 代码实现

std::string addBinaryStrings(std::string a, std::string b) {

int n = a.length(), m = b.length();

if (n < m) {

for (int i = 0; i < m - n; ++i) {

a = "0" + a;

}

} else {

for (int i = 0; i < n - m; ++i) {

b = "0" + b;

}

}

n = a.length(), m = b.length();

std::string result(n, '0');

int carry = 0;

for (int i = n - 1; i >= 0; --i) {

int sum = a[i] - '0' + b[i] - '0' + carry;

if (sum < 2) {

result[i] = sum + '0';

carry = 0;

} else if (sum == 2) {

result[i] = '0';

carry = 1;

} else {

result[i] = '1';

carry = 1;

}

}

if (carry == 1) {

result = "1" + result;

}

return result;

}

2.3 示例

以下是一个示例,我们将两个二进制字符串 "10110" 和 "1101" 相加:

10110

+ 01101

------

100011

结果为 "100011"。

3. 添加多个二进制字符串

3.1 思路

要实现将多个二进制字符串相加,可以先将它们按照长度排序,然后从最短的字符串开始,按照前面的方法逐一相加。

以下是具体的操作步骤:

将所有的二进制字符串按照长度从短到长排序。

对于每一位,依次取出所有字符串的这一位,并将它们相加。如果相加的数字个数为n,则它们的和最大为2n-1。如果和小于2,则直接将它们的和写入结果字符串中。如果和等于2,则写入0,并将进位标志设为1。如果和等于3,则写入1,并将进位标志设为1。

在当前位的操作结束后,如果进位标志为1,则需要将进位加到下一位的计算中。

3.2 代码实现

std::string addBinaryStrings(const std::vector& strings) {

int n = strings.size();

std::vector sortedStrings = strings;

std::sort(sortedStrings.begin(), sortedStrings.end(), [](const std::string& a, const std::string& b) {

return a.length() < b.length();

});

std::vector indices(n, 0);

std::string result;

int carry = 0;

for (int i = sortedStrings.back().length() - 1; i >= 0; --i) {

int sum = carry;

for (int j = 0; j < n; ++j) {

if (i < sortedStrings[j].length()) {

sum += sortedStrings[j][sortedStrings[j].length() - 1 - i] - '0';

}

}

if (sum < 2) {

result = std::to_string(sum) + result;

carry = 0;

} else if (sum == 2) {

result = "0" + result;

carry = 1;

} else {

result = "1" + result;

carry = 1;

}

}

if (carry == 1) {

result = "1" + result;

}

return result;

}

3.3 示例

以下是一个示例,我们将三个二进制字符串 "1011"、"10" 和 "1101" 相加:

1011

+ 0010

+ 1101

-----

10110

结果为 "10110"。

4. 总结

本文介绍了一种实现将多个二进制字符串相加的方法,并给出了该方法的代码实现。这种方法的时间复杂度为O(maxLength*n),其中maxLength为字符串中最长的字符串长度,n为字符串个数。该方法的思路简单、清晰,代码实现也比较容易理解。

免责声明:本文来自互联网,本站所有信息(包括但不限于文字、视频、音频、数据及图表),不保证该信息的准确性、真实性、完整性、有效性、及时性、原创性等,版权归属于原作者,如无意侵犯媒体或个人知识产权,请来电或致函告之,本站将在第一时间处理。猿码集站发布此文目的在于促进信息交流,此文观点与本站立场无关,不承担任何责任。

后端开发标签