logo

TechCodeview

등합 및 XOR

GfG Practice에서 사용해 보세요. ' title= #practiceLinkDiv { 표시: 없음 !중요; }

양의 정수 n이 주어지면 0이 되는 양의 정수 i의 개수를 찾습니다.<= i <= n and n+i = n^i 

예:  

  Input :   n = 7   Output   : 1   Explanation:   7^i = 7+i holds only for only for i = 0 7+0 = 7^0 = 7   Input:   n = 12   Output:   4 12^i = 12+i hold only for i = 0 1 2 3 for i=0 12+0 = 12^0 = 12 for i=1 12+1 = 12^1 = 13 for i=2 12+2 = 12^2 = 14 for i=3 12+3 = 12^3 = 15
Recommended Practice 등합 및 XOR 시도해 보세요!

방법 1(간단):  
한 가지 간단한 해결책은 i 0의 모든 값을 반복하는 것입니다.<= i <= n and count all satisfying values.  



C++ 
/* C++ program to print count of values such  that n+i = n^i */ #include    using namespace std; // function to count number of values less than // equal to n that satisfy the given condition int countValues (int n) {  int countV = 0;  // Traverse all numbers from 0 to n and  // increment result only when given condition  // is satisfied.  for (int i=0; i<=n; i++ )  if ((n+i) == (n^i) )  countV++;  return countV; } // Driver program int main() {  int n = 12;  cout << countValues(n);  return 0; }
Java 
/* Java program to print count of values  such that n+i = n^i */ import java.util.*; class GFG {    // function to count number of values   // less than equal to n that satisfy  // the given condition  public static int countValues (int n)  {  int countV = 0;    // Traverse all numbers from 0 to n   // and increment result only when   // given condition is satisfied.  for (int i = 0; i <= n; i++ )  if ((n + i) == (n ^ i) )  countV++;    return countV;  }    /* Driver program to test above function */  public static void main(String[] args)   {  int n = 12;  System.out.println(countValues(n));    } } // This code is contributed by Arnav Kr. Mandal.
Python3 
# Python3 program to print count # of values such that n+i = n^i # function to count number # of values less than # equal to n that satisfy  # the given condition def countValues (n): countV = 0; # Traverse all numbers # from 0 to n and # increment result only # when given condition # is satisfied. for i in range(n + 1): if ((n + i) == (n ^ i)): countV += 1; return countV; # Driver Code n = 12; print(countValues(n)); # This code is contributed by mits
C# 
/* C# program to print count of values such that n+i = n^i */ using System; class GFG {    // function to count number of values   // less than equal to n that satisfy  // the given condition  public static int countValues (int n)  {  int countV = 0;    // Traverse all numbers from 0 to n   // and increment result only when   // given condition is satisfied.  for (int i = 0; i <= n; i++ )  if ((n + i) == (n ^ i) )  countV++;    return countV;  }    /* Driver program to test above function */  public static void Main()   {  int n = 12;  Console.WriteLine(countValues(n));    } } // This code is contributed by anuj_67.
PHP 
 // PHP program to print count // of values such that n+i = n^i // function to count number // of values less than // equal to n that satisfy  // the given condition function countValues ($n) { $countV = 0; // Traverse all numbers // from 0 to n and // increment result only // when given condition // is satisfied. for ($i = 0; $i <= $n; $i++ ) if (($n + $i) == ($n^$i) ) $countV++; return $countV; } // Driver Code $n = 12; echo countValues($n); // This code is contributed by m_kit ?>
JavaScript 
<script> /* JavaScript program to print count of values such that n+i = n^i */ // function to count number of values less than // equal to n that satisfy the given condition function countValues (n) {  let countV = 0;  // Traverse all numbers from 0 to n and  // increment result only when given condition  // is satisfied.  for (let i=0; i<=n; i++ )  if ((n+i) == (n^i) )  countV++;  return countV; } // Driver program  let n = 12;  document.write(countValues(n)); // This code is contributed by Surbhi Tyagi. </script>

산출:  

4

시간 복잡도: 에)

공간 복잡도: 오(1)

방법 2(효율적): 
효율적인 솔루션은 다음과 같습니다

우리는 (n+i)=(n^i)+2*(n&i)를 알고 있습니다.
따라서 n + i = n ^ i는 n & i = 0을 의미합니다.
따라서 우리의 문제는 n & i = 0인 i 값을 찾는 것으로 줄어듭니다. 그러한 쌍의 개수를 찾는 방법은 무엇입니까? n의 이진 표현에서 설정되지 않은 비트 수를 사용할 수 있습니다. n & i가 0이 되려면 n의 모든 세트 비트를 설정 해제해야 합니다. k번째 비트가 n의 특정 위치에 설정되면 i의 k번째 비트는 항상 0이어야 하며, 그렇지 않으면 i의 k번째 비트는 0 또는 1이 될 수 있습니다.
따라서 그러한 총 조합은 2^(n에서 설정되지 않은 비트 수)입니다.
예를 들어 n = 12(이진 표현: 1 1 0 0)을 고려하세요. 
n의 모든 비트를 설정 해제할 수 있는 i의 가능한 모든 값은 0 0 0/1 0/1입니다. 여기서 0/1은 0 또는 1을 의미합니다. i의 해당 값의 수는 2^2 = 4입니다. 

다음은 위의 아이디어를 따른 프로그램입니다.  

C++ 
/* c++ program to print count of values such  that n+i = n^i */ #include    using namespace std; // function to count number of values less than // equal to n that satisfy the given condition int countValues(int n) {  // unset_bits keeps track of count of un-set  // bits in binary representation of n  int unset_bits=0;  while (n)  {  if ((n & 1) == 0)  unset_bits++;  n=n>>1;  }  // Return 2 ^ unset_bits  return 1 << unset_bits; } // Driver code int main() {  int n = 12;  cout << countValues(n);  return 0; }
Java 
/* Java program to print count of values  such that n+i = n^i */ import java.util.*; class GFG {    // function to count number of values   // less than equal to n that satisfy   // the given condition  public static int countValues(int n)  {  // unset_bits keeps track of count  // of un-set bits in binary   // representation of n  int unset_bits=0;  while (n > 0)  {  if ((n & 1) == 0)  unset_bits++;  n=n>>1;  }    // Return 2 ^ unset_bits  return 1 << unset_bits;  }    /* Driver program to test above  function */  public static void main(String[] args)   {  int n = 12;  System.out.println(countValues(n));    } }   // This code is contributed by Arnav Kr. Mandal.
C# 
/* C# program to print count of values  such that n+i = n^i */ using System; public class GFG {    // function to count number of values   // less than equal to n that satisfy   // the given condition  public static int countValues(int n)  {    // unset_bits keeps track of count  // of un-set bits in binary   // representation of n  int unset_bits=0;  while (n > 0)  {  if ((n & 1) == 0)  unset_bits++;  n=n>>1;  }    // Return 2 ^ unset_bits  return 1 << unset_bits;  }    /* Driver program to test above  function */  public static void Main(String[] args)   {  int n = 12;  Console.WriteLine(countValues(n));    } } // This code is contributed by umadevi9616
Python3 
# Python3 program to print count of values such  # that n+i = n^i  # function to count number of values less than  # equal to n that satisfy the given condition  def countValues(n): # unset_bits keeps track of count of un-set  # bits in binary representation of n unset_bits = 0 while(n): if n & 1 == 0: unset_bits += 1 n = n >> 1 # Return 2 ^ unset_bits  return 1 << unset_bits # Driver code  if __name__=='__main__': n = 12 print(countValues(n)) # This code is contributed by rutvik
PHP 
 /* PHP program to print count  of values such that n+i = n^i */ // function to count number of  // values less than equal to n  // that satisfy the given  // condition function countValues( $n) { // unset_bits keeps track  // of count of un-set bits  // in binary representation // of n $unset_bits = 0; while ($n) { if (($n & 1) == 0) $unset_bits++; $n = $n >> 1; } // Return 2 ^ unset_bits return 1 << $unset_bits; } // Driver code $n = 12; echo countValues($n); // This code is contributed // by Anuj_67. ?>
JavaScript 
<script> // Javascript program to print count of values // such that n+i = n^i // Function to count number of values // less than equal to n that satisfy // the given condition function countValues(n) {    // unset_bits keeps track of count  // of un-set bits in binary  // representation of n  let unset_bits = 0;    while (n > 0)  {  if ((n & 1) == 0)  unset_bits++;    n = n >> 1;  }    // Return 2 ^ unset_bits  return 1 << unset_bits; }   // Driver Code let n = 12; document.write(countValues(n));   // This code is contributed by susmitakundugoaldanga   </script>

출력 :  

4

시간 복잡도: O(로그(n))

공간 복잡도: 오(1)

https://www.youtube.com/watch?v=zhu605v9KOI&feature=youtu.be