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

[vortura]

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) {
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

 

[Ben Bacarisse]

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) {
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>

 

[Thad Smith]

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]

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..."!

 

[vortura]

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.

 

[Ben Bacarisse]

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".

 

[Seebs]

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