Subtraction of two numbers using 2’s Complement
Given two numbers a and b. The task is to subtract b from a by using 2’s Complement method.
Note: Negative numbers represented as 2’s Complement of Positive Numbers.
For example, -5 can be represented in binary form as 2’s Complement of 5. Look at the image below:
Examples:
Input : a = 2, b = 3 Output : -1 Input : a = 9, b = 7 Output : 2
To subtract b from a. Write the expression (a-b) as:
(a - b) = a + (-b)
Now (-b) can be written as (2’s complement of b). So the above expression can be now written as:
(a - b) = a + (2's complement of b)
So, the problem now reduces to “Add a to the 2’s complement of b“. The below image illustrates the above method of subtraction for the first example where a = 2 and b = 3.
Below is the implementation of the above method:
C++
#include <bits/stdc++.h> using namespace std; // function to subtract two values // using 2's complement method int Subtract( int a, int b) { int c; // ~b is the 1's Complement of b // adding 1 to it make it 2's Complement c = a + (~b + 1); return c; } // Driver code int main() { int a = 2, b = 3; cout << Subtract(a, b)<<endl; a = 9; b = 7; cout << Subtract(a, b); return 0; } |
Java
class GFG { // function to subtract two values // using 2's complement method static int Subtract( int a, int b) { int c; // ~b is the 1's Complement // of b adding 1 to it make // it 2's Complement c = a + (~b + 1 ); return c; } // Driver code public static void main(String[] args) { int a = 2 , b = 3 ; System.out.println(Subtract(a, b)); a = 9 ; b = 7 ; System.out.println(Subtract(a, b)); } } // This code is contributed // by ChitraNayal |
Python3
# python3 program of subtraction of # two numbers using 2's complement . # function to subtract two values # using 2's complement method def Subtract(a,b): # ~b is the 1's Complement of b # adding 1 to it make it 2's Complement c = a + (~b + 1 ) return c # Driver code if __name__ = = "__main__" : # multiple assignments a,b = 2 , 3 print (Subtract(a,b)) a,b = 9 , 7 print (Subtract(a,b)) |
C#
// C# program of subtraction of // two numbers using 2's complement using System; class GFG { // function to subtract two values // using 2's complement method static int Subtract( int a, int b) { int c; // ~b is the 1's Complement // of b adding 1 to it make // it 2's Complement c = a + (~b + 1); return c; } // Driver code static void Main() { int a = 2, b = 3; Console.WriteLine(Subtract(a, b)); a = 9; b = 7; Console.WriteLine(Subtract(a, b)); } } // This code is contributed // by mits |
PHP
<?php // function to subtract two values // using 2's complement method function Subtract( $a , $b ) { // ~b is the 1's Complement // of b adding 1 to it make // it 2's Complement $c = $a + (~ $b + 1); return $c ; } // Driver code $a = 2; $b = 3; echo Subtract( $a , $b ) . "\n" ; $a = 9; $b = 7; echo Subtract( $a , $b ) . "\n" ; // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Function to subtract two values // using 2's complement method function Subtract(a, b) { var c; // ~b is the 1's Complement of b // adding 1 to it make it 2's Complement c = a + (~b + 1); return c; } // Driver code var a = 2, b = 3; document.write( Subtract(a, b) + "<br>" ); a = 9; b = 7; document.write( Subtract(a, b)); // This code is contributed by itsok </script> |
-1 2
Time complexity – O(nlog2(n))
Auxiliary Space – O(1)
Method 2: Basic Approach or Brute Force Approach
Subtraction of two Binary Numbers, subtract two binary numbers using 2’s Complement method.
Step-1: Find the 2’s complement of the subtrahend.
Step-2: Add the first number and 2’s complement of the subtrahend.
Step-3: If the carry is produced, discard the carry. If there is no carry then take the 2’s complement of the result.
Below is the implementation of the above approach.
C++
//C++ code for above approach #include<iostream> #include<bits/stdc++.h> using namespace std; // Program to subtract void Subtract( int n, int a[], int b[]) { // 1's Complement for ( int i = 0; i < n; i++) { //Replace 1 by 0 if (b[i] == 1) { b[i] = 0; } //Replace 0 by 1 else { b[i] = 1; } } //Add 1 at end to get 2's Complement for ( int i = n - 1; i >= 0; i--) { if (b[i] == 0) { b[i] = 1; break ; } else { b[i] = 0; } } // Represents carry int t = 0; for ( int i = n - 1; i >= 0; i--) { // Add a, b and carry a[i] = a[i] + b[i] + t; // If a[i] is 2 if (a[i] == 2) { a[i] = 0; t = 1; } // If a[i] is 3 else if (a[i] == 3) { a[i] = 1; t = 1; } else t = 0; } cout << endl; // If carry is generated // discard the carry if (t==1) { // print the result for ( int i = 0; i < n; i++) { // Print the result cout<<a[i]; } } // if carry is not generated else { // Calculate 2's Complement // of the obtained result for ( int i = 0; i < n; i++) { if (a[i] == 1) a[i] = 0; else a[i] = 1; } for ( int i = n - 1; i >= 0; i--) { if (a[i] == 0) { a[i] = 1; break ; } else a[i] = 0; } // Add -ve sign to represent cout << "-" ; // -ve result // Print the resultant array for ( int i = 0; i < n; i++) { cout << a[i]; } } } // Driver Code int main() { int n; n = 5; int a[] = {1, 0, 1, 0, 1}, b[] = {1, 1, 0, 1, 0}; Subtract(n,a,b); return 0; } |
Java
// Java code for above approach import java.io.*; class GFG{ // Program to subtract static void Subtract( int n, int a[], int b[]) { // 1's Complement for ( int i = 0 ; i < n; i++) { // Replace 1 by 0 if (b[i] == 1 ) { b[i] = 0 ; } // Replace 0 by 1 else { b[i] = 1 ; } } // Add 1 at end to get 2's Complement for ( int i = n - 1 ; i >= 0 ; i--) { if (b[i] == 0 ) { b[i] = 1 ; break ; } else { b[i] = 0 ; } } // Represents carry int t = 0 ; for ( int i = n - 1 ; i >= 0 ; i--) { // Add a, b and carry a[i] = a[i] + b[i] + t; // If a[i] is 2 if (a[i] == 2 ) { a[i] = 0 ; t = 1 ; } // If a[i] is 3 else if (a[i] == 3 ) { a[i] = 1 ; t = 1 ; } else t = 0 ; } System.out.println(); // If carry is generated // discard the carry if (t == 1 ) { // Print the result for ( int i = 0 ; i < n; i++) { // Print the result System.out.print(a[i]); } } // If carry is not generated else { // Calculate 2's Complement // of the obtained result for ( int i = 0 ; i < n; i++) { if (a[i] == 1 ) a[i] = 0 ; else a[i] = 1 ; } for ( int i = n - 1 ; i >= 0 ; i--) { if (a[i] == 0 ) { a[i] = 1 ; break ; } else a[i] = 0 ; } // Add -ve sign to represent System.out.print( "-" ); // -ve result // Print the resultant array for ( int i = 0 ; i < n; i++) { System.out.print(a[i]); } } } // Driver Code public static void main (String[] args) { int n; n = 5 ; int a[] = { 1 , 0 , 1 , 0 , 1 }; int b[] = { 1 , 1 , 0 , 1 , 0 }; Subtract(n, a, b); } } // This code is contributed by avanitrachhadiya2155 |
Python3
# Python implementation of above approach # Program to subtract def Subtract(n, a, b): # 1's Complement for i in range (n): # Replace 1 by 0 if (b[i] = = 1 ): b[i] = 0 # Replace 0 by 1 else : b[i] = 1 # Add 1 at end to get 2's Complement for i in range (n - 1 , - 1 , - 1 ): if (b[i] = = 0 ): b[i] = 1 break else : b[i] = 0 # Represents carry t = 0 for i in range (n - 1 , - 1 , - 1 ): # Add a, b and carry a[i] = a[i] + b[i] + t # If a[i] is 2 if (a[i] = = 2 ): a[i] = 0 t = 1 # If a[i] is 3 elif (a[i] = = 3 ): a[i] = 1 t = 1 else : t = 0 print () # If carry is generated # discard the carry if (t = = 1 ): # Print the result for i in range (n): # Print the result print (a[i],end = "") # If carry is not generated else : # Calculate 2's Complement # of the obtained result for i in range (n): if (a[i] = = 1 ): a[i] = 0 else : a[i] = 1 for i in range (n - 1 , - 1 , - 1 ): if (a[i] = = 0 ): a[i] = 1 break else : a[i] = 0 # Add -ve sign to represent print ( "-" ,end = "") # -ve result # Print the resultant array for i in range (n): print (a[i],end = "") # Driver Code n = 5 a = [ 1 , 0 , 1 , 0 , 1 ] b = [ 1 , 1 , 0 , 1 , 0 ] Subtract(n, a, b) # This code is contributed by shinjanpatra |
C#
// C# code for above approach using System; class GFG{ // Program to subtract static void Subtract( int n, int [] a, int [] b) { // 1's Complement for ( int i = 0; i < n; i++) { // Replace 1 by 0 if (b[i] == 1) { b[i] = 0; } // Replace 0 by 1 else { b[i] = 1; } } // Add 1 at end to get 2's Complement for ( int i = n - 1; i >= 0; i--) { if (b[i] == 0) { b[i] = 1; break ; } else { b[i] = 0; } } // Represents carry int t = 0; for ( int i = n - 1; i >= 0; i--) { // Add a, b and carry a[i] = a[i] + b[i] + t; // If a[i] is 2 if (a[i] == 2) { a[i] = 0; t = 1; } // If a[i] is 3 else if (a[i] == 3) { a[i] = 1; t = 1; } else t = 0; } Console.WriteLine(); // If carry is generated // discard the carry if (t == 1) { // Print the result for ( int i = 0; i < n; i++) { // Print the result Console.Write(a[i]); } } // If carry is not generated else { // Calculate 2's Complement // of the obtained result for ( int i = 0; i < n; i++) { if (a[i] == 1) a[i] = 0; else a[i] = 1; } for ( int i = n - 1; i >= 0; i--) { if (a[i] == 0) { a[i] = 1; break ; } else a[i] = 0; } // Add -ve sign to represent Console.Write( "-" ); // -ve result // Print the resultant array for ( int i = 0; i < n; i++) { Console.Write(a[i]); } } } // Driver Code static public void Main() { int n; n = 5; int [] a = {1, 0, 1, 0, 1}; int [] b = {1, 1, 0, 1, 0}; Subtract(n, a, b); } } // This code is contributed by rag2127 |
Javascript
<script> // Javascript code for above approach // Program to subtract function Subtract(n,a,b) { // 1's Complement for (let i = 0; i < n; i++) { // Replace 1 by 0 if (b[i] == 1) { b[i] = 0; } // Replace 0 by 1 else { b[i] = 1; } } // Add 1 at end to get 2's Complement for (let i = n - 1; i >= 0; i--) { if (b[i] == 0) { b[i] = 1; break ; } else { b[i] = 0; } } // Represents carry let t = 0; for (let i = n - 1; i >= 0; i--) { // Add a, b and carry a[i] = a[i] + b[i] + t; // If a[i] is 2 if (a[i] == 2) { a[i] = 0; t = 1; } // If a[i] is 3 else if (a[i] == 3) { a[i] = 1; t = 1; } else t = 0; } document.write( "<br>" ); // If carry is generated // discard the carry if (t == 1) { // Print the result for (let i = 0; i < n; i++) { // Print the result document.write(a[i]); } } // If carry is not generated else { // Calculate 2's Complement // of the obtained result for (let i = 0; i < n; i++) { if (a[i] == 1) a[i] = 0; else a[i] = 1; } for (let i = n - 1; i >= 0; i--) { if (a[i] == 0) { a[i] = 1; break ; } else a[i] = 0; } // Add -ve sign to represent document.write( "-" ); // -ve result // Print the resultant array for (let i = 0; i < n; i++) { document.write(a[i]); } } } // Driver Code let n = 5; let a=[1, 0, 1, 0, 1]; let b=[1, 1, 0, 1, 0]; Subtract(n, a, b); // This code is contributed by patel2127 </script> |
-00101
Time complexity : O(N)
Auxiliary Space : O(1)