Table of Contents
For the given binary number, print its 1`s and 2`s complement.
1`s complement of a binary is another binary with all its bits changed from 1 to 0 and 0 to 1.
2`s complement is 1 added to the 1`s complement of the binary number.
Examples
a) Input : 1010
Output : 1`s complement is 0101
2`s complement is 0110
b) Input : 1001
Output : 1`s complement is 0110
2`s complementis 0111
Time complexity : O(n)
Algorithm
1. Create a function flip which changes character to 0 if its 1 and 1 if its 0.
2. For 1`s complement,
a. Traverse the binary string.
b. For every character flip the string and add all of them.
3. For 2`s complement,
a. Traverse the 1`s complement.
b. If we get 1, we make them 0, keep going left.
c. If we get 0, make it 1 and end loop and return.
4. Print final 1`s complement and 2`s complement.
C++ Program
#include <bits/stdc++.h>
using namespace std;
//Function return '0' if '1', else return '0'
char flip(char c)
{
if (c == '0')
{
return '1';
}
else
{
return '0';
}
}
// Print 1's and 2's complement of binary number
// represented by "binary_string"
void PrintComplements(string binary_string)
{
int n = binary_string.length();
string ones, twos;
int i;
ones = twos = "";
//For 1`s complement flip all bits
for (i = 0; i < n; i++)
{
ones += flip(binary_string[i]);
}
//2`s complement
int k;
twos = ones;
for (k = n - 1;k >= 0;k--)
{
if (ones[k] == '1')//If its 1, make it 0 and move forward
{
twos[k] = '0';
}
else//If its 0, make it 1 and end loop
{
twos[k] = '1';
break;
}
}
//If no break, add one more one.
//Case: Adding 1 to 111 --> 1 + 111 = 1000
if(k == -1)
{
twos = '1' + twos;
}
cout<<"1's complement is: "<<ones<<endl;
cout<<"2's complement is: "<<twos<<endl;
}
//Main function
int main()
{
string binary_string = "1001";
cout<<"Input binary string is: "<<binary_string<<endl;
PrintComplements(binary_string);
return 0;
}