Given two non-negative integers a and b. The problem is to check if one of the two numbers is 1’s complement of the other.
The ones’ complement of a binary number is defined as the value obtained by inverting all the bits in the binary representation of the number (swapping 0s for 1s and vice versa).
Examples:
Input : a = 10, b = 5 Output : Yes (10)10 = (1010)2 1's complement of 10 is = (0101)2 = (101)2 = (5)10 Input : a = 1, b = 14 Output : Yes (14)10 = (1110)2 1's complement of 14 is = (0001)2 = (1)2 = (1)10
Approach: Following are the steps:
- Calculate n = a ^ b.
- Check whether all bits are set in the binary representation of n. Refer to this post.
CPP
// C++ implementation to check if one of the two // numbers is one's complement of the other #include <bits/stdc++.h> using namespace std; // function to check if all the bits are set // or not in the binary representation of 'n' bool areAllBitsSet(unsigned int n) { // all bits are not set if (n == 0) return false; // if true, then all bits are set if (((n + 1) & n) == 0) return true; // else all bits are not set return false; } // function to check if one of the two numbers // is one's complement of the other bool isOnesComplementOfOther(unsigned int a, unsigned int b) { return areAllBitsSet(a ^ b); } // Driver program to test above int main() { unsigned int a = 10, b = 5; if (isOnesComplementOfOther(a,b)) cout << "Yes"; else cout << "No"; return 0; } |
Java
// Java implementation to // check if one of the two // numbers is one's complement // of the other import java.util.*; import java.lang.*; public class GfG{ // function to check // if all the bits are set // or not in the binary // representation of 'n' public static boolean areAllBitsSet(long n) { // all bits are not set if (n == 0) return false; // if true, then all bits are set if (((n + 1) & n) == 0) return true; // else all bits are not set return false; } // function to check if // one of the two numbers // is one's complement // of the other public static boolean isOnesComplementOfOther(long a, long b) { return areAllBitsSet(a ^ b); } // Driver function public static void main(String argc[]){ long a = 10, b = 5; if (isOnesComplementOfOther(a,b)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by Sagar Shukla |
Python3
# Python3 implementation to # check if one of the two # numbers is one's complement # of the other # function to check if # all the bits are set # or not in the binary # representation of 'n' def areAllBitsSet(n): # all bits are not set if (n == 0): return False; # if True, then all bits are set if (((n + 1) & n) == 0): return True; # else all bits are not set return False; # function to check if one # of the two numbers is # one's complement of the other def isOnesComplementOfOther(a, b): return areAllBitsSet(a ^ b) # Driver program a = 1b = 14if (isOnesComplementOfOther(a, b)): print ("Yes") else: print ("No") # This code is contributed by # Saloni Gupta 4 |
C#
// C# implementation to check // if one of the two numbers is // one's complement of the other using System; class GFG { // function to check // if all the bits are set // or not in the binary // representation of 'n' public static bool areAllBitsSet(long n) { // all bits are not set if (n == 0) return false; // if true, then all bits are set if (((n + 1) & n) == 0) return true; // else all bits are not set return false; } // function to check if // one of the two numbers // is one's complement // of the other public static bool isOnesComplementOfOther(long a, long b) { return areAllBitsSet(a ^ b); } // Driver function public static void Main() { long a = 10, b = 5; if (isOnesComplementOfOther(a, b)) Console.Write("Yes"); else Console.Write("No"); } } // This code is contributed by Sam007 |
PHP
<?php // PHP implementation to // check if one of the two // numbers is one's complement // of the other // function to check if // all the bits are set // or not in the binary // representation of 'n' function areAllBitsSet($n) { // all bits are not set if ($n == 0) return false; // if true, then all // bits are set if ((($n + 1) & $n) == 0) return true; // else all bits // are not set return false; } // function to check if // one of the two numbers // is one's complement of // the other function isOnesComplementOfOther($a, $b) { return areAllBitsSet($a ^ $b); } // Driver Code $a = 10; $b = 5; if (isOnesComplementOfOther($a, $b)) echo "Yes"; else echo "No"; // This code is contributed by anuj_67. ?> |
Javascript
<script> // Javascript implementation to // check if one of the two // numbers is one's complement // of the other // function to check // if all the bits are set // or not in the binary // representation of 'n' function areAllBitsSet(n) { // all bits are not set if (n == 0) return false; // if true, then all bits are set if (((n + 1) & n) == 0) return true; // else all bits are not set return false; } // function to check if // one of the two numbers // is one's complement // of the other function isOnesComplementOfOther(a, b) { return areAllBitsSet(a ^ b); } // Driver code let a = 10, b = 5; if (isOnesComplementOfOther(a,b)) document.write("Yes"); else document.write("No"); </script> |
Output:
Yes
Time Complexity : O(1)
Auxiliary Space : O(1)
If you like neveropen and would like to contribute, you can also write an article using contribute.neveropen.co.za or mail your article to review-team@neveropen.co.za. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
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!
