Rotate

[slashdotcommacolon]

Hello, is this the correct solution to Exercise 2-7 of K&R, it seems to
work but using sizeof(x)*8-n to shift the saved bits that would get
lost to the end seems like cheating:

unsigned int rightrot (unsigned int x, int n)
{
return ~(~(x >> n) ^ ((x & ~(~0 << n))<<((sizeof (x)*8)-n)));
}

Any advice appreciated.

p.s. "Write a function rightrot(x,n) that returns the value of the
integer x rotated to the right by n bit positions".

 

[Ben Pfaff]

unsigned int rightrot (unsigned int x, int n)
{
return ~(~(x >> n) ^ ((x & ~(~0 << n))<<((sizeof (x)*8)-n)));
}

p.s. "Write a function rightrot(x,n) that returns the value of the
integer x rotated to the right by n bit positions".

A few comments:

* This will only be well-defined for n of least 0 and
strictly less than the number of bits in an unsigned
int, because shifting by a count outside that range
yields undefined behavior.

* I don't understand why you use ~ so much, nor do I
understand why ^ is preferred to |.

* The number of bits in a byte may vary from one
implementation to another. You can use CHAR_BIT from
<limits.h> to find out the number of bits per byte.

* An `unsigned int' might have fewer value bits than the
size of its representation implies.

 

[James Harris]

A few comments:

* This will only be well-defined for n of least 0 and
strictly less than the number of bits in an unsigned
int, because shifting by a count outside that range
yields undefined behavior.

* I don't understand why you use ~ so much, nor do I
understand why ^ is preferred to |.

* The number of bits in a byte may vary from one
implementation to another. You can use CHAR_BIT from
<limits.h> to find out the number of bits per byte.

* An `unsigned int' might have fewer value bits than the
size of its representation implies.

I'll have a go. Keeping to the strict question I'll use a signed int but
I guess the result for negative numbers is implementation dependent.

#include <limits.h>
int rightrot(int x, unsigned int n) {
unsigned int n1 = n % WORD_BIT; /* No. of bits in an int */
return (x >> n1) | (x << (WORD_BIT - n1))
}

 

[Ben Pfaff]

I'll have a go. Keeping to the strict question I'll use a signed int but
I guess the result for negative numbers is implementation dependent.

#include <limits.h>
int rightrot(int x, unsigned int n) {
unsigned int n1 = n % WORD_BIT; /* No. of bits in an int */
return (x >> n1) | (x << (WORD_BIT - n1))
}

Not quite--if n1 == 0 then shifting left by WORD_BIT - n1 yields
undefined behavior.

Also, `x' should be unsigned.

 

[James Harris]

Not quite--if n1 == 0 then shifting left by WORD_BIT - n1 yields
undefined behavior.

You are right (but you knew that anyway!) Just looked up the standard
and it says, "The result is undefined if the right operand is negative,
or greater than or equal to the number of bits in the left expression's
type."

Also, `x' should be unsigned.

The standard I have says here, "The right shift is equivalent to
division by 2^E1 if E1 is unsigned or if it has a non-negative value;
otherwise the result is implementation-defined."

 

[Ben Pfaff]

The standard I have says here, "The right shift is equivalent to
division by 2^E1 if E1 is unsigned or if it has a non-negative value;
otherwise the result is implementation-defined."

Is your routine designed to work only for non-negative values of
`x'? Even then, it is incorrect, because even for non-negative
`x' it can left-shift 1 bits past the leftmost value bit in `x',
which yields undefined behavior for signed integer types.

 

[Peter Nilsson]

Hello, is this the correct solution to Exercise 2-7 of K&R,

Not even close! ITYM 2-8.

it seems
to work but using sizeof(x)*8-n to shift the saved bits that would
get lost to the end seems like cheating:

I've yet to encounter a circumstance where I might want to rotate
over the entire (arbitrary) width of an unsigned type. Normally,
I wish to rotate over a precise number of bits, e.g. 16 or 32.

unsigned int rightrot (unsigned int x, int n)
{
return ~(~(x >> n) ^ ((x & ~(~0 << n))<<((sizeof (x)*8)-n)));
}

