CODEWITHSUNDEEP
c++bit-manipulation
claytonjwong
claytonjwong

Reputation: 844

Swap right-most N bits between two integers

This question was asked during an onsite C++ coding interview. I did NOT provide a good answer during that interview. So I was hoping to get feedback and suggestions from folks here at stack overflow. Now that I've had some more time to come up with a solution, I believe that I wrote a decent solution. I think this works OK as along as a and b refer to different integers. If a and b refer to the same integer, then that integer would be be clobbered to 0. 

void SwapRightMostNBits(int& a, int& b, unsigned int n){

    if (n>31) { n=31; }
    int mask=static_cast<int>(pow(2,n)-1);

    a ^= (b & mask);
    b ^= (a & mask);
    a ^= (b & mask);
}

Upvotes: 3

Views: 109

Answers (1)

MSalters
MSalters

Reputation: 179819

I think the intended trick here is 

void SwapRightMostNBits(unsigned int& a, unsigned int& b, unsigned int n){

    unsigned int mask=(1U<<n) -1;
    unsigned int diff = (a^b) & mask;

    a ^= diff;
    b ^= diff;
}

Note that this uses 3 XOR's, like your solution, but only one masking operation. Plus, this is way friendlier on the CPU registers. There are no false dependency chains. And finally, it works if &a==&b.

Upvotes: 6

Related Questions