Author |
Topic: Integer Reversal (Read 1650 times) |
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender: 
Posts: 4489
|
 |
Integer Reversal
« on: May 22nd, 2004, 9:01am » |
 Quote  Modify
|
What is the shortest C function that takes an int as argument and returns an int with all the bits of the argument reversed? That is, the jth bit of the result is the (n-j)th bit of the argument, where n is the width of an int in bits.
(The function must work for arbitrary widths and not make any assumptions about the size of int or char.)
|
| « Last Edit: May 22nd, 2004, 9:13am by ThudnBlunder » |
 IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Integer Reversal
« Reply #1 on: May 22nd, 2004, 9:54am » |
Quote Modify
|
"no assumptions" means that the source should work on a hypothetical computer with 777-bit integers?
"shortest", does it mean in source size or in execution speed?
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Integer Reversal
« Reply #2 on: May 22nd, 2004, 10:17am » |
Quote Modify
|
Quote:| "shortest", does it mean in source size or in execution speed? |
|
Source size, the number of its characters.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Integer Reversal
« Reply #3 on: May 22nd, 2004, 3:15pm » |
Quote Modify
|
unsigned rev1(unsigned n){
unsigned m;
for(m=n%2,n=~(~n/2);n-1;n/=2)m+=m+n%2;
return m;
}
PS: unfortunately, it won't work with int's
|
| « Last Edit: May 22nd, 2004, 3:20pm by Grimbal » |
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer Reversal
« Reply #4 on: May 23rd, 2004, 9:29am » |
Quote Modify
|
ten more characters, but it works with int 
int rev(int n)
{
unsigned r=0, m=(unsigned)n, c=1;
for(;c>r;c*=2){r=r*2+m%2;m/=2;}
return (int)r;
}
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Integer Reversal
« Reply #5 on: May 23rd, 2004, 10:56am » |
Quote Modify
|
Still can be shortened.
rev3(n){
int r=0,c=1;
for(;c;c*=2)r+=r+(n&1),n>>=1;
return r;
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer Reversal
« Reply #6 on: May 23rd, 2004, 11:04am » |
Quote Modify
|
why not
r+=r+n%2
instead of?
r+=r+(n&1)
And what about the types? Or are we ignoring compiler warnings?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Integer Reversal
« Reply #7 on: May 23rd, 2004, 11:33am » |
Quote Modify
|
How about
:
b(n){return n?b(n<<1)<<1|n<0:0;}
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Integer Reversal
« Reply #9 on: May 23rd, 2004, 11:54am » |
Quote Modify
|
towr: n%2 doesn't give 0 or 1 with negative numbers
With gcc, I get no warning. I probably depends on your compiler.
THUDandBLUNDER: nice code! You still can replace <<1 by *2
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Integer Reversal
« Reply #10 on: May 23rd, 2004, 12:06pm » |
Quote Modify
|
on May 23rd, 2004, 11:54am, grimbal wrote:| With gcc, I get no warning. I probably depends on your compiler. |
|
Must depend on the version then as well, as I also used gcc..
|
| « Last Edit: May 23rd, 2004, 12:24pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Integer Reversal
« Reply #11 on: May 23rd, 2004, 12:17pm » |
Quote Modify
|
I got the problem here.
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Integer Reversal
« Reply #12 on: May 23rd, 2004, 1:05pm » |
Quote Modify
|
Aha. They even thought of the *2, but consider it is not ANSI conforming, because there would be an overflow to the sign bit.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Integer Reversal
« Reply #13 on: May 23rd, 2004, 1:15pm » |
Quote Modify
|
on May 23rd, 2004, 1:05pm, grimbal wrote:| Aha. They even thought of the *2, but consider it is not ANSI conforming, because there would be an overflow to the sign bit. |
|
I would have pointed that out but I wouldn't have known what I was talking about as I don't know C.
(And I always know what I am talking about.) 
|
| « Last Edit: May 26th, 2004, 8:14am by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print