Any advice appreciated.

p.s. "Write a function rightrot(x,n) that returns the value of the
integer x rotated to the right by n bit positions".

/* Note: n in [0..width), where width is the number of value bits
// in an unsigned int.
*/
unsigned rightrot(unsigned x, int n)
{
return (x >> n) | (x * ((-1u >> n) + 1));
}

If n is generally a constant, then it's likely to be better to
implement this as a macro, thus the compiler stands a better
chance of optimising out the multiplication.

If you want to (reluctantly) include n == width, then you can do..

unsigned rightrot(unsigned x, int n)
{
return
(n == 0)
? x
: (x >> (n - 1) >> 1) | (x * ((-1u >> (n - 1) >> 1) + 1));
}

Richard Heathfield has a site on K&R2 exercises at...

http://users.powernet.co.uk/eton/kandr2/index.html

 

[Richard Heathfield]

Richard Heathfield has a site on K&R2 exercises at...

http://users.powernet.co.uk/eton/kandr2/index.html

s/has/had/

I no longer maintain that site, and do not in fact have write access to it.

I have not yet decided whether to incorporate a K&R2 answers section on my
new site; it was a big time drain.

 

[Joe Wright]

Peter Nilsson wrote:




s/has/had/

I no longer maintain that site, and do not in fact have write access to it.

I have not yet decided whether to incorporate a K&R2 answers section on my
new site; it was a big time drain.

Good to have you back Richard. Can you share the story with us?

What were you doing before you left?
What made you leave?
What have you done since you left?
Why did you come back?
What are you doing now?

Enquiring minds want to know..

Again, it's good to see you.

 

[Richard Heathfield]

Good to have you back Richard. Can you share the story with us?

What were you doing before you left?
What made you leave?
What have you done since you left?
Why did you come back?
What are you doing now?

Enquiring minds want to know..

Once upon a time, to cut a long story short, the end.

I don't think there was a single overwhelming factor in my "leaving"
comp.lang.c - I can't quite remember now but I think I was trying to sort
out my Web site or something, and I changed ISP, and for a while I didn't
have any decent protection against spam, and I moved house, and I trashed
my Linux box and ended up using a Win98(!) laptop for a while, etc etc -
one distraction after another after another after another. Usenet just sort
of didn't happen for a while.

I finally sorted out another Linux box, thank heaven, and then one day I
bumped into KNode and thought, "Oh, hello old friend - which reminds me, I
wonder if clc is still around?", and it was, and here I am.

Again, it's good to see you.

Thanks.

 

[Randy Howard]

