Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > clc-wiki answer to K+R exercise 2-7

Reply
Thread Tools

clc-wiki answer to K+R exercise 2-7

 
 
vortura
Guest
Posts: n/a
 
      05-16-2010
Hello all,

I've been working through some of the exercises in the K&R book, and I
think I might have found a bug in one of the answers on the CLC wiki.
Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
the n bits starting at p inverted.

http://clc-wiki.net/wiki/K%26R2_solu...r_2:Exercise_7

The answer listed on the wiki creates a mask of n 1's, then left
shifts them by p before xor'ing with x. By left shifting the mask by
p though, I think the mask is shifted past p, meaning the wrong bits
are inverted by the XOR. I think the correct solution would left
shift the mask by (p + 1 - n) instead. e.g.

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

Is the answer in the wiki buggy, or have I made a mistake somewhere?

regards,
Richard
 
Reply With Quote
 
 
 
 
Ben Bacarisse
Guest
Posts: n/a
 
      05-16-2010
vortura <(E-Mail Removed)> writes:

> I've been working through some of the exercises in the K&R book, and I
> think I might have found a bug in one of the answers on the CLC wiki.
> Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
> the n bits starting at p inverted.
>
> http://clc-wiki.net/wiki/K%26R2_solu...r_2:Exercise_7
>
> The answer listed on the wiki creates a mask of n 1's, then left
> shifts them by p before xor'ing with x. By left shifting the mask by
> p though, I think the mask is shifted past p, meaning the wrong bits
> are inverted by the XOR. I think the correct solution would left
> shift the mask by (p + 1 - n) instead. e.g.


The switch from p to p + 1 - n is just a re-interpretation of what p
means. If p is the 0-based index of the LSB of the sequence, then the
wiki solution is correct. If it is the index of MSB if the sequence
then you are correct. I don't think K&R offer any definition so you are
free to choose. Given that the wiki interpretation is simpler, I'd go
with that one.

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


To invert these bits:

...00000xxx00

you would call invert(x, 4, 3) -- the three bits at position 4 -- but
the wiki solution considers this to be the 3 bits at position 2:
invert(x, 2, 3).

<snip>
--
Ben.
 
Reply With Quote
 
 
 
 
Thad Smith
Guest
Posts: n/a
 
      05-17-2010
Ben Bacarisse wrote:
> vortura <(E-Mail Removed)> writes:
>
>> I've been working through some of the exercises in the K&R book, and I
>> think I might have found a bug in one of the answers on the CLC wiki.
>> Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
>> the n bits starting at p inverted.
>>
>> http://clc-wiki.net/wiki/K%26R2_solu...r_2:Exercise_7
>>
>> The answer listed on the wiki creates a mask of n 1's, then left
>> shifts them by p before xor'ing with x. By left shifting the mask by
>> p though, I think the mask is shifted past p, meaning the wrong bits
>> are inverted by the XOR. I think the correct solution would left
>> shift the mask by (p + 1 - n) instead. e.g.

>
> The switch from p to p + 1 - n is just a re-interpretation of what p
> means.


No, it's a re-interpretation of assignment order for "n bits starting at p" (in
both cases p means p'th bit starting with bit 0 as LSB). Do you start at bit p
and go through higher bit numbers or start at p and go through lower bit
numbers? If I said "I want tickets for the three consecutive seats starting at
seat 5", most people would expect me to get seats 5, 6, and 7, not 3, 4, and 5.

--
Thad
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      05-17-2010
Thad Smith <(E-Mail Removed)> writes:

> Ben Bacarisse wrote:
>> vortura <(E-Mail Removed)> writes:
>>
>>> I've been working through some of the exercises in the K&R book, and I
>>> think I might have found a bug in one of the answers on the CLC wiki.
>>> Exercise 2-7 asks for a function, invert(x, p, n) that returns x with
>>> the n bits starting at p inverted.
>>>
>>> http://clc-wiki.net/wiki/K%26R2_solu...r_2:Exercise_7
>>>
>>> The answer listed on the wiki creates a mask of n 1's, then left
>>> shifts them by p before xor'ing with x. By left shifting the mask by
>>> p though, I think the mask is shifted past p, meaning the wrong bits
>>> are inverted by the XOR. I think the correct solution would left
>>> shift the mask by (p + 1 - n) instead. e.g.

>>
>> The switch from p to p + 1 - n is just a re-interpretation of what p
>> means.

