寻找平价的程序-yiteyi-C++库

平价： 一个数字的奇偶性是指它是否包含奇数或偶数的1位。如果数字包含奇数个1位，则该数字具有“奇数奇偶校验”；如果数字包含偶数个1位，则该数字具有“偶数奇偶校验”。以下解决方案的主要思想是–在n不为0时循环，在循环中取消设置一个设定位并反转奇偶校验。

null

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

Algorithm: getParity(n)1. Initialize parity = 02. Loop while n != 0            a. Invert parity              parity = !parity      b. Unset rightmost set bit             n = n & (n-1)3. return parityExample: Initialize: n = 13 (1101)   parity = 0n = 13 & 12  = 12 (1100)   parity = 1n = 12 & 11 = 8  (1000)   parity = 0n = 8 & 7 = 0  (0000)    parity = 1

节目：

C++

                         // C++ program to find parity                       
                         // of an integer                       
                         # include<bits/stdc++.h>                       
                         # define bool int                       
                         using                                     namespace                                     std;                       
           
                         // Function to get parity of number n. It returns 1                       
                         // if n has odd parity, and returns 0 if n has even                       
                         // parity                       
                         bool                                     getParity(unsigned                                     int                                     n)                       
                         {                       
                                                 bool                                     parity = 0;                       
                                                 while                                     (n)                       
                                                 {                       
                                                 parity = !parity;                       
                                                 n     = n & (n - 1);                       
                                                 }                       
                                                 return                                     parity;                       
                         }                       
           
                         /* Driver program to test getParity() */                       
                         int                                     main()                       
                         {                       
                                                 unsigned                                     int                                     n = 7;                       
                                                 cout<<                                     "Parity of no "                                     <<n<<                                     " = "                                     <<(getParity(n)?                                     "odd"                                     :                                     "even"                                     );                       
                                   
                                                 getchar                                     ();                       
                                                 return                                     0;                       
                         }                       

