Given a binary string, task is to convert this string in to two’s complement with the help of XOR operator.
Examples:
Input : 00000101
Output :11111011Input : 10010
Output : 01110
We have discussed an approach in previous post to find 2’s complement
For 2’s complement, we first find one’s complement. We traverse the one’s complement starting from LSB (least significant bit), and look for 0. We flip all 1’s (change to 0) until we find a 0. Finally, we flip the found 0.
We traverse from the last bot and keep ignoring all 0s until we find a 1. We ignore first 1 also. Then we toggle all bits by doing XOR with 1.
C++
// C++ program to find 2's complement using XOR.#include <bits/stdc++.h>using namespace std;string TwoscomplementbyXOR(string str){ int n = str.length(); // A flag used to find if a 1 bit is seen // or not. bool check_bit = 0; for (int i = n - 1; i >= 0; i--) { if (str[i] == '0' && check_bit == 0) { continue; } else { // xor operator is used to flip the if (check_bit == 1) str[i] = (str[i] - '0') ^ 1 + '0'; // bits after converting in to // ASCII values check_bit = 1; } } // if there is no 1 in the string so just add // 1 in starting of string and return if (check_bit == 0) return "1" + str; else return str;}// Driver codeint main(){ string str = "101"; cout << TwoscomplementbyXOR(str); return 0;} |
Java
// Java program to find 2's complement using XOR.import java.util.*; class GFG{static void TwoscomplementbyXOR(String str){ int n = str.length(); // A flag used to find if a 1 bit is seen // or not. boolean check_bit = false; for(int i = n - 1; i >= 0; i--) { if (str.charAt(i) == '0' && check_bit == false) { continue; } else { // xor operator is used to flip the if (check_bit == true) { if (str.charAt(i) == '0') str = str.substring(0, i) + '1' + str.substring(i + 1); else str = str.substring(0, i) + '0' + str.substring(i + 1); } // bits after converting in to // ASCII values check_bit = true; } } // If there is no 1 in the string so just add // 1 in starting of string and return if (check_bit == false) { System.out.println("1" + str); } else System.out.println(str);}// Driver codepublic static void main(String[] args) { String str = "101"; TwoscomplementbyXOR(str);}}// This code is contributed by amreshkumar3 |
Python3
# Python program to find 2's complement using XOR.def TwoscomplementbyXOR(str): n = len(str) # A flag used to find if a 1 bit is seen # or not. check_bit = 0 i = n - 1 s = list(str) while (i >= 0): if (s[i] == '0' and check_bit == 0): continue else: # xor operator is used to flip the if (check_bit == 1): s[i] = chr((ord(s[i]) - 48) ^ 1 + 48) # bits after converting in to # ASCII values check_bit = 1 i -= 1 # if there is no 1 in the string so just add # 1 in starting of string and return str = "".join(s) if (check_bit == 0): return "1" + str else: return str# Driver codestr = "101"print(TwoscomplementbyXOR(str))# This code is contributed by subhammahato348. |
C#
// C# program to find 2's complement using XOR.using System;class GFG { static void TwoscomplementbyXOR(string str) { int n = str.Length; // A flag used to find if a 1 bit is seen // or not. bool check_bit = false; for(int i = n - 1; i >= 0; i--) { if (str[i] == '0' && check_bit == false) { continue; } else { // xor operator is used to flip the if (check_bit == true) { if (str[i] == '0') str = str.Substring(0, i) + '1' + str.Substring(i + 1); else str = str.Substring(0, i) + '0' + str.Substring(i + 1); } // bits after converting in to // ASCII values check_bit = true; } } // If there is no 1 in the string so just add // 1 in starting of string and return if (check_bit == false) { Console.WriteLine("1" + str); } else Console.WriteLine(str); } // Driver code static void Main() { string str = "101"; TwoscomplementbyXOR(str); }}// This code is contributed by divyeshrabadiya07. |
PHP
<?php// PHP program to find 2's complement // using XOR. function TwoscomplementbyXOR($str) { $n =strlen($str); // A flag used to find if a 1 // bit is seen or not. $check_bit = 0; for ($i = $n - 1; $i >= 0; $i--) { if ($str[$i] == '0' && $check_bit == 0) { continue; } else { // xor operator is used // to flip the if ($check_bit == 1) $str[$i] = ($str[$i] - '0') ^ 1 + '0'; // bits after converting in to // ASCII values $check_bit = 1; } } // if there is no 1 in the string // so just add 1 in starting of // string and return if ($check_bit == 0) return "1" + $str; else return $str; } // Driver code $str = "101"; echo TwoscomplementbyXOR($str); // This code is contributed by akt_mit?> |
Javascript
<script>// Javascript program to find 2's complement // using XOR. function TwoscomplementbyXOR(str) { let n = str.length; // A flag used to find if a 1 // bit is seen or not. let check_bit = 0; for (let i = n - 1; i >= 0; i--) { if (str[i] == '0' && check_bit == 0) { continue; } else { // xor operator is used // to flip the if (check_bit == 1) { if (str.charAt(i) == '0') str = str.substr(0, i) + '1' + str.substr(i + 1); else str = str.substr(0, i) + '0' + str.substr(i + 1); } // bits after converting in to // ASCII values check_bit = 1; } } // if there is no 1 in the string // so just add 1 in starting of // string and return if (check_bit == 0) return "1" + str; else return str;}// Driver code let str = "101";document.write(TwoscomplementbyXOR(str));// This code is contributed by _saurabh_jaiswal</script> |
Output:
011
Time complexity: O(n) where n is the length of the given string
Auxiliary space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