>
> No, it's a re-interpretation of assignment order for "n bits starting
> at p" (in both cases p means p'th bit starting with bit 0 as LSB). Do
> you start at bit p and go through higher bit numbers or start at p and
> go through lower bit numbers? If I said "I want tickets for the three
> consecutive seats starting at seat 5", most people would expect me to
> get seats 5, 6, and 7, not 3, 4, and 5.


Which is what I thought I said. Is your point that I should have been
more dogmatic about which one is correct? I.e. that interpreting p to
be the MSB of the run being inverted is unusual enough to be wrong? If
so, I won't disagree but I would not have made that point by starting a
reply with "No..."!

--
Ben.
 
Reply With Quote
 
vortura
Guest
Posts: n/a
 
      05-17-2010
On May 17, 12:00*am, Ben Bacarisse <(E-Mail Removed)> wrote:
> The switch from p to p + 1 - n is just a re-interpretation of what p
> means. *If p is the 0-based index of the LSB of the sequence, then the
> wiki solution is correct. *If it is the index of MSB if the sequence
> then you are correct. *I don't think K&R offer any definition so you are
> free to choose. *Given that the wiki interpretation is simpler, I'd go
> with that one.


Thanks Ben. I see what you're saying - that there are a couple of
ways in which p could be interpreted. The way I chose to interpret it
was based on the getbits() example in K&R immediately preceding
exercises 2-6 and 2-7, which says:

'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 bit positions 4, 3, and 2, right adjusted.'

If the same assumptions about p hold for the exercises, then I believe
my answer is correct. Also, it seems that the wiki answers to
exercises 2-6 and 2-7 each take a different approach. 2-6 takes p
(like I have), as index of the MSB of the sequence, while 2-7 takes it
to be the index of the LSB of the sequence.

--
Richard
 
Reply With Quote
 
Ben Bacarisse
Guest
Posts: n/a
 
      05-17-2010
vortura <(E-Mail Removed)> writes:

> On May 17, 12:00*am, Ben Bacarisse <(E-Mail Removed)> wrote:
>> The switch from p to p + 1 - n is just a re-interpretation of what p
>> means.

<snip>
> If the same assumptions about p hold for the exercises, then I believe
> my answer is correct. Also, it seems that the wiki answers to
> exercises 2-6 and 2-7 each take a different approach. 2-6 takes p
> (like I have), as index of the MSB of the sequence, while 2-7 takes it
> to be the index of the LSB of the sequence.


Yes, but as Thad Smith points out, taking "3 bits at position 4" to mean
bits 2, 3 and 4 is a little odd to say the least. Those bits should
designated "3 bits at position 2".

--
Ben.
 
Reply With Quote
 
Seebs
Guest
Posts: n/a
 
      05-17-2010
On 2010-05-17, Ben Bacarisse <(E-Mail Removed)> wrote:
> vortura <(E-Mail Removed)> writes:
>> On May 17, 12:00*am, Ben Bacarisse <(E-Mail Removed)> wrote:
>>> The switch from p to p + 1 - n is just a re-interpretation of what p
>>> means.

><snip>
>> If the same assumptions about p hold for the exercises, then I believe
>> my answer is correct. Also, it seems that the wiki answers to
>> exercises 2-6 and 2-7 each take a different approach. 2-6 takes p
>> (like I have), as index of the MSB of the sequence, while 2-7 takes it
>> to be the index of the LSB of the sequence.


> Yes, but as Thad Smith points out, taking "3 bits at position 4" to mean
> bits 2, 3 and 4 is a little odd to say the least. Those bits should
> designated "3 bits at position 2".


I'm not sure about that. It seems to me that the natural thing is to number
bits by significance, so 0x01 is position 0, 0x02 is position 1, and so on.

But if I am talking about consecutive digits, I normally count down. Three
digits, starting in the millions place, is 111.....; so if position four is
0b10000, then three bits starting at position four would be 0b11100, because
it seems intuitive to me to count that way...

.... But if we're talking about a numbered set of bits, it probably makes sense
to go the other way.

-s
--
Copyright 2010, all wrongs reversed. Peter Seebach / http://www.velocityreviews.com/forums/(E-Mail Removed)
http://www.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modified answer to Accelerated C++ Exercise 11-6 stops linking? zackp C++ 5 01-05-2010 06:16 PM
Answer to C++ Primer 4th edition Exercise 1.20 (in section 1.4.4) mmdspam@googlemail.com C++ 0 05-26-2008 05:41 PM
Wrong answer equals to a blank answer or not? Zadkin Microsoft Certification 8 06-27-2006 01:51 PM
Cisco Student VPN exercise problem : gen_unrfrag: fail to generate unreachable, unexpected args robert Cisco 0 06-02-2004 07:33 PM



Advertisments