Find One’s Complement of an Integer
Given an integer n, find the one’s complement of the integer.
Examples:
Input : n = 5 Output : 2 Input : n = 255 Output : 0 Input : n = 26 Output : 5
Basic Approach :
The naïve approach to solve the problem would be to first convert the given number into its binary representation and then change every 1’s to 0 and 0’s to 1. After changing all 0’s and 1’s convert the binary representation to number.
Implementation of the above approach :
C++
// CPP program to find 1's complement of n. #include <bits/stdc++.h> using namespace std; unsigned int onesComplement(unsigned int n) { vector< int > v; // convert to binary representation while (n != 0) { v.push_back(n % 2); n = n / 2; } reverse(v.begin(), v.end()); // change 1's to 0 and 0's to 1 for ( int i = 0; i < v.size(); i++) { if (v[i] == 0) v[i] = 1; else v[i] = 0; } // convert back to number representation int two = 1; for ( int i = v.size() - 1; i >= 0; i--) { n = n + v[i] * two; two = two * 2; } return n; } int main() { unsigned int n = 22; cout << onesComplement(n); return 0; } |
Java
// Java program to find 1's complement of n. import java.util.*; class GFG { static int onesComplement( int n) { ArrayList<Integer> v = new ArrayList<Integer>(); // convert to binary representation while (n != 0 ) { v.add(n % 2 ); n = n / 2 ; } Collections.reverse(v); // change 1's to 0 and 0's to 1 for ( int i = 0 ; i < v.size(); i++) { if (v.get(i) == 0 ) v.set(i, 1 ); else v.set(i, 0 ); } // convert back to number representation int two = 1 ; for ( int i = v.size() - 1 ; i >= 0 ; i--) { n = n + v.get(i) * two; two = two * 2 ; } return n; } // Driver code public static void main(String[] args) { int n = 22 ; // Function call System.out.println(onesComplement(n)); } } // This code is contributed by phasing17 |
Python3
# Python3 program to find 1's complement of n. def onesComplement(n): v = [] # convert to binary representation while (n ! = 0 ): v.append(n % 2 ) n = n / / 2 v.reverse() # change 1's to 0 and 0's to 1 for i in range ( len (v)): if (v[i] = = 0 ): v[i] = 1 else : v[i] = 0 # convert back to number representation two = 1 for i in range ( len (v) - 1 , - 1 , - 1 ): n = n + v[i] * two two = two * 2 return n # Driver code n = 22 # Function call print (onesComplement(n)) # This code is contributed by phasing17 |
C#
// C# program to find 1's complement of n. using System; using System.Collections; public class GFG{ public static int onesComplement( int n) { ArrayList v = new ArrayList(); // convert to binary representation while (n != 0) { v.Add(n % 2); n = n / 2; } v.Reverse(); // change 1's to 0 and 0's to 1 for ( int i = 0; i < v.Count; i++) { if (Convert.ToInt32(v[i]) == 0) v[i]= 1; else v[i]= 0; } // convert back to number representation int two = 1; for ( int i = v.Count - 1; i >= 0; i--) { n = n + Convert.ToInt32(v[i]) * two; two = two * 2; } return n; } // Driver code static public void Main (){ int n = 22; // Function call Console.WriteLine(onesComplement(n)); } } // This code is contributed by Pushpesh Raj. |
Javascript
// JavaScript program to find 1's complement of n. function onesComplement(n) { let v = []; // convert to binary representation while (n != 0) { v.push(n % 2); n = Math.floor(n / 2); } v.reverse(); // change 1's to 0 and 0's to 1 for ( var i = 0; i < v.length; i++) { if (v[i] == 0) v[i] = 1; else v[i] = 0; } // convert back to number representation let two = 1; for (let i = v.length - 1; i >= 0; i--) { n = n + v[i] * two; two = two * 2; } return n; } // Driver code let n = 22; console.log(onesComplement(n)); // This code is contributed by phasing17 |
Output
9
Time Complexity : O(log n)
Auxiliary Space : O(log n)
An efficient approach to this problem is as follows:
1. Find the number of bits in the given integer
2. XOR the given integer with 2^number_of_bits-1
C++
// CPP program to find 1's complement of n. #include <bits/stdc++.h> using namespace std; unsigned int onesComplement(unsigned int n) { // Find number of bits in the given integer int number_of_bits = floor (log2(n)) + 1; // XOR the given integer with pow(2,number_of_bits-1) // and print the result return ((1 << number_of_bits) - 1) ^ n; } int main() { unsigned int n = 22; cout << onesComplement(n); return 0; } |
Java
// Java program to find 1's complement of n. class GFG { static int onesComplement( int n) { // Find number of bits in the // given integer int number_of_bits = ( int )(Math.floor(Math.log(n) / Math.log( 2 ))) + 1 ; // XOR the given integer with pow(2, // number_of_bits-1 and print the result return (( 1 << number_of_bits) - 1 ) ^ n; } // Driver code public static void main(String[] args) { int n = 22 ; System.out.print(onesComplement(n)); } } // This code is contributed by Anant Agarwal. |
Python3
# Python3 program to find # 1's complement of n. import math def onesComplement(n): # Find number of bits in # the given integer number_of_bits = ( int )(math.floor(math.log(n) / math.log( 2 ))) + 1 # XOR the given integer with pow(2, # number_of_bits-1 and print the result return (( 1 << number_of_bits) - 1 ) ^ n # Driver code n = 22 print (onesComplement(n)) # This code is contributed by Anant Agarwal. |
C#
// C# program to find 1's complement of n. using System; class GFG { static int onesComplement( int n) { // Find number of bits in the given integer int number_of_bits = ( int )(Math.Floor(Math.Log(n) / Math.Log(2))) + 1; // XOR the given integer with pow(2, // number_of_bits-1 and print the result return ((1 << number_of_bits) - 1) ^ n; } // Driver code public static void Main() { int n = 22; Console.WriteLine(onesComplement(n)); } } // This code is contributed by Anant Agarwal. |
PHP
<?php // PHP program to find 1's // complement of n. function Log2( $x ) { return (log10( $x ) / log10(2)); } function onesComplement( $n ) { // Find number of bits in // the given integer $number_of_bits = floor (log2( $n )) + 1; // XOR the given integer with // number_of_bits-1 and print the result return ((1 << $number_of_bits ) - 1) ^ $n ; } // Driver Code $n = 22; echo onesComplement( $n ); // This code is contributed by ihritik ?> |
Javascript
<script> // Javascript program to find // 1's complement of n. // Function to check whether a // number is power of 2 or not function onesComplement(n) { // Find number of bits in the // given integer let number_of_bits = (Math.floor(Math.log(n) / Math.log(2))) + 1; // XOR the given integer with pow(2, // number_of_bits-1 and print the result return ((1 << number_of_bits) - 1) ^ n; } // driver program let n = 22; document.write(onesComplement(n)); </script> |
Output
9
Time Complexity : O(log n)
Auxiliary Space : O(1)