Author |
Topic: Reverse a number (Read 1269 times) |
|
u07103
Newbie
Gender: 
Posts: 6
|
 |
Reverse a number
« on: Nov 2nd, 2008, 11:42am » |
 Quote  Modify
|
How do you reverse a number using bitwise operator only...cud not find a related thread!!!!
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reverse a number
« Reply #1 on: Nov 2nd, 2008, 12:31pm » |
Quote Modify
|
It's here
Basically split the number in parts using bitmasks, and then use shifts to reorder the parts.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
u07103
Newbie
Gender:
Posts: 6
|
|
Re: Reverse a number
« Reply #2 on: Nov 2nd, 2008, 9:58pm » |
Quote Modify
|
dis wud just reverse the binary representation...question says reverse the number...i.e. rev(1234) = 4321
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reverse a number
« Reply #3 on: Nov 3rd, 2008, 2:11am » |
Quote Modify
|
That would just reverse the decimal representation. There is no such thing as a reversed number. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Reverse a number
« Reply #4 on: Apr 16th, 2009, 6:34pm » |
Quote Modify
|
on Nov 3rd, 2008, 2:11am, towr wrote:| That would just reverse the decimal representation. |
|
I didn't get it. How will reversing the binary representation of a number reverse the number in decimal too. For example 12 = (1100) -> reversed to 0011 = 3.
Quote:| There is no such thing as a reversed number. |
|
What did you mean?
|
| « Last Edit: Apr 16th, 2009, 6:35pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reverse a number
« Reply #5 on: Apr 17th, 2009, 12:08am » |
Quote Modify
|
on Apr 16th, 2009, 6:34pm, R wrote:| I didn't get it. How will reversing the binary representation of a number reverse the number in decimal too. |
|
It won't. Not generally, at least.
Quote:There is a difference between a number and its representation. A number is not something that can be reversed. At least I don't see how. It's not that type of concept.
Confusing a number with any of its representations, whether binary or decimal is just, well, confused. It's like saying the reverse of walking north is htron gniklaw, rather than walking south. "Walking north" is just a representation in words of an action; you don't get the reverse of the action by reversing its representation. Likewise you don't get the reverse of a number by reversing any of its representations.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Reverse a number
« Reply #6 on: Apr 17th, 2009, 12:20am » |
Quote Modify
|
on Apr 17th, 2009, 12:08am, towr wrote:
There is a difference between a number and its representation. A number is not something that can be reversed. At least I don't see how. It's not that type of concept.
Confusing a number with any of its representations, whether binary or decimal is just, well, confused. It's like saying the reverse of walking north is htron gniklaw, rather than walking south. "Walking north" is just a representation in words of an action; you don't get the reverse of the action by reversing its representation. Likewise you don't get the reverse of a number by reversing any of its representations. |
|
Ok I get your point about definition of "Reverse". But I think, this question is just about calculating a number which contains digits of the given number N, in the reverse order. And it is not about the mathematical or ideal definition of REVERSE.
It is just one of the number manipulating programming exercise. Isn't it?
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reverse a number
« Reply #7 on: Apr 17th, 2009, 1:58am » |
Quote Modify
|
on Apr 17th, 2009, 12:20am, R wrote:| It is just one of the number manipulating programming exercise. Isn't it? |
|
Yeah. But if it isn't specified, reversing the binary representation makes more sense to me than reversing the decimal one. Especially if you're using only bitwise operators.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Reverse a number
« Reply #8 on: Apr 17th, 2009, 8:26am » |
Quote Modify
|
on Apr 17th, 2009, 1:58am, towr wrote:
Yeah. But if it isn't specified,
|
|
In Reply#2, the original poster of this questions has specified the meaning.
Quote:
reversing the binary representation makes more sense to me than reversing the decimal one. Especially if you're using only bitwise operators.
|
|
That is a question on the correctness of this prblem. May be the original poster mis-interpreted the question from where he heard it.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
oldspy
Newbie
Posts: 9
|
|
Re: Reverse a number
« Reply #9 on: May 15th, 2009, 5:16pm » |
Quote Modify
|
For dicimal version, it's simply. Get one digit a time from right and push it to the result from right:
int reverseDicimal( int n )
{
int res = 0;
int factor = 1;
int digit = 0;
while ( n != 0 )
{
digit = n % 10;
res = (res + digit ) * factor;
factor *= 10;
n = ( n - digit ) / 10;
}
return res;
}
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Reverse a number
« Reply #10 on: May 16th, 2009, 2:39am » |
Quote Modify
|
on May 15th, 2009, 5:16pm, oldspy wrote:| For dicimal version, it's simply. Get one digit a time from right and push it to the result from right: |
|
The question requires you to use only bitwise operators, you're not using them at all and are instead using only arithmetic operators which indeed makes it very simple.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reverse a number
« Reply #11 on: May 16th, 2009, 6:27pm » |
Quote Modify
|
There is still the possibility that the number is supposed to be encoded in EBCDIC.
|
|
IP Logged |
|
|
|
oldspy
Newbie
Posts: 9
|
|
Re: Reverse a number
« Reply #12 on: May 16th, 2009, 7:07pm » |
Quote Modify
|
For binary reverse, here are the steps:
Write a loop to swap all adjacent bit blocks where bit block span from 1 to half of the total bits of the number.
|
|
IP Logged |
|
|
|
oldspy
Newbie
Posts: 9
|
|
Re: Reverse a number
« Reply #13 on: May 16th, 2009, 7:29pm » |
Quote Modify
|
Here is the code:
int reverseBits( int n )
{
int mask = 1;
int i = 1;
int bits = 8 * sizeof n;
while ( i < bits )
{
int mask2 = mask;
int tmp = 0;
int k = 0;
// swap all adjacent blocks with span of i bits
do
{
tmp += ((n & mask2) << i ) + ((n & (mask2 << i)) >> i );
mask2 = mask2 << (2*i);
k += 2*i;
}
while ( k < bits );
n = tmp;
i = i << 1;
mask = (1 << i) - 1;
}
return n;
}
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Reverse a number
« Reply #14 on: May 18th, 2009, 1:15am » |
Quote Modify
|
That looks like O(#bits) to me. In the first outer loop you are swapping every pair of bits. You might just as well swap them one by one to where they belong.
int reverseBits( int n )
{
int rev = 0;
unsigned mask1 = 1;
unsigned mask2 = ~(~0U>>1);
while( mask1<mask2 ){
if( mask1 & n ) rev |= mask2;
if( mask2 & n ) rev |= mask1;
mask1 >>= 1;
mask2 <<= 1;
}
return rev;
}
int bits = 8 * sizeof n;
|
|
IP Logged |
|
|
|
oldspy
Newbie
Posts: 9
|
|
Re: Reverse a number
« Reply #15 on: May 18th, 2009, 1:33am » |
Quote Modify
|
Yeah. It's bits - 1. But the algorithm can be improved to get to O(log (bits)).
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print