2's complement for a given string using XOR
Last Updated : 21 Sep, 2022
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 :11111011
Input : 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 code int main() { string str = "101"; cout << TwoscomplementbyXOR(str); return 0; } // 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 code public static void main(String[] args) { String str = "101"; TwoscomplementbyXOR(str); } } // This code is contributed by amreshkumar3 # 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 code str = "101" print(TwoscomplementbyXOR(str)) # This code is contributed by subhammahato348.
// 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 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 ?> <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> Time complexity: O(n) where n is the length of the given string
Auxiliary space: O(1)
Similar Reads
XOR of all substrings of a given Binary String Given a binary string str of size N, the task is to calculate the bitwise XOR of all substrings of str. Examples: Input: str = "11"Output: 11Explanation: The substrings of "11" are: 1, 1, and 11.Their XOR = 1 ⊕ 1 ⊕ 11 = 11 Input: str = "110"Output: 111Explanation: The substrings of 110 are: 1, 1, 0,
6 min read
Efficient method for 2's complement of a binary string Given a Binary Number as string, print its 2's complements.2’s complement of a binary number is 1 added to the 1’s complement of the binary number. Note that 1's complement is simply flip of given binary number. Examples: 2's complement of "0111" is "1001" 2's complement of "1100" is "0100" We stron
6 min read
Find One’s Complement of an Integer | Set 2 Given an integer N, find the one’s complement of the integer. Examples: Input: N = 5Output: 2Explanation: Binary representation of 5 is "101". Its one's complement is "010" = 2. Input: N = 255Output: 0 Input: N = 26Output: 5 Approach: Already the XOR-based approach and converting the number to binar
3 min read
String transformation using XOR and OR Given two binary strings. The task is to check if string s1 can be converted to string s2 by performing the given operations any number of times. Choose any two adjacent characters in a string s1 and replace one of them by a^b and the other by a \oplus b (a OR b). Examples: Input: S1 = "11", S2 = "1
7 min read
Longest Common Substring with max XOR Given two strings s1 and s2, the task is to find the length of the longest common substring of s1 and s2 such that the XOR is maximum. Examples: Input: s1 = "79567", s2 = "56779"Output: 2Explanation: The longest common substring with a max XOR is "79", which has an XOR of 14 and a length is 2. Input
8 min read
String obtained by reversing and complementing a Binary string K times Given a binary string of size N and an integer K, the task is to perform K operations upon the string and print the final string: If the operation number is odd, then reverse the string,If the operation number even, then complement the string. Examples: Input: str = "1011", K = 2 Output: 0010 After
6 min read