3

I saw a some solutions but its look complex.

What are the most effective way to swap between two bits in n,m postions?

int swapBits(int num, int nPostion, int mPosition);
Improve this question
3
  • 2
    check this: Link 1 Commented Jul 21, 2016 at 10:20
  • Why would a function swapping two bit take int num ? Commented Jul 21, 2016 at 11:15
  • take int , swap two bits in number and return the new number atfer swapping Commented Jul 21, 2016 at 12:33

6 Answers 6

Reset to default
8

Given integer n in which we wants to swap bit at location p1 and p2 : Algorithm : if both bits are same then just return same value else toggle both bits using XOR.

unsigned int swapBits(unsigned int n, unsigned int p1, unsigned int p2) { return (((n >> p1) & 1) == ((n >> p2) & 1) ? n : ((n ^ (1 << p2)) ^ (1 << p1))); }
Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

(1 << p2) should be (1U << p2) to avoid undefined behavior if p2 is one less than the width of unsigned int. Same remark for (1 << p1)
3

Not sure it is the most effective, but I think this is a rather simple solution:

int bitValue(int num, int nPosition) { return ( num >> nPosition ) % 2; } int swapBits(int num, int nPosition, int mPosition) { int nVal = bitValue(num, nPosition); int mVal = bitValue(num, mPosition); if (nVal != mVal) { if (1 == nVal) { num -= 1<<nPosition; num += 1<<mPosition; } else { num += 1<<nPosition; num -= 1<<mPosition; } } return num; }

Same solution in a more efficient (but less readable) way:

int swapBits2(int num, int nPosition, int mPosition) { int nVal = ( num >> nPosition ) % 2; int mVal = ( num >> mPosition ) % 2; if (nVal != mVal) { num += (-1)*(2*mVal-1)*(1<<mPosition) + (-1)*(2*nVal-1)*(1<<nPosition); } return num; }

and last:

int swapBits3(int num, int nPosition, int mPosition) { int k = ((num >> nPosition) & 1) - (num >> mPosition) & 1; return num + k*(1<<mPosition) - k*(1<<nPosition); }
Improve this answer

Comments

1

Parth Bera's answer contains a branch, but the xor-idea is correct.

Assume the bits of p are ????A????B???. To turn A into B and B into A, we need to xor them with (A^B). For convenience, let X=A^B

????A????B??? 0000X0000X000 ^ ============= ????B????A???

How do we generate 0000X0000X000 ?

????A????B??? >> (nPostion-mPostion) ?????????A??? ^ ?????????X??? & (1<<mPosition) 000000000X000 << (nPostion-mPostion) 0000X00000000 + 0000X0000X000 ^ ????A????B??? == ????B????A???
Improve this answer

Comments

0

You can use the following macro to avoid temporary variables or a stack allocation, and it will work with any numeric type:

#define SWAP_BITS(v,b1,b2) \ (((v)>>(b1)&1)==((v)>>(b2)&1)?(v):(v^(1ULL<<(b1))^(1ULL<<(b2))))
Improve this answer

4 Comments

Why use a macro that evaluates its arguments multiple times when an inline function will do just fine?
Also your code does not work for signed types int, long and long long if b1 or b2 refer to the most significant bit as shifting 1 cast to the destination type by that much has undefined behavior.
Yep, I updated that in my code to 1ULL, updated my answer now as well. About multiple evaluation: Yes that may happen but shouldn't the compiler optimize that away, at least if it knows to be free of side-effects? The macro may no be the best choice if you pass in a function call as expression. But if you want to use it for multiple types you'd need to define your function multiple times, don't you?
The compiler cannot optimize multiple evaluations away, the macro is substituted literally and the compiler must assume that the multiple evaluations are intended. Macros are indeed useful to handle multiple types but the new _Generic construct allows a macro to expand to the appropriate function call as determined from the type of the argument eg: #define swap_bits(v,b1,b2) _Generic(+(v), unsigned int: swap_bits_uint, unsigned long: swap_bits_ulong, unsigned long long: swap_bits_ullong)(v, b1, b2)
0

Building on Shay Gold's solution, here is one with a few bug fixes:

unsigned int swapBits(unsigned int num, int nPosition, int mPosition) { unsigned int k = ((num >> nPosition) & 1) - ((num >> mPosition) & 1); return num + k * ((1U << mPosition) - (1U << nPosition)); }
Improve this answer

2 Comments

Shouldn't it be the other way around: int swapBits(int num... and unsigned int ...position? Also I don't get why shifting negative numbers should be undefined (although your link suggests this), if we shift bits into the sign bit or out of the sign bit, the number would just swap signs. It's not particularly undefined but maybe unexpected...
@hurikhan77: The C Standard explicitly says that shifting negative values has undefined behavior. In other languages, such as java and javascript, shifting negative values to the right with >> is defined to perform sign replication, and some C implementations do that but the C Standard does not mandate this behavior, nor the one you describe.
0 
unsigned int swapbits(unsigned int num, unsigned int pos1, unsigned int pos2) { unsigned int bits_of_interest_mask = (1 << pos1) | (1 << pos2); unsigned int bits_of_interest = num & bits_of_interest_mask; unsigned int null_factor = ((bits_of_interest != 0) & (bits_of_interest != bits_of_interest_mask)); unsigned int xor_mask = null_factor * bits_of_interest_mask; return num ^ xor_mask; }

(Compilers remove the multiplication by the boolean: https://godbolt.org/z/a4z3jnh7c, https://godbolt.org/z/aM3TK7bq1)

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.