Check if one of the numbers is one’s complement of the other
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 = 1 b = 14 if (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)