C - Swap a bit between two numbers

Question

I just tried with this code:

void swapBit(unsigned char* numbA, unsigned char* numbB, short bitPosition)//bitPosition 0-x
{
    unsigned char oneShift = 1 << bitPosition;

    unsigned char bitA = *numbA & oneShift;
    unsigned char bitB = *numbB & oneShift;

    if (bitA)
        *numbB |= bitA;
    else
        *numbB &= (~bitA ^ oneShift);

    if (bitB)
        *numbA |= bitB;
    else
        *numbA &= (~bitB ^ oneShift);
}

to swap bit position x of a and b but because of the if() I think there's something better.

Also when i see this:

*numbB &= (~bitA ^ oneShift);

I really think that there's an easier way to do it. If you have something for me, i would take it :)

Thanks in advance

This isn't really "swap two bits of a number" is it, more like "swap the a bit between two numbers" or something, that's still a confusing description though.. — harold, Jul 27 '17 at 21:41
Step 1: When working with unsigned types, better to use `1u << bitPosition` (add `u`) — chux - Reinstate Monica, Jul 27 '17 at 21:50
Thanks, harold, I modified the title, i didn't mind it.... Chux, i'll use that now, thanks :) — Tom Clabault, Jul 27 '17 at 21:57

score 5 · Accepted Answer · answered Jul 27 '17 at 21:42

5

First you should set the corresponding position in a number to 0, and then OR it with the actual bit, removing all of the conditions:

*numbB &= ~oneShift; // Set the bit to `0`
*numbB |= bitA;      // Set to the actual bit value

The same for the other number.

answered Jul 27 '17 at 21:42

Eugene Sh.

17,802
8
40
61

Very nice ! Thanks you a lot – Tom Clabault Jul 27 '17 at 21:59

score 2 · Answer 2 · answered Jun 13 '18 at 13:46

A single bit is no easier than an arbitrary bitmask, so lets just talk about that. You can always call this function with 1U << bitpos.

If a bit position is the same in both values, no change is needed in either. If it's opposite, they both need to invert.

XOR with 1 flips a bit; XOR with 0 is a no-op.

So what we want is a value that has a 1 everywhere there's a bit-difference between the inputs, and a 0 everywhere else. That's exactly what a XOR b does. Simply mask this to only swap some of the bits, and we have a bit-swap in 3 XORs + 1 AND.

// call with  unsigned char mask = 1U << bitPosition; if you want
inline
void swapBit_char(unsigned char *A, unsigned char *B, unsigned char mask)
{
    unsigned char tmpA = *A, tmpB = *B; // read into locals in case A==B

    unsigned char bitdiff = tmpA ^ tmpB;
    bitdiff &= mask;               // only swap bits matching the mask
    *A = tmpA ^ bitdiff;
    *B = tmpB ^ bitdiff;
}

(Godbolt compiler explorer with gcc for x86-64 and ARM, includes a version with unsigned instead of unsigned char.)

You could consider if(bitdiff) { ... }, but unless you're going to avoid dirtying a cache line in memory by avoiding the assignments, it's probably not worth doing any conditional behaviour. With values in registers (after inlining), a branch to save two xor instructions is almost never worth it.

This is not an xor-swap. It does use temporary storage. As @chux's answer demonstrates, a masked xor-swap requires 3 AND operations as well as 3 XOR. (And defeats the only benefit of XOR-swap by requiring a temporary register or other storage for the & results.)

This version only requires 1 AND. Also, the last two XORs are independent of each other, so total latency from inputs to both outputs is only 3 operations. (Typically 3 cycles).

For an x86 asm example, see this code-golf Exchange capitalization of two strings in 14 bytes of x86-64 machine code (with commented asm source)

A micro optimization for a weak compiler could use `bitdiff = (*A ^ *B) & mask; *A ^= bitdiff; *B ^= bitdiff;` which is like the result of the "This version only requires ..." paragraph. — chux - Reinstate Monica, Jun 13 '18 at 14:49
@chux: Writing to `*A` before doing `*B ^= bitdiff` is not equivalent in a stand-alone function when it's not know that `A != B`. Check the godbolt link for the code-gen different with the `_mayalias` version (named that because gcc has to reload `*B` after the write to `*A`.) — Peter Cordes, Jun 13 '18 at 14:53

score 1 · Answer 3 · answered Jul 27 '17 at 22:42

1

Form the mask

unsigned char mask = 1u << bitPosition;

And then earn the wrath of your peer group with XOR swap algorithm.

*numbA ^= *numbB & mask;
*numbB ^= *numbA & mask;
*numbA ^= *numbB & mask;

Note this fails when numbA == numbB.

answered Jul 27 '17 at 22:42

chux - Reinstate Monica

143,097
13
135
256

1

I wanted to give it as an alternative, but remembered the wrath of the SO peers on one of recent questions ☺️ – Eugene Sh. Jul 27 '17 at 23:48
@EugeneSh. IMO, it is the `numbA == numbB` problem that ultimately rejects this approach as it is a surprising error. – chux - Reinstate Monica Jul 28 '17 at 01:18
@EugeneSh.: `*numbB & mask` already needs temporary storage somewhere so it can be an operand for XOR. (Unless you're on a machine with ternary booleans, like x86 [AVX512F `vpternlogd`](http://felixcloutier.com/x86/VPTERNLOGD:VPTERNLOGQ.html).) So a masked xor-swap defeats the only advantage of xor-swap (at an asm level): no extra register. I posted an answer with 3 XOR and only 1 AND. (I think the bit-difference technique was fairly well known; I've seen it before but hadn't previously fully grokked it.) Anyway, it's *far* better than the OP's branchy version. – Peter Cordes Jun 13 '18 at 14:15

C - Swap a bit between two numbers

3 Answers3

Linked