algorithm - 一种简单/按位计算位奇偶校验的方法

在我的例子中，奇偶性定义为：
相邻的0，1置换的数目，使所有0都向左，所有1都向右。
注意，1,1的置换和0,0的置换不计算在内。当置换数为偶数时，奇偶称为偶数，否则为奇数。
举几个例子：
'101'奇数
1000多
“10011”偶数
10100多

最佳答案

首先，注意相邻0-1置换的最小数目是inversions的数目：它是0-1对的数目，因此0代表1的右边。
设（ki）为所有设定位（即等于1的位）位置的排序序列。位置从零开始计数，从右边开始计数（即从低位开始）。然后在第i个设置位的右边有ki-i零位（我从零开始计数）。因此，逆的总数是所有集合位上的和（Ki）-和（i）。
第一部分很容易处理如果ki是偶数，丢弃它。如果Ki是奇数，它会切换和的奇偶性所以实际上和的奇偶性（Ki）等于奇数位的集合位数的奇偶性这个数字很容易找到：首先屏蔽所有偶数位，然后计算设置位的数目（使用popcount）。
第二部分也很容易处理。首先，计算你的数字中的设置位数（再次使用popcount）设它为n，现在k=0的和，n-1正好是（n-1）*n/2。注意，当且仅当数字n中的第二位（从这里的一位开始计数）被设置时，它才是奇数所以只要你得到n，你只需要提取它的第二位。
下面是C++中的结果代码：

uint32_t get_inversions_parity(uint32_t x) {
    uint32_t bitsCnt = popcount(x);
    uint32_t oddCnt = popcount(x & 0xAAAAAAAAU);
    return ((bitsCnt >> 1) ^ oddCnt) & 1;
}

如你所见，你只需要一些快速的方法来做popcount。

关于algorithm - 一种简单/按位计算位奇偶校验的方法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33420943/