C - Mistake in solutions to K&R?

Author

Mistake in solutions to K&R?

poodles

2006-06-27, 7:56 am

This post lists a possible error in the solution to Exercise 2-7, page
49 (K&R) on the webpage
http://users.powernet.co.uk/eton/kandr2/krx207.html

Question:

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.

The return statement on the webpage is

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

which is (possibly) incorrect; I've made the following one which is
correct (please correct me if it isn't):

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

Explanation:

Take a number 1 1000 1000, say, and p=7 and n=4 then the answer should
be 1 0111 1000

In the original code the following steps take place:

1) 0000 0000 0000 0000 0000 0000 0000 0000 //0U

2) 1111 1111 1111 1111 1111 1111 1111 1111 //~

3) 1111 1111 1111 1111 1111 1111 1111 0000 //<<n

4) 0000 0000 0000 0000 0000 0000 0000 1111 //~

5) 0000 0000 0000 0000 0000 0111 1000 0000 //<< p

6) 0000 0000 0000 0000 0000 0001 1000 1000 //x itself

7) 0000 0000 0000 0000 0000 0110 0000 1000 //x^ (value in
step 5)

which is the wrong answer.

In my code, the following steps take place:

1) 0000 0000 0000 0000 0000 0000 0000 0000 //0U

2) 1111 1111 1111 1111 1111 1111 1111 1111 //~

3) 1111 1111 1111 1111 1111 1111 0000 0000 //<<p+1

4) 0000 0000 0000 0000 0000 0000 1111 1111 //~

5) 0000 0000 0000 0000 0000 0000 0000 1111 //>>p+1-n

6) 0000 0000 0000 0000 0000 0000 1111 0000 //<<p+1-n

7) 0000 0000 0000 0000 0000 0001 1000 1000 //x itself

7) 0000 0000 0000 0000 0000 0001 0111 1000 //x^ (value in
step 6)

which is, hopefully, the correct answer.

Examples

#1. (Same as above)

Take the number

392.d=110001000.b

Then if p=7 and n=4, then the answer after reversal will be:

376.d=101111000.b

This is what the code I made gives as the answer.

The answer the code on the website gives is

1544.d=11000001000.b

#2.

Take the number

588.d=1001001100.b

Then if p=7 and n=7, then the answer after reversal will be:

690.d=1010110010.b

This is what the code I made gives as the answer.

The answer the code on the website gives is

15820.d=11110111001100.b

----------------------------------------------------------------------------------------------------------------------
P.S: in the main() function on the same page, which was written "in a
hurry while tired", it's likely that n and p have been accidentally
reversed (that's not a mistake, anyway).

========================================
===================
Do you make Adsense Websites?
If the answer is yes, checkout this website:
http://www.uniquecontentpro.com/?a=1231

Harald van Dĳk

2006-06-27, 6:56 pm

poodles wrote:
> This post lists a possible error in the solution to Exercise 2-7, page
> 49 (K&R) on the webpage
> http://users.powernet.co.uk/eton/kandr2/krx207.html
>
> Question:
>
> 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.
>
> The return statement on the webpage is
>
> return x ^ (~(~0U << n) << p);
>
> which is (possibly) incorrect; I've made the following one which is
> correct (please correct me if it isn't):
>
> return x^((~(~0U<<(p+1))>>(p+1-n))<<(p+1-n));
>
> Explanation:
>
> Take a number 1 1000 1000, say, and p=7 and n=4 then the answer should
> be 1 0111 1000

Unless you for no apparent reason count in two different directions,
the 4 bits starting from the 7th are the 7th, the 8th, the 9th and the
10th, and I would expect the answer to be 0110 0000 1000.

poodles

2006-06-27, 6:56 pm

poodles

2006-06-27, 6:56 pm

Harald van D=C4=B3k wrote:

> Unless you for no apparent reason count in two different directions,
> the 4 bits starting from the 7th are the 7th, the 8th, the 9th and the
> 10th, and I would expect the answer to be 0110 0000 1000.

You may be right, but here's a quote from the K&R book:

quote:
As an illustration of some of the bit operators, consider the function
getbits(x,p,n) that
returns the (right adjusted) n-bit field of x that begins at position
p=2E We assume that bit
position 0 is at the right end and that n and p are sensible positive
values. For example,
getbits(x,4,3) returns the three bits in positions 4, 3 and 2,
right-adjusted.

poodles

2006-06-27, 6:56 pm

Harald van D=C4=B3k wrote:
> Unless you for no apparent reason count in two different directions,
> the 4 bits starting from the 7th are the 7th, the 8th, the 9th and the
> 10th, and I would expect the answer to be 0110 0000 1000.

You may be right, but here's a quote from the K&R book:

quote:
As an illustration of some of the bit operators, consider the function
getbits(x,p,n) that returns the (right adjusted) n-bit field of x that
begins at position
p=2E We assume that bit position 0 is at the right end and that n and p
are sensible positive
values. For example, getbits(x,4,3) returns the three bits in positions
4, 3 and 2,
right-adjusted.

Sponsored Links