Bit invert function in K&R exercise 2-7

Question

Exercise 2-7 of The C Programming Language:

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

I understood the question like this: I have 182 which is 101(101)10 in binary, the part in parentheses has to be inverted without changing the rest. The return value should be 10101010 then, which is 170 in decimal.

Here is my attempt:

#include <stdio.h>

unsigned int getbits(unsigned int bitfield, int pos, int num);
unsigned int invert(unsigned int bitfield, int pos, int num);

int main(void)
{
    printf("%d\n", invert(182, 4, 3));
    return 0;
}

/* getbits: get num bits from position pos */
unsigned int getbits(unsigned int bitfield, int pos, int num)
{
    return (bitfield >> (pos+1-n)) & ~(~0 << num);
}

/* invert: flip pos-num bits in bitfield */
unsigned int invert(unsigned int bitfield, int pos, int num)
{
    unsigned int mask;
    unsigned int bits = getbits(bitfield,pos,num);

    mask = (bits << (num-1)) | ((~bits << (pos+1)) >> num);

    return bitfield ^ mask;
}

It seems correct (to me), but invert(182, 4, 3) outputs 536870730. getbits() works fine (it's straight from the book). I wrote down what happens in the expression I've assigned to y:

(00000101 << 2) | ((~00000101 << 5) >> 3)    -- 000000101 is the part being flipped: 101(101)10
       00010100 | ((11111010 << 5) >> 3)
       00010100 | (01000000 >> 3)
       00010100 | 00001000
= 00011100

  10110110 (182)
^ 00011100
----------
= 10101010 (170)

Should be correct, but it isn't. I found out this is where it goes wrong: ((~xpn << (p+1)) >> n). I don't see how.

Also, I've no idea how general this code is. My first priority is to just get this case working. Help in this issue is welcome too.

Answer 1

((1u<<n)-1) is a bit mask with n '1' bits at the RHS. <<p shifts this block of ones p positions to the left. (you should shift with (p-n) instead of p if you want to count from the left).

return val  ^ (((1u<<n)-1) <<p) ;

There still is a problem when p is larger than the wordsize (shifting by more than the wordsize is undefined), but that should be the responsability of the caller ;-)

For the example 101(101)10 with p=2 and n=3:

1u<<n               := 1000
((1u<<n)-1)         := 0111
(((1u<<n)-1) <<p) := 011100
original val    := 10110110
val ^ mask      := 10101010

Answer 2

I think you have an off-by-one issue in one of the shifts (it's just a hunch, I'm not entirely sure). Nevertheless, I'd keep it simple (I'm assuming the index position p starts from the LSB, i.e. p=0 is the LSB):

unsigned int getbits(unsigned int x, int p, int n) {
  unsigned int ones = ~(unsigned int)0;
  return x ^ (ones << p) ^ (ones << (p+n));
}

edit: If you need p=0 to be the MSB, just invert the shifts (this works correctly because ones is defined as unsigned int):

unsigned int getbits(unsigned int x, int p, int n) {
  unsigned int ones = ~(unsigned int)0;
  return x ^ (ones >> p) ^ (ones >> (p+n));
}

note: in both cases if p < 0, p >= sizeof(int)*8, p+n < 0 or p+n >= sizeof(int)*8 the result of getbits is undefined.

Answer 3

Take a look at Steve Summit's "Introductory C programming" and at Ted Jensen's "At tutorial on pointers and arrays in C". The language they cover is a bit different from today's C (also programming customs have evolved, machines are much larger, and real men don't write assembler anymore), but much of what they say is as true today as it was then. Sean Anderson's "Bit twiddling hacks" will make your eyes bulge. Guaranteed.

Answer 4

I found out what was wrong in my implementation (other than counting num from the wrong direction). Seems fairly obvious afterwards now that I've learned more about bits.

When a 1-bit is shifted left, out of range of the bit field, it's expanded.

   1000 (8) << 1
== 10000 (16)

bitfield << n multiplies bitfield by 2 n times. My expression ((~bits << (pos+1)) >> num) has 5, 4 and 3 as values for bits, pos and num, respectively. I was multiplying a number almost the size of a 32-bit int by 2, twice.

Answer 5

how about my function? i think it so good.

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