1

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.

Improve this question
7
  • 3
    num1 ^= num2; num2 ^= num1; num1 ^= num2;? Commented Mar 18, 2020 at 11:58
  • 1
    Swapping values with XOR Commented Mar 18, 2020 at 11:58
  • 2
    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? Commented Mar 18, 2020 at 12:04
  • 1
    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. Commented Mar 18, 2020 at 12:36
  • 2
    @PeterCordes Bad question title then... and still not obvious that xor is faster than a = (a & 0xFF)<<8 | (a & 0xFF00)>>8; or similar. See godbolt.org/z/FKjFaH, it resulted in a rol trick on gcc x86. Commented Mar 18, 2020 at 12:56

3 Answers 3

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

This is the same bit-at-a-time algorithm proposed in What is the fastest way to swap values in C? 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.
2

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; }
Improve this answer

Comments

1

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)

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.