Richard Heathfield wrote
(in article

Once upon a time, to cut a long story short, the end.

[snip]

We know the truth, you are just covering up your secret life as
a British spy. Oops, I hope I didn't just become part of
another scandal over leaking secret identities.

 

[CBFalconer]

Richard Heathfield wrote

Once upon a time, to cut a long story short, the end.

[snip]

We know the truth, you are just covering up your secret life as
a British spy. Oops, I hope I didn't just become part of
another scandal over leaking secret identities.

Are you also going to spend a year or so lying about it, with the
evidence available to all the google eyed? It won't take jailing
threats to uncover.

 

[Richard Heathfield]

Richard Heathfield wrote

Once upon a time, to cut a long story short, the end.

[snip]

We know the truth, you are just covering up your secret life as
a British spy. Oops, I hope I didn't just become part of
another scandal over leaking secret identities.

Are you also going to spend a year or so lying about it,

I think that's a bit harsh. Randy H was just perpetuating an old
comp.programming in-joke (as I suspect you know already).

 

[Randy Howard]

Richard Heathfield wrote
(in article

Richard Heathfield wrote

Once upon a time, to cut a long story short, the end.
[snip]

We know the truth, you are just covering up your secret life as
a British spy. Oops, I hope I didn't just become part of
another scandal over leaking secret identities.

Are you also going to spend a year or so lying about it,

I think that's a bit harsh. Randy H was just perpetuating an old
comp.programming in-joke (as I suspect you know already).

I think he was making a political comment with respect to the
current Washington, D.C. fire-of-the-week.

 

[CBFalconer]

Richard Heathfield wrote

Randy Howard wrote:
Richard Heathfield wrote

Once upon a time, to cut a long story short, the end.
[snip]

We know the truth, you are just covering up your secret life as
a British spy. Oops, I hope I didn't just become part of
another scandal over leaking secret identities.

Are you also going to spend a year or so lying about it,

I think that's a bit harsh. Randy H was just perpetuating an old
comp.programming in-joke (as I suspect you know already).

I think he was making a political comment with respect to the
current Washington, D.C. fire-of-the-week.

Yes, thanks. Looking back it really should have had at least a
smiley or two. It was not well worded.

 

[James Harris]

Is your routine designed to work only for non-negative values of
`x'? Even then, it is incorrect, because even for non-negative
`x' it can left-shift 1 bits past the leftmost value bit in `x',
which yields undefined behavior for signed integer types.

Yes, I can see that the data type should be declared as unsigned. I'm
unsure, though, if I have a function declared

.... func(unsigned int x)

how this will react if called with

int i;
....
....func(i);

Before you say, I searched a c.l.c faq I found from google for keywords
such as promot and arg but no joy.

 

[pete]

James Harris wrote:

Yes, I can see that the data type should be declared as unsigned. I'm
unsure, though, if I have a function declared

... func(unsigned int x)

how this will react if called with

int i;
...
...func(i);

Before you say,
I searched a c.l.c faq I found from google for keywords
such as promot and arg but no joy.

It will be as though

....func((unsigned)i);

The rules for converting int i to unsigned x are
1 If i is greater than UINT_MAX,
then subtract (UINT_MAX + 1) from i repeatedly,
until i isn't greater than UINT_MAX.
2 If i is negative,
then add (UINT_MAX + 1) to i repeatedly,
until i isn't negative.
3 If the value of i is within the range for unsigned,
keep the magnitude of the value the same.

func(-1) is the same as func(UINT_MAX).

 

[James Harris]

It will be as though

...func((unsigned)i);

The rules for converting int i to unsigned x are
1 If i is greater than UINT_MAX,
then subtract (UINT_MAX + 1) from i repeatedly,
until i isn't greater than UINT_MAX.
2 If i is negative,
then add (UINT_MAX + 1) to i repeatedly,
until i isn't negative.
3 If the value of i is within the range for unsigned,
keep the magnitude of the value the same.

func(-1) is the same as func(UINT_MAX).

That's complicated! So, taking 16-bit inclusive values if

i is between 0 and 32767 (0x0000 and 0x7fff) ==> value gets passed as
given
i is between -32768 and -1 (0x8000 and 0xffff) ==> value passed is taken
as 65536 + i
in other words between 32768 and 65535 (0x8000 and 0xffff) !

In other words for 2's complement same width integers the bit values are
reinterpreted and no computation is required. I guess that for 1's
complement there is an adjustment......

-1 (0xfffe) has to become 0xffff
-2 (0xfffd) has to become 0xfffe

(i.e. adding 1) so are you saying that a 1's complement machine would
have to test for the negative case and adjust the value accordingly?

I'm not going to try and work out the values if source and destination
are of different bit widths. It's too late!

 

[pete]

I guess that for 1's
complement there is an adjustment......

-1 (0xfffe) has to become 0xffff
-2 (0xfffd) has to become 0xfffe

(i.e. adding 1) so are you saying that a 1's complement machine would
have to test for the negative case and adjust the value accordingly?

The one's complement machine would have to go through whatever
gyrations it takes to make (-1 == UINT_MAX) true.

(-1 == UINT_MAX), is universally true,
regardless of two's complement,
one's complement or sign and magnitude.

Here's how it looks in N869:

6.3.1.3 Signed and unsigned integers
[#1] When a value with integer type is converted to another
integer type other than _Bool, if the value can be
represented by the new type, it is unchanged.
[#2] Otherwise, if the new type is unsigned, the value is
converted by repeatedly adding or subtracting one more than
the maximum value that can be represented in the new type
until the value is in the range of the new type.