如何使用按位运算符和位操作在 C 语言中交换 2 个整数？

Question

我在使用位操作交换 2 个整数时遇到了一些问题。下面是我的代码和控制台 input/output.

#include <stdio.h>

int main() {
    int num1 = 0;
    int num2 = 0;
    int position = 1;

    scanf("%d", &num1);
    scanf("%d", &num2);

    for (int bitindex = 0; bitindex < 8; bitindex++) {
        printf("\nPosition: %d\n", position);
        printf("Number 1: %d\n", num1);
        printf("Number 2: %d\n", num2);
        if ((num1 & position) != (num2 & position)) {
            num1 ^= (num1 << bitindex);
            num2 ^= (num2 << bitindex);
        }
        if (bitindex == 0) {
            position++;
        }
        else {
            position *= 2;
        }
    }

    // printf("Number 1: %d\n", num1);
    // printf("Number 2: %d\n", num2);
}

输出：

4 7
Position: 1 Number 1: 4 Number 2: 7
Position: 2 Number 1: 0 Number 2: 0
Position: 4 Number 1: 0 Number 2: 0
Position: 8 Number 1: 0 Number 2: 0
Position: 16 Number 1: 0 Number 2: 0
Position: 32 Number 1: 0 Number 2: 0
Position: 64 Number 1: 0 Number 2: 0
Position: 128 Number 1: 0 Number 2: 0

我可能做错了一些事情，我对低级 C 编程还很陌生。我的算法天生就有缺陷吗？有没有更简单的方法来做到这一点？欢迎任何帮助和建议。

Answer 1

Is my algorithm inherently flawed?

是的。您需要在特定位置反转位。

       num1 ^= position;
       num2 ^= position;

1 * 2 等于 1 + 1。每个循环只做 position *= 2;。

int position = 1;
for (int bitindex = 0; bitindex < 8; bitindex++) {
    if ((num1 & position) != (num2 & position)) {
       num1 ^= position;
       num2 ^= position;
    }
    position *= 2;
}

Is there a simpler way to do this?

是的，按照评论中的建议用 xor 交换值。

Answer 2

在 C 中使用按位运算符交换 2 个整数的简单方法：

int main() {
    int i, k;
    scanf("%d%d", &i, &k);
    printf(" value of i=%d k=%d before swapping", i, k);

    i = i ^ k;
    k = i ^ k;
    i = i ^ k;
    printf("value of i=%d k=%d after swapping", i, k);

    return 0;
}

Answer 3

Is there a simpler way to do this?

是的，使用 tmp var，它更简单并且可以被编译器更好地优化。

   int tmp = num1;
   num1 = num2;
   num2 = tmp;
// this swaps the whole value, not just the low 8 bits
// if that's important, see below for bit-difference XOR

这有时可以编译为零 asm 指令；编译器只知道哪个 var 在哪里。 Why don't people use xor swaps?

对整个值进行简单的异或交换是可能的，但除非在手写 asm 中的极少数情况下，否则你不应该使用它。在 C 中，始终使用 tmp var。 What is the fastest way to swap values in C? 询问异或交换与普通交换。出于某种原因，很多人认为 xor 交换实际上可能更有效，并将其称为 "premature optimization"。不是。这对编译器不利，对人类也不利。如果它在某些机器上效率更高，优化编译器会将普通交换编译为 asm 中的 xor 交换；这就是现代优化编译器的重点。

Is my algorithm inherently flawed?

为了性能，是的。

对于正确性，不是天生的缺陷，而是一个突出的错误。您正在使用 num1 & position、 检查 bitindex 的位，但您没有交换这些位，而是使用 num1 << bitindex 而不是 1 << bitindex.

第一步，bitindex = 0，如果一个是奇数，另一个是偶数，则将两个数字归零（因此条件为真，因为它们的低位不同）。 x^x == 0 所有 x.

            // with bit-index = 0
            num1 ^= (num1 << bitindex);   // becomes num1 ^= num1
            num2 ^= (num2 << bitindex);   // becomes num2 ^= num2

通常使用移位的 num1 和 num2 是没有用的。

另请注意，您的 position 已经 1<<bitindex，因此您最好使用它，而根本没有 bitindex。

您正在尝试实现一次一位的交换，这是非常低效的。您只会如果您只想交换特定范围的位，请执行 之类的 操作，并且您仍然可以通过使用设置了这些位的掩码一步完成所需的所有位位置。（而不是在循环中左移一位掩码。）

来自 Swapping bits at a given point between two bytes 解释了该算法的工作原理：

    unsigned bitdiff = num1 ^ num2;
    bitdiff &= 0xff;               // only swap the low 8 bits
    num1 ^= bitdiff;
    num2 ^= bitdiff;

用这个替换你的循环，它可以交换 4 和 7。

或者对于更大的输入，如 555 和 444，我们得到 700 和 299。（那是
0x22b, 0x1bc => 0x2bc, 0x12b 正确交换低 8 位)

如何使用按位运算符和位操作在 C 语言中交换 2 个整数？

How can I swap 2 integers in C using bitwise operators and bit manipulation?

c

bit-manipulation

low-level