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

# 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

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

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

regards,
Richard

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) {
> mask = ~(~0U << n) << (p + 1 - n);
> }

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.

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.

--

Ben Bacarisse
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.

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

--
Ben.

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

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.

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!