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

Discussion in 'C Programming' started by vortura, May 16, 2010.

1. ### vorturaGuest

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&R2_solutions:Chapter_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) {
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

vortura, May 16, 2010

2. ### Ben BacarisseGuest

vortura <> 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&R2_solutions:Chapter_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);
> 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.

Ben Bacarisse, May 17, 2010

3. ### Thad SmithGuest

Ben Bacarisse wrote:
> vortura <> 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&R2_solutions:Chapter_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 Smith, May 17, 2010
4. ### Ben BacarisseGuest

Thad Smith <> writes:

> Ben Bacarisse wrote:
>> vortura <> 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&R2_solutions:Chapter_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.

Ben Bacarisse, May 17, 2010
5. ### vorturaGuest

On May 17, 12:00 am, Ben Bacarisse <> 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

vortura, May 17, 2010
6. ### Ben BacarisseGuest

vortura <> writes:

> On May 17, 12:00Â am, Ben Bacarisse <> 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.

Ben Bacarisse, May 17, 2010
7. ### SeebsGuest

On 2010-05-17, Ben Bacarisse <> wrote:
> vortura <> writes:
>> On May 17, 12:00 am, Ben Bacarisse <> 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.seebs.net/log/ <-- lawsuits, religion, and funny pictures
http://en.wikipedia.org/wiki/Fair_Game_(Scientology) <-- get educated!

Seebs, May 17, 2010