473,326 Members | 2,048 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,326 software developers and data experts.

Rotate

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

Nov 15 '05 #1
16 4644
sl****************@hotmail.com writes:
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.
--
"The way I see it, an intelligent person who disagrees with me is
probably the most important person I'll interact with on any given
day."
--Billy Chambless
Nov 15 '05 #2

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...
sl****************@hotmail.com writes:
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.


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))
}
Nov 15 '05 #3
"James Harris" <no.email.please> writes:
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.
--
"It wouldn't be a new C standard if it didn't give a
new meaning to the word `static'."
--Peter Seebach on C99
Nov 15 '05 #4

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...
"James Harris" <no.email.please> writes:
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.


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."
Nov 15 '05 #5
"James Harris" <no.email.please> writes:
"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...
"James Harris" <no.email.please> writes:
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))
}


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


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.
--
int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuv wxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
Nov 15 '05 #6
sl****************@hotmail.com wrote:
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

--
Peter

Nov 15 '05 #7
Peter Nilsson wrote:

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.

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain
Nov 15 '05 #8
Richard Heathfield wrote
(in article
<dc**********@nwrdmz01.dmz.ncs.ea.ibs-infra.bt.com>):
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.
--
Randy Howard (2reply remove FOOBAR)

Nov 15 '05 #9
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, with the
evidence available to all the google eyed? It won't take jailing
threats to uncover.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 15 '05 #10
CBFalconer 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).

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
mail: rjh at above domain
Nov 15 '05 #11
Richard Heathfield wrote
(in article
<dc**********@nwrdmz02.dmz.ncs.ea.ibs-infra.bt.com>):
CBFalconer 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.

--
Randy Howard (2reply remove FOOBAR)

Nov 15 '05 #12
Randy Howard wrote:
Richard Heathfield wrote
CBFalconer 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.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
Nov 15 '05 #13

"Ben Pfaff" <bl*@cs.stanford.edu> wrote in message
news:87************@benpfaff.org...
<snip>
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.


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.

--
James
Nov 15 '05 #14
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).

--
pete
Nov 15 '05 #15

"pete" <pf*****@mindspring.com> wrote in message
news:42**********@mindspring.com...

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!

--
Thx,
James
Nov 15 '05 #16
James Harris wrote:

"pete" <pf*****@mindspring.com> wrote in message
news:42**********@mindspring.com...

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

--
pete
Nov 15 '05 #17

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

7
by: Showjumper | last post by:
Hi, I have developed an upload server controls to be reused over a number of projects. One of the tasks it needs to handle is to rotate an image. I want to accoplish this by checking the checkbox...
3
by: byrd48 | last post by:
Hi, I am developing a web site which allows users to upload and share photos. I have a datalist which lists the photos and has the usual edit, update commands. Within the edititemtemplate, I...
2
by: Peter Proost | last post by:
Hi group, I got the following piece of code which draws a square with stars round it, now I want the stars to rotate round the square, I can do this with the mx.rotate and a timer and an...
17
by: santel_helvis | last post by:
Hi All, Could anyone tell me how to rotate the image in javascript. Which concepts I should concentrate to rotate the image
1
by: iwdu15 | last post by:
hi, im trying to rotate a gdi drawn object on my form with a keypress....forinstance when i push the down arrow, for it to rotate the object drawn until the top is down, or if i push the right...
8
by: lovecreatesbeauty | last post by:
I write a function to rotate a matrix by 90 degrees clockwise, this function works on a matrix of specific size, for example, it rotates a 4*4 matrix of integers in the following code. The function...
1
by: RC | last post by:
First, this is a SVG issue, not 100% of XML issue. But I can't find SVG group to post this. Since SVG is XML file, I post here hopefully someone know both SVG and XML can help. Here is my SVG...
8
by: Samuel Shulman | last post by:
Is it possible and how to rotate pictures in HTML document Thank you, Samuel
10
by: Joey_Stacks | last post by:
Does anyone know of a scipt that will rotate random div layers on page refresh? I have a primary content area front and center on my site homepage, and I'd like to rotate various chunks of html...
2
by: Dariusz.Donimirski | last post by:
I must rotate bmp using Xlib without change bmp's memory. If someone knows how I can do this, please help me. dariusz sorry about my english, I'm still learning
0
by: DolphinDB | last post by:
Tired of spending countless mintues downsampling your data? Look no further! In this article, you’ll learn how to efficiently downsample 6.48 billion high-frequency records to 61 million...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...
0
isladogs
by: isladogs | last post by:
The next Access Europe User Group meeting will be on Wednesday 3 Apr 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM). In this session, we are pleased to welcome former...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.