Bit Swaps

Question: How would you find the number of bit swaps required to convert integer A to integer B?

Answer: Gut instinct might suggest that you go through every bit of A and every bit of B while simultaneously updating a count of the bits that are different. But how about a cooler way to solve this?

A key to solving a lot of bit manipulation questions is the use of the XOR functionality.

int bit_swaps_required( int a, int b ) {
    unsigned int count = 0;
    for( int c = a ^ b; c != 0; c = c >> 1 ) {
        count += c & 1;
    }
    return count;
}

Simple right?

Help share this post through Twitter!

4 Responses

  1. Jun says:

    Perhaps this is even better?


    int bit_swap_required (int a, int b)
    {
    unsigned int count = 0;
    unsigned int c = a^b;
    while (c)
    {
    c &= c-1;
    ++ count;
    }
    return count;
    }

  2. Man says:

    Better solution: count the ones in a^b.

    count = 0;
    for(int c =a^b; c !=0; c &=(c-1), count++);

  3. Smiley says:

    Thanks, good catch. I’ve updated the post.

  4. Kaspter says:

    Hi, a slip of the pen??
    int bit_swaps_required( int a, int b ) {
    unsigned int count = 0;
    for( int c = a ^ b; c != 0; c = c >> 1 ) {
    count += c & 1;
    }
    return count;
    }

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>