CODEWITHSUNDEEP
cbit-manipulationlow-level
kiryakov
kiryakov

Reputation: 145

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

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.

Upvotes: 1

Views: 2064

Answers (3)

Peter Cordes
Peter Cordes

Reputation: 364163

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)

Upvotes: 1

hanie
hanie

Reputation: 1885

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

Upvotes: 2

KamilCuk
KamilCuk

Reputation: 140970

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.

Upvotes: 2

Related Questions