等和与异或-yiteyi-C++库

给定一个正整数n，求正整数i的计数，使0<=i<=n，n+i=n^i

null

例如：

Input  : n = 7Output : 1Explanation:7^i = 7+i holds only for only for i = 07+0 = 7^0 = 7Input: n = 12Output: 412^i = 12+i hold only for i = 0, 1, 2, 3for i=0, 12+0 = 12^0 = 12for i=1, 12+1 = 12^1 = 13for i=2, 12+2 = 12^2 = 14for i=3, 12+3 = 12^3 = 15

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

方法1（简单）： 一个简单的解决方案是迭代i0<=i<=n的所有值，并计算所有满足的值。

C++

                         /* C++ program to print count of values such                       
                                                 that n+i = n^i */                       
                         #include <iostream>                       
                         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                       
                         // 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>                       

输出：

时间复杂性： O（n）

空间复杂性： O（1）

方法2（高效）： 一个有效的解决方案如下

我们知道（n+i）=（n^i）+2*（n&i）所以n+i=n^i意味着n&i=0 因此，我们的问题归结为寻找i的值，使得n&i=0。如何找到这样的配对数？我们可以在n的二进制表示中使用未设置位的计数。对于n&i为零，我必须取消设置n的所有设置位。如果第k位设置在n中的某个特定位置，则第k位在i中必须始终为0，否则第k位可以为0或1 因此，此类组合的总数为2^（n中未设置位的计数）例如，考虑n＝12（二进制表示：1、1、0、0）。可以取消n的所有位的i的所有可能值都是0/10/1，其中0/1表示0或1。i的此类值的数量为2^2=4。

以下是遵循上述理念的节目。

C++

                         /* c++ program to print count of values such                       
                                                 that n+i = n^i */                       
                         #include <bits/stdc++.h>                       
                         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                       
                         /* 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>                       

输出：

时间复杂性： O（对数（n））

空间复杂性： O（1）

本文由 Nikhil Chakravartula .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用写极客。组织或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章