title: Bit invert function in K&R exercise 2-7
body: <p>Exercise 2-7 of <em>The C Programming Language</em>:  </p>
  
  <blockquote>
    <p>Write a function <code>invert(x,p,n)</code> that returns <code>x</code> with the <code>n</code> bits that begin at position <code>p</code> inverted (i.e., 1 changed to 0 and vice versa), leaving the others unchanged.</p>
  </blockquote>
  
  <p>I understood the question like this: I have 182 which is <code>101(101)10</code> in binary, the part in parentheses has to be inverted without changing the rest. The return value should be <code>10101010</code> then, which is 170 in decimal.</p>
  
  <p>Here is my attempt:  </p>
  
  <pre><code>#include &lt;stdio.h&gt;
  
  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 &gt;&gt; (pos+1-n)) &amp; ~(~0 &lt;&lt; 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 &lt;&lt; (num-1)) | ((~bits &lt;&lt; (pos+1)) &gt;&gt; num);
  
      return bitfield ^ mask;
  }
  </code></pre>
  
  <p>It seems correct (to me), but <code>invert(182, 4, 3)</code> outputs <code>536870730</code>. <code>getbits()</code> works fine (it's straight from the book). I wrote down what happens in the expression I've assigned to <code>y</code>:  </p>
  
  <pre><code>(00000101 &lt;&lt; 2) | ((~00000101 &lt;&lt; 5) &gt;&gt; 3)    -- 000000101 is the part being flipped: 101(101)10
         00010100 | ((11111010 &lt;&lt; 5) &gt;&gt; 3)
         00010100 | (01000000 &gt;&gt; 3)
         00010100 | 00001000
  = 00011100
  
    10110110 (182)
  ^ 00011100
  ----------
  = 10101010 (170)
  </code></pre>
  
  <p>Should be correct, but it isn't. I found out this is where it goes wrong: <code>((~xpn &lt;&lt; (p+1)) &gt;&gt; n)</code>. I don't see how.</p>
  
  <p>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.</p>