wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Integer Reversal
        
(Message started by: THUDandBLUNDER on May 22^nd, 2004, 9:01am)

Title: Integer Reversal
Post by THUDandBLUNDER on May 22^nd, 2004, 9:01am

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 j^th 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.)

Title: Re: Integer Reversal
Post by grimbal on May 22^nd, 2004, 9:54am

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

Title: Re: Integer Reversal
Post by THUDandBLUNDER on May 22^nd, 2004, 10:17am

Quote:

"shortest", does it mean in source size or in execution speed?

Source size, the number of its characters.

Title: Re: Integer Reversal
Post by grimbal on May 22^nd, 2004, 3:15pm

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

Title: Re: Integer Reversal
Post by towr on May 23^rd, 2004, 9:29am

ten more characters, but it works with int :P

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;
}

Title: Re: Integer Reversal
Post by grimbal on May 23^rd, 2004, 10:56am

Still can be shortened.

rev3(n){
int r=0,c=1;
for(;c;c*=2)r+=r+(n&1),n>>=1;
return r;
}

Title: Re: Integer Reversal
Post by towr on May 23^rd, 2004, 11:04am

why not
r+=r+n%2
instead of?
r+=r+(n&1)

And what about the types? Or are we ignoring compiler warnings?

Title: Re: Integer Reversal
Post by THUDandBLUNDER on May 23^rd, 2004, 11:33am

How about
:
[hide]b(n){return n?b(n<<1)<<1|n<0:0;}[/hide]

Title: Re: Integer Reversal
Post by towr on May 23^rd, 2004, 11:45am

I can't compile it..
otherwise I'm sure it's fine :P

Title: Re: Integer Reversal
Post by grimbal on May 23^rd, 2004, 11:54am

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

Title: Re: Integer Reversal
Post by towr on May 23^rd, 2004, 12:06pm

on 05/23/04 at 11:54:25, 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..

Title: Re: Integer Reversal
Post by THUDandBLUNDER on May 23^rd, 2004, 12:17pm

I got the problem here (http://home.tiscalinet.ch/t_wolf/tw/misc/contest.html).

Title: Re: Integer Reversal
Post by grimbal on May 23^rd, 2004, 1:05pm

Aha. They even thought of the *2, but consider it is not ANSI conforming, because there would be an overflow to the sign bit.

Title: Re: Integer Reversal
Post by THUDandBLUNDER on May 23^rd, 2004, 1:15pm

on 05/23/04 at 13:05:11, 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.) ::)