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 (単純) :  
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 をゼロにするには、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(log(n))

空間の複雑さ: ○(1)

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