diff --git a/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BigIntegerExample.java b/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BigIntegerExample.java new file mode 100644 index 000000000000..ed37d5266c44 --- /dev/null +++ b/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BigIntegerExample.java @@ -0,0 +1,46 @@ +package com.baeldung.arbitrarylengthbinaryintegers; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +import java.math.BigInteger; + +public class BigIntegerExample { + + private static final Logger log = LoggerFactory.getLogger(BigIntegerExample.class); + + public static void main(String[] args) { + BigInteger a = new BigInteger("1101001011010101010101010101010101010101010101010101010101010101010", 2); + BigInteger b = new BigInteger("-10000", 2); + + log.info(getBinaryOperations(a, b)); + + BigInteger c = new BigInteger("11111111111111111111111111111000", 2); + log.info("c = " + c.toString(2) + " (" + c + ")"); + } + + public static String getBinaryOperations(BigInteger a, BigInteger b) { + return "a = " + a.toString(2) + " (" + a + ")\n" + + "b = " + b.toString(2) + " (" + b + ")\n" + + "a + b = " + a.add(b).toString(2) + " (" + a.add(b) + ")\n" + + "a - b = " + a.subtract(b).toString(2) + " (" + a.subtract(b) + ")\n" + + "a * b = " + a.multiply(b).toString(2) + " (" + a.multiply(b) + ")\n" + + "a / b = " + a.divide(b).toString(2) + " (" + a.divide(b) + ")"; + } + + public static BigInteger add(BigInteger a, BigInteger b) { + return a.add(b); + } + + public static BigInteger subtract(BigInteger a, BigInteger b) { + return a.subtract(b); + } + + public static BigInteger multiply(BigInteger a, BigInteger b) { + return a.multiply(b); + } + + public static BigInteger divide(BigInteger a, BigInteger b) { + return a.divide(b); + } +} \ No newline at end of file diff --git a/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryLiterals.java b/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryLiterals.java new file mode 100644 index 000000000000..5f565394d115 --- /dev/null +++ b/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryLiterals.java @@ -0,0 +1,44 @@ +package com.baeldung.arbitrarylengthbinaryintegers; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +public class BinaryLiterals { + + private static final Logger log = LoggerFactory.getLogger(BinaryLiterals.class); + + public static void main(String[] args) { + int a = 0b110100101101010; + int b = 0b1000; + + log.info(getBinaryOperations(a, b)); + + int c = 0b11111111111111111111111111111000; // (2^32 - 8) written in base 2 + log.info("c = " + Integer.toBinaryString(c) + " (" + c + ")"); + } + + public static String getBinaryOperations(int a, int b) { + return "a = " + Integer.toBinaryString(a) + " (" + a + ")\n" + + "b = " + Integer.toBinaryString(b) + " (" + b + ")\n" + + "a + b = " + Integer.toBinaryString(a + b) + " (" + (a + b) + ")\n" + + "a - b = " + Integer.toBinaryString(a - b) + " (" + (a - b) + ")\n" + + "a * b = " + Integer.toBinaryString(a * b) + " (" + (a * b) + ")\n" + + "a / b = " + Integer.toBinaryString(a / b) + " (" + (a / b) + ")"; + } + + public static int add(int a, int b) { + return a + b; + } + + public static int subtract(int a, int b) { + return a - b; + } + + public static int multiply(int a, int b) { + return a * b; + } + + public static int divide(int a, int b) { + return a / b; + } +} \ No newline at end of file diff --git a/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryStringOperations.java b/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryStringOperations.java new file mode 100644 index 000000000000..b1f354a91864 --- /dev/null +++ b/core-java-modules/core-java-numbers-8/src/main/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryStringOperations.java @@ -0,0 +1,403 @@ +package com.baeldung.arbitrarylengthbinaryintegers; + +import org.slf4j.Logger; +import org.slf4j.LoggerFactory; + +public class BinaryStringOperations { + + private static final Logger log = LoggerFactory.getLogger(BinaryStringOperations.class); + + public static void main(String[] args) { + String a = "+110100101000"; + String b = "+1011"; + log.info(getBinaryOperations(a, b)); + a = "+110100101000"; + b = "-1011"; + log.info(getBinaryOperations(a, b)); + a = "-110100101000"; + b = "+1011"; + log.info(getBinaryOperations(a, b)); + a = "-110100101000"; + b = "-1011"; + log.info(getBinaryOperations(a, b)); + b = "+110100101000"; + a = "+1011"; + log.info(getBinaryOperations(a, b)); + b = "+110100101000"; + a = "-1011"; + log.info(getBinaryOperations(a, b)); + b = "-110100101000"; + a = "+1011"; + log.info(getBinaryOperations(a, b)); + b = "-110100101000"; + a = "-1011"; + log.info(getBinaryOperations(a, b)); + + } + + public static String getBinaryOperations(String a, String b) { + return "\na = " + a + "\n" + + "b = " + b + "\n" + + "a + b = " + add(a, b) + "\n" + + "a - b = " + subtract(a, b) + "\n" + + "a * b = " + multiply(a, b) +"\n" + + "a / b = " + divide(a, b) + "\n"; + } + + public static String add(String a, String b) { + String unsignedA = removePlusMinus(a); + String unsignedB = removePlusMinus(b); + + if (isPositive(a)) { + if (isPositive(b)) { + // Example: a=1011, b=1111 + return unsignedAdd(unsignedA, unsignedB); + } else { + // Example: a=1011, b=-1111 + return subtract(unsignedA, unsignedB); + } + } else { + if (isPositive(b)) { + // Example: a=-1011, b=1111 + return subtract(unsignedB, unsignedA); + } else { + // Example: a=-1011, b=-1111 + return '-' + unsignedAdd(unsignedA, unsignedB); + } + } + } + + public static String unsignedAdd(String a, String b) { + validateUnsignedBinaryString(a); + validateUnsignedBinaryString(b); + + // Remove leading zeros + a = a.replaceFirst("^0+(?!$)", ""); + b = b.replaceFirst("^0+(?!$)", ""); + + int length = Math.max(a.length(), b.length()); + + // Pad the shorter string with leading zeros to make both strings of equal length + a = String.format("%" + length + "s", a).replace(' ', '0'); + b = String.format("%" + length + "s", b).replace(' ', '0'); + + StringBuilder result = new StringBuilder(length * 2); + boolean carry = false; + + // Iterate from the LSB (least significant bit) to the MSB (most significant bit) + for (int i = length - 1; i >= 0; i--) { + // Determine the bit values of the current position for both strings + boolean v1 = (a.charAt(i) == '1'); + boolean v2 = (b.charAt(i) == '1'); + + // Calculate the result bit for the current position considering the carry + boolean r = carry && v1 && v2 || carry && !v1 && !v2 || !carry && v1 && !v2 || !carry && !v1 && v2; + + // Update the carry for the next iteration + carry = carry && v1 || carry && v2 || v1 && v2; + + // Insert the result bit at the beginning of the result string + result.insert(0, r ? '1' : '0'); + } + + // If there is a carry left, insert it at the beginning of the result string + if (carry) { + result.insert(0, '1'); + } + + return result.toString(); + } + + + public static String subtract(String a, String b) { + String unsignedA = removePlusMinus(a); + String unsignedB = removePlusMinus(b); + boolean isGreater = compareBinaryStrings(unsignedA, unsignedB) >= 0; + + if (isPositive(a)) { + if (isPositive(b)) { + if (isGreater) { + // Example: a=1011, b=101 + return unsignedSubtract(unsignedA, unsignedB); + } else { + // Example: a=101, b=1011 + return '-' + unsignedSubtract(unsignedB, unsignedA); + } + } else { + // Example: a=1011, b=-1011 + return unsignedAdd(unsignedA, unsignedB); + } + } else { + if (isPositive(b)) { + // Example: a=-1011, b=1011 + return '-' + unsignedAdd(unsignedA, unsignedB); + } else { + if (isGreater) { + // Example: a=-1011, b=-101 + return '-' + unsignedSubtract(unsignedA, unsignedB); + } else { + // Example: a=-101, b=-1011 + return unsignedSubtract(unsignedB, unsignedA); + } + } + } + } + + private static String unsignedSubtract(String a, String b) { + validateUnsignedBinaryString(a); + validateUnsignedBinaryString(b); + + // If b is greater than a, throw an exception since subtraction would result in a negative value + if (compareBinaryStrings(b, a) > 0) { + throw new IllegalArgumentException("Cannot subtract: b is greater than a."); + } + + // Remove leading zeros + a = a.replaceFirst("^0+(?!$)", ""); + b = b.replaceFirst("^0+(?!$)", ""); + + // Since a >= b, without leading zeros b.length() <= a.length() + int length = a.length(); + + // Pad "b" with leading zeros to make both strings of equal length + b = String.format("%" + length + "s", b).replace(' ', '0'); + + // Two's complement step 1: invert all the bits + StringBuilder inverted = new StringBuilder(); + for (int i = 0; i < b.length(); i++) { + char c = b.charAt(i); + if (c == '0') { + inverted.append('1'); + } else { + inverted.append('0'); + } + } + + // Two's complement step 2: add 1 to the inverted bits + String b2complement = addOne(inverted.toString()); + + // Executes the sum between a and the two's complement of b + // Since a>=b, the result will always have an extra bit due to the carry out + // We remove this extra bit by using substring(1) + String result = unsignedAdd(a, b2complement).substring(1); + + // Remove leading zeros from the result + result = result.replaceFirst("^0+(?!$)", ""); + + // If the result is an empty string, it means the result is zero + if (result.isEmpty()) { + result = "0"; + } + + return result; + + } + + public static String multiply(String a, String b) { + String unsignedA = removePlusMinus(a); + String unsignedB = removePlusMinus(b); + + if (isPositive(a)) { + if (isPositive(b)) { + // Example: a=1011, b=1111 + return unsignedMultiply(unsignedA, unsignedB); + } else { + // Example: a=1011, b=-1111 + return '-' + unsignedMultiply(unsignedA, unsignedB); + } + } else { + if (isPositive(b)) { + // Example: a=-1011, b=1111 + return '-' + unsignedMultiply(unsignedA, unsignedB); + } else { + // Example: a=-1011, b=-1111 + return unsignedMultiply(unsignedA, unsignedB); + } + } + } + + public static String divide(String a, String b) { + String unsignedA = removePlusMinus(a); + String unsignedB = removePlusMinus(b); + + if (isPositive(a)) { + if (isPositive(b)) { + // Example: a=1011, b=1111 + return unsignedDivide(unsignedA, unsignedB); + } else { + // Example: a=1011, b=-1111 + String result = unsignedDivide(unsignedA, unsignedB); + if (result.equals("0")) { + // We treat the zero separately so that it does not return -0 + return result; + } + return '-' + result; + } + } else { + if (isPositive(b)) { + // Example: a=-1011, b=1111 + String result = unsignedDivide(unsignedA, unsignedB); + if (result.equals("0")) { + // We treat the zero separately so that it does not return -0 + return result; + } + return '-' + result; + } else { + // Example: a=-1011, b=-1111 + return unsignedDivide(unsignedA, unsignedB); + } + } + } + + private static void validateUnsignedBinaryString(String s) { + if (s.isEmpty()) { + throw new IllegalArgumentException("The string is empty."); + } + if (!s.matches("[01]*")) { + throw new IllegalArgumentException("The string contains invalid characters. Only '0' and '1' are allowed."); + } + } + + private static int compareBinaryStrings(String a, String b) { + // Remove leading zeros + a = a.replaceFirst("^0+(?!$)", ""); + b = b.replaceFirst("^0+(?!$)", ""); + + // Compare lengths + if (a.length() > b.length()) { + return 1; + } else if (a.length() < b.length()) { + return -1; + } + + // Compare digit by digit + for (int i = 0; i < a.length(); i++) { + if (a.charAt(i) != b.charAt(i)) { + return a.charAt(i) - b.charAt(i); + } + } + return 0; // They are equal + } + + private static String addOne(String binary) { + StringBuilder result = new StringBuilder(binary); + int length = result.length(); + + // Start from the LSB (Least Significant Bit) and add 1 + for (int i = length - 1; i >= 0; i--) { + if (result.charAt(i) == '0') { + result.setCharAt(i, '1'); + return result.toString(); + } else { + result.setCharAt(i, '0'); + } + } + + // If all bits were inverted (e.g., "111" becomes "000"), add 1 as MSB (Most Significant Bit) + return "1" + result.toString(); + } + + private static String unsignedMultiply(String a, String b) { + validateUnsignedBinaryString(a); + validateUnsignedBinaryString(b); + + // Remove leading zeros + a = a.replaceFirst("^0+(?!$)", ""); + b = b.replaceFirst("^0+(?!$)", ""); + + String result = "0"; + int zeros = -1; + + // Iterate from the LSB (least significant bit) to the MSB (most significant bit) of "b" + for (int i = b.length() - 1; i >= 0; i--) { + zeros++; + if (b.charAt(i) == '1') { + // Calculate the partial product by appending the necessary number of zeros to "a" + // and this partial product is added to the result + result = unsignedAdd(result, appendZeros(a, zeros)); + } + } + + return result; + } + + private static String appendZeros(String a, int zeros) { + StringBuilder sb = new StringBuilder(a); + for (int i = 0; i < zeros; i++) { + sb.append('0'); + } + return sb.toString(); + } + + private static String unsignedDivide(String a, String b) { + validateUnsignedBinaryString(a); + validateUnsignedBinaryString(b); + + if (compareBinaryStrings(b, a) > 0) { + return "0"; + } + + // Remove leading zeros + a = a.replaceFirst("^0+(?!$)", ""); + b = b.replaceFirst("^0+(?!$)", ""); + + if (b.equals("0")) { + throw new ArithmeticException("Division by zero is not allowed"); + } + + StringBuilder result = new StringBuilder(a.length()); + String remainder = ""; + + // Iterate through each bit of the dividend "a" from MSB to LSB + for (int i = 0; i < a.length(); i++) { + if (result.length() == 0) { + // Initialize result and remainder if not yet done + if (compareBinaryStrings(a.substring(0, i + 1), b) >= 0) { + result.append('1'); + remainder = unsignedSubtract(a.substring(0, i + 1), b); + } + } else { + // Concatenate the current bit of "a" to the remainder + remainder += a.charAt(i); + // Compare the current remainder with the divisor "b" + if (compareBinaryStrings(remainder, b) >= 0) { + // If remainder is greater than or equal to divisor, append '1' to result + result.append('1'); + // Subtract divisor "b" from remainder + remainder = unsignedSubtract(remainder, b); + } else { + // If remainder is less than divisor, append '0' to result + result.append('0'); + } + } + } + + return result.toString(); + } + + private static String removePlusMinus(String s) { + if (s == null || s.isEmpty()) { + throw new IllegalArgumentException("The string cannot be null or empty"); + } + if (s.startsWith("+") || s.startsWith("-")) { + return s.substring(1); + } + return s; + } + + private static boolean isPositive(String s) { + if (s == null || s.isEmpty()) { + throw new IllegalArgumentException("String cannot be null or empty"); + } + + char firstChar = s.charAt(0); + + if (firstChar == '+' || firstChar == '0' || firstChar == '1') { + return true; + } else if (firstChar == '-') { + return false; + } else { + throw new IllegalArgumentException("String does not start with a valid character"); + } + } +} diff --git a/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BigIntegerExampleUnitTest.java b/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BigIntegerExampleUnitTest.java new file mode 100644 index 000000000000..7300ff701c6a --- /dev/null +++ b/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BigIntegerExampleUnitTest.java @@ -0,0 +1,43 @@ +package com.baeldung.arbitrarylengthbinaryintegers; + +import static org.junit.jupiter.api.Assertions.*; + +import org.junit.jupiter.api.Test; + +import java.math.BigInteger; + +class BigIntegerExampleUnitTest { + + @Test + void givenTwoBigIntegers_whenAdding_thenResultIsCorrect() { + BigInteger a = new BigInteger("1101001011010101010101010101010101010101010101010101010101010101010", 2); + BigInteger b = new BigInteger("-10000", 2); + BigInteger expected = new BigInteger("1101001011010101010101010101010101010101010101010101010101010011010", 2); + assertEquals(expected, BigIntegerExample.add(a, b), "The addition of a and b should be correct"); + } + + @Test + void givenTwoBigIntegers_whenSubtracting_thenResultIsCorrect() { + BigInteger a = new BigInteger("1101001011010101010101010101010101010101010101010101010101010101010", 2); + BigInteger b = new BigInteger("-10000", 2); + BigInteger expected = new BigInteger("1101001011010101010101010101010101010101010101010101010101010111010", 2); + assertEquals(expected, BigIntegerExample.subtract(a, b), "The subtraction of b from a should be correct"); + } + + @Test + void givenTwoBigIntegers_whenMultiplying_thenResultIsCorrect() { + BigInteger a = new BigInteger("1101001011010101010101010101010101010101010101010101010101010101010", 2); + BigInteger b = new BigInteger("-10000", 2); + BigInteger expected = new BigInteger("-11010010110101010101010101010101010101010101010101010101010101010100000", 2); + assertEquals(expected, BigIntegerExample.multiply(a, b), "The multiplication of a and b should be correct"); + } + + @Test + void givenTwoBigIntegers_whenDividing_thenResultIsCorrect() { + BigInteger a = new BigInteger("1101001011010101010101010101010101010101010101010101010101010101010", 2); + BigInteger b = new BigInteger("-10000", 2); + BigInteger expected = new BigInteger("-110100101101010101010101010101010101010101010101010101010101010", 2); + assertEquals(expected, BigIntegerExample.divide(a, b), "The division of a by b should be correct"); + } + +} \ No newline at end of file diff --git a/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryLiteralsUnitTest.java b/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryLiteralsUnitTest.java new file mode 100644 index 000000000000..3af72a542737 --- /dev/null +++ b/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryLiteralsUnitTest.java @@ -0,0 +1,41 @@ +package com.baeldung.arbitrarylengthbinaryintegers; + +import static org.junit.jupiter.api.Assertions.*; + +import org.junit.jupiter.api.Test; + +class BinaryLiteralsUnitTest { + + @Test + void givenTwoBinaryLiterals_whenAdding_thenResultIsCorrect() { + int a = 0b110100101101010; + int b = 0b1000; + int expected = 0b110100101110010; // Result of a + b in binary + assertEquals(expected, BinaryLiterals.add(a, b), "The addition of a and b should be correct"); + } + + @Test + void givenTwoBinaryLiterals_whenSubtracting_thenResultIsCorrect() { + int a = 0b110100101101010; + int b = 0b1000; + int expected = 0b110100101100010; // Result of a - b in binary + assertEquals(expected, BinaryLiterals.subtract(a, b), "The subtraction of b from a should be correct"); + } + + @Test + void givenTwoBinaryLiterals_whenMultiplying_thenResultIsCorrect() { + int a = 0b110100101101010; + int b = 0b1000; + int expected = 0b110100101101010000; // Result of a * b in binary + assertEquals(expected, BinaryLiterals.multiply(a, b), "The multiplication of a and b should be correct"); + } + + @Test + void givenTwoBinaryLiterals_whenDividing_thenResultIsCorrect() { + int a = 0b110100101101010; + int b = 0b1000; + int expected = 0b110100101101; // Result of a / b in binary + assertEquals(expected, BinaryLiterals.divide(a, b), "The division of a by b should be correct"); + } + +} diff --git a/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryStringOperationsUnitTest.java b/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryStringOperationsUnitTest.java new file mode 100644 index 000000000000..1d14c4b883b6 --- /dev/null +++ b/core-java-modules/core-java-numbers-8/src/test/java/com/baeldung/arbitrarylengthbinaryintegers/BinaryStringOperationsUnitTest.java @@ -0,0 +1,41 @@ +package com.baeldung.arbitrarylengthbinaryintegers; + +import static org.junit.jupiter.api.Assertions.*; + +import org.junit.jupiter.api.Test; + +class BinaryStringOperationsUnitTest { + + @Test + void givenTwoBinaryStrings_whenAdding_thenResultIsCorrect() { + String a = "1101001011010101010101010101010101010101010101010101010101010101010"; + String b = "-10000"; + String expected = "1101001011010101010101010101010101010101010101010101010101010011010"; // Expected result of a + b + assertEquals(expected, BinaryStringOperations.add(a, b), "The addition of a and b should be correct"); + } + + @Test + void givenTwoBinaryStrings_whenSubtracting_thenResultIsCorrect() { + String a = "1101001011010101010101010101010101010101010101010101010101010101010"; + String b = "-10000"; + String expected = "1101001011010101010101010101010101010101010101010101010101010111010"; // Expected result of a - b + assertEquals(expected, BinaryStringOperations.subtract(a, b), "The subtraction of b from a should be correct"); + } + + @Test + void givenTwoBinaryStrings_whenMultiplying_thenResultIsCorrect() { + String a = "1101001011010101010101010101010101010101010101010101010101010101010"; + String b = "-10000"; + String expected = "-11010010110101010101010101010101010101010101010101010101010101010100000"; // Expected result of a * b + assertEquals(expected, BinaryStringOperations.multiply(a, b), "The multiplication of a and b should be correct"); + } + + @Test + void givenTwoBinaryStrings_whenDividing_thenResultIsCorrect() { + String a = "1101001011010101010101010101010101010101010101010101010101010101010"; + String b = "-10000"; + String expected = "-110100101101010101010101010101010101010101010101010101010101010"; // Expected result of a / b + assertEquals(expected, BinaryStringOperations.divide(a, b), "The division of a by b should be correct"); + } + +}