Hallar el complemento a uno de un entero – Part 1

Dado un entero n, encuentra el complemento a uno del entero. 
Ejemplos: 
 

Input  : n = 5
Output : 2

Input  : n = 255
Output : 0

Input  : n = 26
Output : 5

Enfoque básico:

El enfoque ingenuo para resolver el problema sería convertir primero el número dado en su representación binaria y luego cambiar cada 1 a 0 y 0 a 1. Después de cambiar todos los 0 y 1, convierta la representación binaria en número.

Implementación del enfoque anterior:

// 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 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 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

// 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

9

Complejidad de tiempo: O (log n)

Espacio Auxiliar : O(log n)

Un enfoque eficiente para este problema es el siguiente: 
1. Encuentra el número de bits en el entero dado 
2. XOR el entero dado con 2^número_de_bits-1
 

// 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 poe(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 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 poe(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 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 poe(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# 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 poe(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 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
?>

<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 poe(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>

9

Complejidad de tiempo: O (log n)

Espacio Auxiliar : O(1)
 

 
Este artículo es una contribución de Amit SK . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.