5

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

Improve this question
3
  • 1
    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.. Commented Jul 27, 2017 at 21:41
  • Step 1: When working with unsigned types, better to use 1u << bitPosition (add u) Commented Jul 27, 2017 at 21:50
  • Thanks, harold, I modified the title, i didn't mind it.... Chux, i'll use that now, thanks :) Commented Jul 27, 2017 at 21:57

3 Answers 3

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

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

1 Comment

Very nice ! Thanks you a lot
2

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)

Improve this answer

2 Comments

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: 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.)
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.

Improve this answer

3 Comments

I wanted to give it as an alternative, but remembered the wrath of the SO peers on one of recent questions ☺️
@EugeneSh. IMO, it is the numbA == numbB problem that ultimately rejects this approach as it is a surprising error.
@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.) 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.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.