4

I have written a code for swapping bit positions(source bit and destination bit).. it is working fine.. But is there any optimized code to do this?

int bit_swap(int num, int sbit, int dbit)
{
if(num & (1 << sbit) == num & (1 << dbit))
return num;
else
return (num ^ ((1 << sbit) | (1 << dbit)));
}

Here.. num is the input number.. sbit is the source bit position and dbit is the destination bit position..

Is there any way to write this code in a single line without using if and else

Improve this question
6
  • 3
    Have you profiled? Have you profiled as-is without the if? Commented Jan 2, 2013 at 6:02
  • 3
    graphics.stanford.edu/~seander/bithacks.html#SwappingBitsXOR Commented Jan 2, 2013 at 6:04
  • 1
    @leppie: the article is too good.. helped me a lot.. thanks a ton! :) Commented Jan 2, 2013 at 6:09
  • 1
    For a swap operation, both bits are both source and destination, thus naming one as source and the other as destination is misleading. Better name them pos1 and pos2 or something similar, as given in some answers. Additionally, it is usually a good idea to use unsigned ints when handling single bits, at least if you want your code to be portable. But this depends on what you need this for, just be aware that you may run into problems with negative values. Commented Jan 2, 2013 at 9:16
  • 2
    I would advise turning up the warning level to start with, clang reports: & has lower precedence than ==; == will be evaluated first [-Wparentheses] in if(num & (1 << sbit) == num & (1 << dbit)). Commented Jan 2, 2013 at 10:06

3 Answers 3

Reset to default
12

You are making the classical mistake in thinking that less lines in C means more optimised code.

You should really examine the assembler output and profile your code to see if it's an actual bottleneck.

What I tend to do is optimise for readability first then only attack performance if it becomes an issue. So, a more readable solution (in my not so humble opinion) would be something like:

unsigned int bit_swap (unsigned int num, unsigned int pos1, unsigned int pos2) {
    // Swapping identical bit positions is a no-op.

    if (pos1 == pos2)
        return num;

    // Get masks from bit positions.

    unsigned int mask1 = 1 << pos1;
    unsigned int mask2 = 1 << pos2;

    // Get bit truth values.

    int bit1_was_set = ((num & mask1) != 0);
    int bit2_was_set = ((num & mask2) != 0);

    // Clear and set first bit (set only if second bit was originally set).

    num = num & ~mask1;
    if (bit2_was_set)
        num = num | mask1;

    // Do the same for other bit.

    num = num & ~mask2;
    if (bit1_was_set)
        num = num | mask2;

    // Return the value with swapped bits.

    return num;
}

Despite having far more lines than your approach, you may well find the insanely optimising compilers available nowadays will give you similar code under the covers.

What you almost certainly will discover is that non-C-guru people (and possibly yourself, six months from now) will be able to understand your source code better than a single line multi-bitwise-operator variant.

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

Comments

6

No conditional version.

int bit_swap(int num, int sbit, int dbit)
{
    int sval = !!(num & (1 << sbit));  // sets to 1 iff the s-bit is already set
    int dval = !!(num & (1 << dbit));  // sets to 1 iff the d-bit is already set

    int xorval = (sval ^ dval); // sets to 1 if (sval != dval), otherwise 0

    // so if xorval is 1, then it will toggle the bits at the S and D positions
    // otherwise, the expression below evalutes to "num" that was passed in
    return (num ^ ((xorval << sbit) | (xorval << dbit)));
}
Improve this answer

9 Comments

This code has undefined behavior if sbit or dbit indicates the highest bit in an int in typical C implementations, because 1 << sbit or 1 << dbit overflows the values of a signed int. Generally, it is better to use unsigned integers for bit operations like this.
Undefined only if (sbit < 0) || (sbit >= (sizeof(int)*8) will there be a problem. (Same for dbit). Assuming 32-bit, 31 is the MSB index. (1 << 31) is 0x80000000 and will not overflow. Bit shifting left is ok for signed int, but is undefined for right-shifts. There's no right-shifts above.
1<<31 is an overflow with a 32-bit int. C 2011 (N1570) 6.5.7 4: “If E1 has a signed type and nonnegative value, and E1*2E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.” The value 231 is not representable in a 32-bit int.
Interesting. I just looked at the spec you cited. I knew about the undefined behavior of right-shifting a signed-negative int, but not the left-shift behavior. However, I suspect the world would tip upside down if (1<<31) wasn't 0x80000000 (on a 2's complement machine).
It is a trap to think that the machine works a certain way, so the C semantics follow along. One of the things that happens is that C rules are built into the optimizer in various ways, and it makes perfectly legal but unexpected deductions. Once the optimizer deduces that a certain piece of code evaluates 1<<31, it can do anything it wants, like completely eliminating all code that flows to that evaluation (after observable effects before it) and all code that flows from it.
|
2

I came up with

unsigned swapBits(unsigned num, int sbit, int dbit)
{
  return ( num &               // All bits
    ~((1<<sbit) | (1<<dbit)))  // Except sbit and dbit
    | (((num>>sbit)&1)<<dbit)  // but with sbit moved to dbit
    | (((num>>dbit)&1)<<sbit); // and with dbit moved to sbit
}

I did have an ARM in mind, with its cheap shifts.

Improve this answer

1 Comment

nice one.. was expecting this kinda answer.. :)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.