如何在 C 中对单个数字的所有位进行异或？

Question

有没有一种简单的方法可以将单个数字的所有位异或在一起，即 C 中的一元异或？

具有以下效果的内容：

result = ^(0x45); // ( 0 ^ 1 ^ 0 ^ 0 ^ 0 ^ 1 ^ 0 ^ 1 = 1)
result = ^(0x33); // ( 0 ^ 0 ^ 1 ^ 1 ^ 0 ^ 0 ^ 1 ^ 1 = 0)

Answer 1

没有专门的运算符。您需要按如下方式手动执行此操作：

unsigned int value = 0x45;
unsigned int result = 0;
while (value) {
    result ^= value & 1;
    value >>= 1;
}

您还可以创建一个查找 table，其中包含所有 1 字节值的奇偶校验：

char parity[256] = { 0, 1, 1, 0, 1, 0, 0, 1,
                    ...
                     1, 0, 0, 1, 0, 1, 1, 0 };

Answer 2

如果您使用的是 gnu gcc，您应该能够使用 __builtin_popcount 来计算打开位的数量（即位设置为 1）。 XOR 的结果将是这个数字的奇偶校验。但是，此解决方案未使用标准，并不总是有效。

我相信没有仅使用标准的优雅解决方案。

Answer 3

GCC 为此内置了一个函数：

int xor_bits(unsigned x) {
    return __builtin_parity(x);
}

或者，您可以通过计算设置位数来计算奇偶校验。为此内置的 gcc 是 __builtin_popcount():

int xor_bits(unsigned x) {
    return __builtin_popcount(x) & 1;
}

如果您只想坚持使用标准 C，https://graphics.stanford.edu/~seander/bithacks.html and How to count the number of set bits in a 32-bit integer? 有一些计算设置位数的好方法。

Answer 4

你可以计算一个循环中的所有位，或者如果你想要一些可能更有效的东西，你可以屏蔽掉原始数字的部分并对它们重复进行异或运算，直到你得到 1 位操作数。假设一个 32 位整数，用 2 的补码表示：

int xor_all(int v)
{
    int l = (v & 0xFFFF0000) >> 16;
    int r = v & 0x0000FFFF;
    int m = l ^ r;

    l = (m & 0xFF00) >> 8;
    r = m & 0x00FF;
    m = l ^ r;

    l = (m & 0xF0) >> 4;
    r = m & 0x0F;
    m = l ^ r;

    l = (m & 0xC) >> 2;
    r = m & 3;
    m = l ^ r;

    l = (m & 2) >> 1;
    r = m & 1;
    m = l ^ r;
    return m;
}

还有其他技术；如果您只取结果的最低位，则任何计算设置位的好例程都将起作用。上面代码的好处是比较容易理解，但不一定是最快的。

Answer 5

一种简化的 O(log2(n)) 方法。

#include <limits.h>

int odd_parity(unsigned v) { 
    #if (UINT_MAX > 0xFFFFFFFFFFFFFFFFu)
    v ^= v >> 64;  // Prepare for the future
    #endif
    #if (UINT_MAX > 0xFFFFFFFFu)
    v ^= v >> 32;
    #endif
    #if (UINT_MAX > 0xFFFFu)
    v ^= v >> 16;
    #endif
    v ^= v >> 8;
    v ^= v >> 4;
    v ^= v >> 2;
    v ^= v >> 1;
    return (int) (v&1);
}

Answer 6

试试这个：

unsigned long parity(unsigned long x) {
    for(char i=sizeof(unsigned long)<<2;x>1;i>>=1) x=(x^(x<<i))>>i;
    return x;
}

unsigned long 是支持的最大类型（unsigned long long 是最大可能的类型）。它在 <cstdint> or <stdint.h> 中定义。 sizeof(unsigned long) 是字节。我们需要半位开始，所以它是字节 * 4。然后，上半部分与下半部分异或。然后我们摆脱下半部分。编辑后的答案保证收敛，最多溢出1个。

Answer 7

如果二进制表示中1的个数为奇数则答案为1；如果是偶数，那么答案是 0

如何在 C 中对单个数字的所有位进行异或？

How to XOR all of the bits of a single number in C?

c

xor