Invert n bits beginning at position p of an unsigned integer

Question

In an attempt to create a function that returns x with the n bits that begin at position p inverted, leaving the others unchanged - following the exercise in K&R - I've come up with the following piece of code.

Still, I find it unclear where to start counting, i.e. the result would be different if starting from the right. I am starting from the left - bit one is the first bit from the left.

unsigned invert(unsigned x, unsigned p, unsigned n)
{
  return x ^ ((~0U >> (p - 1 + (sizeof(int) * CHAR_BIT - p + 1 - n))) << (sizeof(int) * CHAR_BIT - p + 1 - n));
}

Which I'd then simplify to:

unsigned invert(unsigned x, unsigned p, unsigned n)
{
  return x ^ ((~0U >> (sizeof(int) * CHAR_BIT - n)) << (sizeof(int) * CHAR_BIT - p + 1 - n));
}

I'm not performing any boundary checks.

Is this good practice? Is there a cleaner solution?

Answer 1

When you find it "unclear where to start counting" you have encountered one of the greatest problems in software development: extracting useful specifications from your stakeholders! In these situations, when we can't just ask, then we need to choose an interpretation that seems most useful and reasonable, and (this is the important bit), be very clear that we had to make a choice, and what we chose.

In this case, I would probably make a somewhat more specific name, and also add an explanatory comment:

/*
 * Returns x with n bits inverted starting at bit p
 * (counting from the left)
 * E.g. invert_bits(0x0000, 4, 2) == 0x0c00 for 16-bit unsigned
 */
unsigned invert_bits(unsigned x, unsigned p, unsigned n)

That example in the comment would normally become one of the tests I use to verify the function.

I find it odd that we're working with unsigned yet we use sizeof (int) to calculate the width. Although we know that int and unsigned int have the same size, it's clearer to be consistent. Actually, I would just use sizeof x, which then makes it easier to re-use the code - e.g. if we write a version for unsigned long.

I think the arithmetic could be simplified if we consider that a mask with the leftmost p bits unset is ~0u >> p. Using invert_bits(0x0000, 4, 2) again, as in the comment, we can visualise what we're doing:

      0000111111111111   mask_p = ~0u >> p;
      0000001111111111   mask_n = mask_p >> n;
      0000110000000000   mask_p ^ mask_n

As a completed function, we can reuse a single mask variable for this:

unsigned invert_bits(unsigned x, unsigned p, unsigned n)
{
    unsigned mask = ~0u >> p;
    mask ^= mask >> n;
    return x ^ mask;
}

The nice thing about this is that it adapts automatically to the type's size, without needing any sizeof at all in the computation.

---

In case I've provided too much spoiler here, I provide some follow-up exercises:

1. Write the same function, but with the assumption that you count bits from the rightmost (least significant) bit.
2. Write a version for unsigned long.
3. Write versions that unconditionally set and reset the specified group of bits.
4. Write a main() that tests whether the above functions work as advertise. Remember to return EXIT_SUCCESS or EXIT_FAILURE as appropriate.

Which code can be shared in the answers to these questions?