C

                         // C program to find parity                       
                         // of an integer                       
                         # include <stdio.h>                       
                         # define  bool int                       
           
                         /* Function to get parity of number n. It returns 1                       
                                                 if n has odd parity, and returns 0 if n has even                       
                                                 parity */                       
                         bool                                     getParity(unsigned                                     int                                     n)                       
                         {                       
                                                 bool                                     parity = 0;                       
                                                 while                                     (n)                       
                                                 {                       
                                                 parity = !parity;                       
                                                 n      = n & (n - 1);                       
                                                 }                       
                                                 return                                     parity;                       
                         }                       
           
                         /* Driver program to test getParity() */                       
                         int                                     main()                       
                         {                       
                                                 unsigned                                     int                                     n = 7;                       
                                                 printf                                     (                                     "Parity of no %d = %s"                                     ,  n,                       
                                                 (getParity(n)?                                     "odd"                                     :                                     "even"                                     ));                       
                                   
                                                 getchar                                     ();                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to find parity                       
                         // of an integer                       
                         import                                     java.util.*;                       
                         import                                     java.lang.*;                       
                         import                                     java.io.*;                       
                         import                                     java.math.BigInteger;                       
           
                         class                                     GFG                       
                                                 {                       
                                                 /* Function to get parity of number n.                       
                                                 It returns 1 if n has odd parity, and                       
                                                 returns 0 if n has even parity */                       
                                                 static                                     boolean                                     getParity(                                     int                                     n)                       
                                                 {                       
                                                 boolean                                     parity =                                     false                                     ;                       
                                                 while                                     (n !=                                     0                                     )                       
                                                 {                       
                                                 parity = !parity;                       
                                                 n = n & (n-                                     1                                     );                       
                                                 }                       
                                                 return                                     parity;                       
                                   
                                                 }                       
                                   
                                                 /* Driver program to test getParity() */                       
                                                 public                                     static                                     void                                     main (String[] args)                       
                                                 {                       
                                                 int                                     n =                                     12                                     ;                       
                                                 System.out.println(                                     "Parity of no "                                     + n +                                     " = "                                     +                       
                                                 (getParity(n)?                                     "odd"                                     :                                     "even"                                     ));                       
                                                 }                       
                         }                       
                         /* This code is contributed by Amit khandelwal*/                       

蟒蛇3

                         # Python3 code to get parity.                       
           
                         # Function to get parity of number n.                       
                         # It returns 1 if n has odd parity,                       
                         # and returns 0 if n has even parity                       
                         def                                     getParity( n ):                       
                                                 parity                                     =                                     0                       
                                                 while                                     n:                       
                                                 parity                                     =                                     ~parity                       
                                                 n                                     =                                     n & (n                                     -                                     1                                     )                       
                                                 return                                     parity                       
           
                         # Driver program to test getParity()                       
                         n                                     =                                     7                       
                         print                                     (                                     "Parity of no "                                     , n,                                     " = "                                     ,                       
                                                 (                                     "odd"                                     if                                     getParity(n)                                     else                                     "even"                                     ))                       
           
                         # This code is contributed by "Sharad_Bhardwaj".                       

C#

                         // C# program to find parity of an integer                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 /* Function to get parity of number n.                       
                                                 It returns 1 if n has odd parity, and                       
                                                 returns 0 if n has even parity */                       
                                                 static                                     bool                                     getParity(                                     int                                     n)                       
                                                 {                       
                                                 bool                                     parity =                                     false                                     ;                       
                                                 while                                     (n != 0)                       
                                                 {                       
                                                 parity = !parity;                       
                                                 n = n & (n-1);                       
                                                 }                       
                                                 return                                     parity;                       
                                   
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main ()                       
                                                 {                       
                                                 int                                     n = 7;                       
                                                 Console.Write(                                     "Parity of no "                                     + n                       
                                                 +                                     " = "                                     + (getParity(n)?                       
                                                 "odd"                                     :                                     "even"                                     ));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       

PHP

                         <?php                       
                         // PHP program to find the parity                       
                         // of an unsigned integer                       
           
                         // Function to get parity of                       
                         // number n. It returns 1                       
                         // if n has odd parity, and                       
                         // returns 0 if n has even                       
                         // parity                       
                         function                                     getParity(                                     $n                                     )                       
                         {                       
                                                 $parity                                     = 0;                       
                                                 while                                     (                                     $n                                     )                       
                                                 {                       
                                                 $parity                                     = !                                     $parity                                     ;                       
                                                 $n                                     =                                     $n                                     & (                                     $n                                     - 1);                       
                                                 }                       
                                                 return                                     $parity                                     ;                       
                         }                       
           
                                                 // Driver Code                       
                                                 $n                                     = 7;                       
                                                 echo                                     "Parity of no "                                     ,                                     $n                                     ,                                     " = "                                     ,                       
                                                 getParity(                                     $n                                     )?                                     "odd"                                     :                                     "even"                                     ;                       
                                   
                         // This code is contributed by anuj_67.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // Javascript program to find parity                       
                         // of an integer                       
           
                         // Function to get parity of number n.                       
                         // It returns 1 if n has odd parity, and                       
                         // returns 0 if n has even parity                       
                         function                                     getParity(n)                       
                         {                       
                                                 var                                     parity =                                     false                                     ;                       
                                                 while                                     (n != 0)                       
                                                 {                       
                                                 parity = !parity;                       
                                                 n = n & (n - 1);                       
                                                 }                       
                                                 return                                     parity;                       
                         }                       
                                   
                         // Driver code                       
                         var                                     n = 7;                       
                         document.write(                                     "Parity of no "                                     + n +                                     " = "                                     +                       
                                                 (getParity(n) ?                                     "odd"                                     :                                     "even"                                     ));                       
                                   
                         // This code is contributed by Kirti                       
           
                         </script>                       

输出：

Parity of no 7 = odd

上述解决方案可以通过使用查找表进行优化。详情请参考Bit Twiddle Hacks[First reference]。 时间复杂性： 上述算法所用的时间与设置的位数成正比。最坏情况的复杂度是O（logn）。

辅助空间： O（1） 使用： 奇偶校验用于错误检测和加密。 使用XOR和查表计算数字的奇偶校验 参考资料： http://graphics.stanford.edu/~seander/bithacks。html#ParityNaive -上次检查日期为2009年5月30日。

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

THE END

技术文章