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

Question

I am having some trouble with swapping 2 integers using bit manipulation. Below is my code and console 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);
}

Output:

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

I might be doing something completely wrong, I'm fairly new to low-level C programming. Is my algorithm inherently flawed? Is there a simpler way to do this? Any help and advice is welcome.

[Swapping values with XOR](https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR) — KamilCuk, Mar 18 '20 at 11:58
Do you want to only exchange some set of bits selected by a mask? A masked xor-swap can be useful. A plain xor-swap of the whole values is possible but you should never use it except in rare cases in hand-written asm. In C always use a tmp var instead. [Why don't people use xor swaps?](https://stackoverflow.com/q/16535461) — Peter Cordes, Mar 18 '20 at 12:04
Just use a temporary variable. Swapping data with xor just because we can is bad practice since it makes the code less readable and possibly also less efficient. In addition, you may get accidental integer promotion bugs with xor that wouldn't be present with simple assignment. — Lundin, Mar 18 '20 at 12:36
@Lundin: note that the OP only wants to swap the low 8 bits of their `int`. Bit hacks *are* appropriate there; I added an answer that uses XOR with a masked bit-difference instead of looping. (As well as repeating the point that xor-swap is a terrible idea) — Peter Cordes, Mar 18 '20 at 12:43
@PeterCordes Bad question title then... and still not obvious that xor is faster than `a = (a & 0xFF)<<8 | (a & 0xFF00)>>8; ` or similar. See https://godbolt.org/z/FKjFaH, it resulted in a `rol` trick on gcc x86. — Lundin, Mar 18 '20 at 12:56
@Lundin: Sorry, I explained it wrong by leaving out a plural on `int`s. They want to swap the low 8 bits between two `int`s, not swap bit-ranges within one `int`. The optimized version of what they want is XORing both inputs with `unsigned bitdiff = (num1 ^ num2) & 0xff;` like I wrote in my answer. (And BTW, your rotate zeros the upper 16 bits, not *just* swapping the low two 8-bit fields. I wonder if gcc can optimize to `rol word [rdi], 8` if we write it to preserve the upper 16... yes https://godbolt.org/z/GE3Upd wow I'm impressed. I didn't think GCC would do partial access to an object) — Peter Cordes, Mar 18 '20 at 13:03

score 2 · Accepted Answer · answered Mar 18 '20 at 12:04

2

Is my algorithm inherently flawed?

Yes. You need invert bit at certain position.

       num1 ^= position;
       num2 ^= position;

1 * 2 is equal to 1 + 1. Just do position *= 2; each loop.

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?

Yes, swap values with xor, as suggested in comments.

answered Mar 18 '20 at 12:04

KamilCuk

120,984
8
59
111

This is the same bit-at-a-time algorithm proposed in [What is the fastest way to swap values in C?](https://stackoverflow.com/a/45512) as intentionally slow, but maybe still hidden by memory latency for a big sort algo. (It probably won't be, though.) It could be branchless by masking with `position` and doing a masked xor-swap instead of an `if`. – Peter Cordes Mar 18 '20 at 12:11

score 2 · Answer 2 · answered Mar 18 '20 at 12:07

simple way to swap 2 integers in C using bitwise operators:

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;
}

Peter Cordes · Answer 3 · 2020-03-18T12:45:07.103

Is there a simpler way to do this?

Yes, use a tmp var, it's simpler and can be optimized better by compilers.

   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

This can sometimes compile to zero asm instructions; the compiler just knows which var is where. Why don't people use xor swaps?

A plain xor-swap of the whole values is possible but you should never use it except in rare cases in hand-written asm. In C always use a tmp var instead. What is the fastest way to swap values in C? asks about xor-swap vs. normal swap. For some reason a lot of people think an xor swap might actually be more efficient and call it a "premature optimization". It's not. It's bad for compilers as well as bad for humans. If it was more efficient on some machine, optimizing compilers would compile normal swaps into xor swaps in the asm; that's the point of a modern optimizing compiler.

Is my algorithm inherently flawed?

For performance, yes.

For correctness, not inherently flawed, but one showstopper bug. You're checking the bit at bitindex with num1 & position, but instead of exchanging those bits you use num1 << bitindex instead of 1 << bitindex.

The very first step of this, with bitindex = 0, will zero both numbers if one is odd and the other is even (so the condition is true because their low bits differ). x^x == 0 for all x.

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

In general using shifted num1 and num2 is not useful.

Also note that your position is already 1<<bitindex so you might as well just use that and not have bitindex at all.

You're trying to implement a bit-at-a-time swap which is very inefficient. You'd only ever do something like this if you wanted to swap only a certain range of bits, and you'd still do all the bit positions you wanted in one step by using a mask with those bits set. (Instead of left shifting a single-bit mask in a loop.)

From Swapping bits at a given point between two bytes which explains how this algorithm works:

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

With this replacing your loop, it can swap 4 and 7.

Or for larger inputs like 555 and 444, we get 700 and 299. (That's
0x22b, 0x1bc => 0x2bc, 0x12b correctly swapping the low 8 bits)

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

3 Answers3