Skip to content

Commit cacd23a

Browse files
mjk22071998mjk22071998
authored
Add binary addition (TheAlgorithms#5593)
1 parent a2457bd commit cacd23a

File tree

3 files changed

+173
-0
lines changed

3 files changed

+173
-0
lines changed

‎DIRECTORY.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -272,6 +272,7 @@
272272
* [GrahamScan](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/geometry/GrahamScan.java)
273273
* greedyalgorithms
274274
* [ActivitySelection](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/ActivitySelection.java)
275+
* [BinaryAddition](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/BinaryAddition.java)
275276
* [CoinChange](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/CoinChange.java)
276277
* [DigitSeparation](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/DigitSeparation.java)
277278
* [FractionalKnapsack](https://github.com/TheAlgorithms/Java/blob/master/src/main/java/com/thealgorithms/greedyalgorithms/FractionalKnapsack.java)
@@ -787,6 +788,7 @@
787788
* [GrahamScanTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/geometry/GrahamScanTest.java)
788789
* greedyalgorithms
789790
* [ActivitySelectionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/ActivitySelectionTest.java)
791+
* [BinaryAdditionTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/BinaryAdditionTest.java)
790792
* [CoinChangeTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/CoinChangeTest.java)
791793
* [DigitSeparationTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/DigitSeparationTest.java)
792794
* [FractionalKnapsackTest](https://github.com/TheAlgorithms/Java/blob/master/src/test/java/com/thealgorithms/greedyalgorithms/FractionalKnapsackTest.java)

‎src/main/java/com/thealgorithms/greedyalgorithms/BinaryAddition.java

Lines changed: 75 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,75 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import java.util.Collections;
4+
5+
/**
6+
* BinaryAddition class to perform binary addition of two binary strings.
7+
*/
8+
public class BinaryAddition {
9+
/**
10+
* Computes the sum of two binary characters and a carry.
11+
* @param a First binary character ('0' or '1').
12+
* @param b Second binary character ('0' or '1').
13+
* @param carry The carry from the previous operation ('0' or '1').
14+
* @return The sum as a binary character ('0' or '1').
15+
*/
16+
public char sum(char a, char b, char carry) {
17+
int count = 0;
18+
if (a == '1') {
19+
count++;
20+
}
21+
if (b == '1') {
22+
count++;
23+
}
24+
if (carry == '1') {
25+
count++;
26+
}
27+
return count % 2 == 0 ? '0' : '1';
28+
}
29+
/**
30+
* Computes the carry for the next higher bit from two binary characters and a carry.
31+
* @param a First binary character ('0' or '1').
32+
* @param b Second binary character ('0' or '1').
33+
* @param carry The carry from the previous operation ('0' or '1').
34+
* @return The carry for the next bit ('0' or '1').
35+
*/
36+
public char carry(char a, char b, char carry) {
37+
int count = 0;
38+
if (a == '1') {
39+
count++;
40+
}
41+
if (b == '1') {
42+
count++;
43+
}
44+
if (carry == '1') {
45+
count++;
46+
}
47+
return count >= 2 ? '1' : '0';
48+
}
49+
/**
50+
* Adds two binary strings and returns their sum as a binary string.
51+
* @param a First binary string.
52+
* @param b Second binary string.
53+
* @return Binary string representing the sum of the two binary inputs.
54+
*/
55+
public String addBinary(String a, String b) {
56+
// Padding the shorter string with leading zeros
57+
int maxLength = Math.max(a.length(), b.length());
58+
a = String.join("", Collections.nCopies(maxLength - a.length(), "0")) + a;
59+
b = String.join("", Collections.nCopies(maxLength - b.length(), "0")) + b;
60+
StringBuilder result = new StringBuilder();
61+
char carry = '0';
62+
// Iterating over the binary strings from the least significant to the most significant bit
63+
for (int i = maxLength - 1; i >= 0; i--) {
64+
char sum = sum(a.charAt(i), b.charAt(i), carry);
65+
carry = carry(a.charAt(i), b.charAt(i), carry);
66+
result.append(sum);
67+
}
68+
// If there's a remaining carry, append it
69+
if (carry == '1') {
70+
result.append('1');
71+
}
72+
// Reverse the result as we constructed it from the least significant bit
73+
return result.reverse().toString();
74+
}
75+
}

‎src/test/java/com/thealgorithms/greedyalgorithms/BinaryAdditionTest.java

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
package com.thealgorithms.greedyalgorithms;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
public class BinaryAdditionTest {
8+
9+
BinaryAddition binaryAddition = new BinaryAddition();
10+
11+
@Test
12+
public void testEqualLengthNoCarry() {
13+
String a = "1010";
14+
String b = "1101";
15+
String expected = "10111";
16+
assertEquals(expected, binaryAddition.addBinary(a, b));
17+
}
18+
19+
@Test
20+
public void testEqualLengthWithCarry() {
21+
String a = "1111";
22+
String b = "1111";
23+
String expected = "11110";
24+
assertEquals(expected, binaryAddition.addBinary(a, b));
25+
}
26+
27+
@Test
28+
public void testDifferentLengths() {
29+
String a = "101";
30+
String b = "11";
31+
String expected = "1000";
32+
assertEquals(expected, binaryAddition.addBinary(a, b));
33+
}
34+
35+
@Test
36+
public void testAllZeros() {
37+
String a = "0";
38+
String b = "0";
39+
String expected = "0";
40+
assertEquals(expected, binaryAddition.addBinary(a, b));
41+
}
42+
43+
@Test
44+
public void testAllOnes() {
45+
String a = "1111";
46+
String b = "1111";
47+
String expected = "11110";
48+
assertEquals(expected, binaryAddition.addBinary(a, b));
49+
}
50+
51+
@Test
52+
public void testOneZeroString() {
53+
String a = "0";
54+
String b = "10101";
55+
String expected = "10101";
56+
assertEquals(expected, binaryAddition.addBinary(a, b));
57+
58+
// Test the other way around
59+
a = "10101";
60+
b = "0";
61+
expected = "10101";
62+
assertEquals(expected, binaryAddition.addBinary(a, b));
63+
}
64+
65+
@Test
66+
public void testLargeBinaryNumbers() {
67+
String a = "101010101010101010101010101010";
68+
String b = "110110110110110110110110110110";
69+
String expected = "1100001100001100001100001100000";
70+
assertEquals(expected, binaryAddition.addBinary(a, b));
71+
}
72+
73+
@Test
74+
public void testOneMuchLonger() {
75+
String a = "1";
76+
String b = "11111111";
77+
String expected = "100000000";
78+
assertEquals(expected, binaryAddition.addBinary(a, b));
79+
}
80+
81+
@Test
82+
public void testEmptyStrings() {
83+
String a = "";
84+
String b = "";
85+
String expected = ""; // Adding two empty strings should return 0
86+
assertEquals(expected, binaryAddition.addBinary(a, b));
87+
}
88+
89+
@Test
90+
public void testAlternatingBits() {
91+
String a = "10101010";
92+
String b = "01010101";
93+
String expected = "11111111";
94+
assertEquals(expected, binaryAddition.addBinary(a, b));
95+
}
96+
}

0 commit comments

Comments
 (0)