K&R 2-7 - Invert a bitfield from a number

Question

This is my solution to the Exercise 2-7 of K&R C book. The assignment is:

Write a function invert(x,p,n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.

Note: It's assumed that the rigthmost bit of a number has position 0.

Example: If x = 8 (00001000 in binary), p = 2 and n = 3, the result should be 20 (00010100), because bits 2, 3 and 4 are inverted.

Code:

#include <stdio.h>

unsigned invert(unsigned x, int p, int n);

int main(void)
{
    // just a test
    printf("%u\n", invert(8, 2, 3));
    return 0;
}

unsigned invert(unsigned x, int p, int n)
{
    /* The right part makes a mask with 1's under the
       desired bits to be inverted. Then, they're inverted
       by X0Ring it and x.
    */
    return x ^ (~(~0 << n) << p);
}

Answer 1

Just a few notes, since the code is so short:

• Put your main after all of your other function declarations so you don't have to declare the function prototypes at the top.

• You don't have to return 0 at the end of main(). The C standard knows how frequently this is used, and lets us omit it.

  C99 & C11 §5.1.2.2(3)

  ...reaching the } that terminates the main() function returns a value of 0.

• Move your comment to the top of the function and explicitly say what the parameters are and what the output will be.

• Your function parameter names could be better:

  unsigned invert(unsigned num, int position, int num_bits)
  

• Those parameters to your function could be declared const

• Does your function perform as is supposed to with negative numbers? Zeros? Other edge cases? You should have more tests in your code to make sure you get the expected behavior, and if not handle those edge cases more appropriately. Use assert from the standard library header <assert.h> to help with this.

Answer 2

Bug

If you do:

invert(0, 0, 32);

Your function returns 0 instead of 0xffffffff. The problem is that in C, if you shift a 32-bit integer by 32 or more bits, it is undefined behavior.

The reason it is undefined behavior involves the very bug you just ran into. You were expecting that if you shift anything left by 32 bits, you would get 0. However, different computer architectures handle shifting by 32 differently. On an x86 target such as your desktop PC, your C compiler will generate this instruction:

shl dest, src

This shift left instruction shifts dest left by src bits. However, the x86 shl instruction will only shift between 0 and 31 bits. If you give it a src value higher than 32, it will simply mask the shift value by 31 like this:

dest = dest << (src & 31)

Because of this, whenever you try to left shift by 32 it actually left shifts by 0 and doesn't shift at all. So in your function, when you shift ~0 << 32 and expect to get 0, you are actually getting ~0 instead.

Now on other architectures, such as ARM, this behavior is different. ARM's LSL instruction (logical shift left) is defined such that shifting by 32 produces 0, which is more like what you expected to happen.

Fixing the problem

To avoid undefined behavior, you can do a little trick where you shift twice, once by n-1 and another time by 1. This depends on n being limited to the range 1..32:

return x ^ (~(~0U << (n-1) << 1) << p);

Or if you start with the expression that @KIIV suggested (which also invokes undefined behavior), you'd end up with:

return x ^ (((1U << n-1 << 1)-1) << p);

Of course, if n is 0 you'd shift left by -1 which again is undefined. So if n is allowed to be 0, you'd probably be better off just using an if statement to deal with n being too large. While we're at it, we can also check if p is too large because that would invoke undefined behavior as well. So in the end:

if (p >= sizeof(x) * CHAR_BIT)
    return x;
else if (n >= sizeof(x) * CHAR_BIT)
    return x ^ (~0U << p);
else
    return x ^ ((1U << n)-1) << p;

A common mistake

Don't feel bad about making this mistake. For the longest time, I also thought that shifting left by 32 was supposed to result in 0. And even after I learned that it didn't, I've still made the same mistake in my code because it's so easy to forget about this edge case.

It's exacerbated by the fact that shifting is defined differently in other languages. For example, in java, left shifting an int by 32 or more is defined to do the same thing that x86 does, which is mask the shift amount by 31.