HN Explorer

Ask HN: Is it possible to swap two signed integers in C without a third variable

1 points by ummonk ↗ HN
The standard tricks of using arithmetic or xor don't work because both have potentially undefined behavior on some values of signed integers.

If sizeof(int) were guaranteed to be sizeof(unsigned int) then maybe a cast could do it: (unsigned int )&a = (unsigned int )&a ^ (unsigned int )&b; (unsigned int )&b = (unsigned int )&a ^ (unsigned int )&b; (unsigned int )&a = (unsigned int )&a ^ (unsigned int )&b;

What would be a general solution? Is there a way to use the preprocessor to spit out sizeof(int) lines that do bitwise xor on every respective byte in a and b?

9 comments

[ 2.9 ms ] story [ 39.8 ms ] thread
fwsgonzo
It's not a trick to use XOR to swap variables. XOR is a code pessimization. You should be using std::swap or just use a temporary which generates proper machine code. Most instruction sets have exchange which is 1 instruction.

I guess that answers your question. You can swap two integers on x86. See the xchg instruction.

https://www.felixcloutier.com/x86/xchg

rzzzt
I can only get a bunch of MOVs out of Compiler Explorer. It might be because XCHG is also locking?
fwsgonzo
There is a locked version of XCHG that behaves atomically. I believe that if you swap memory locations that lock is implicit, so maybe you are not just swapping registers?
retrocryptid
Also, not everyone uses x86(-64). In the last several years, I've used ARM, RV32 and RV64 as well as X86-64. Sounds like the original poster is painfully aware of platform and compiler differences, and wants to make something as general case as possible.

I mean sure, this seems like a pretty out-there corner case, but maybe they want to support the Bendix G-15 and other 1's complement machines.

ummonk
Yeah I'm not actually implementing anything but I'm curious about the common coding puzzle of "swap two numbers without a third variable" and what that's actually solvable in a non-platform specific way for signed integers given the limitations of what is actually guaranteed by the C standard.
retrocryptid
A laudable goal, but keep in mind, neither gcc nor llvm are truly faithful to the c spec. (Though I haven't really studied C17, so maybe they've mended their ways.) I think I might say it like this: the exhibited behaviour of either gcc or llvm and the behaviour described in C11 are not proper subsets of each other.

This whole exercise got me thinking if there's an architecture supported by gcc where unsigned {short, int, long, long long} and {short, int, long, long long} have different widths. (even though it's not mandated by the spec)

retrocryptid
I looked at the C99 and C11 specs and sure enough, there's nothing that says sizeof( int ) == sizeof( unsigned int ). But I would think it would be common enough you could assume it's true. I mean, have you ever seen a machine made after 1970 where sizeof( int ) and sizeof( unsigned int ) were different? (or short / unsigned short, long / unsigned long, long long / unsigned long long). I suspect this is a no-go since you went to the trouble of posting this question.

I'm sure you could do it byte by byte and hope the compiler could optimize it.

(I don't have the C17 spec around, so maybe someone else could check it didn't add that constraint, in which case my response would be "Of course! just use C17!")

efas
Implicitly, the two signed integers are large enough to fit each other (they are the same size). I would not assume anything about organization in memory though. x=a, y=b; look at arithmetic in pseudo-ops x=a, y=(b-a); there will be an overflow here or after the negation step x=a+(b-a)=b, y=(b-a); x=b, y=(a-b); negate the unitary value could overflow (and set the carry bit) x=b, y=(a-b)+b=a; oops, four operations and not as elegant as XORs can be. Or, the compiler would probably use a third register.