Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > the algorithm of decimal<->binary conversion

Reply
Thread Tools

the algorithm of decimal<->binary conversion

 
 
Flash Gordon
Guest
Posts: n/a
 
      02-21-2005
Chris Williams wrote:
> Mars wrote:
>
>>ummm....
>>is this good enough??
>>
>>conv convert(long long input)
>>{
>> int pass;
>> conv rconv;
>>
>> rconv=init();
>>
>> while (1)
>> {
>> if ((input!=1)&&(input!=0))
>> {
>> pass=input%2;
>> input/=2;

>
>
> Division is slow (modulus is essentially division as well.)


Not on all systems.

> Also, a
> note on code comments for Usenet: Since lines can be permanently
> wrapped, you are best to put all comments in /* */ style if you are
> going to post. This allows people to copy and paste directly and still
> have it compile.


That is true.

> But I say this only because you have none.
>
> 2 >> 1 = 1 //division by two
> 4 >> 1 = 2
> 6 >> 1 = 3
> 8 >> 1 = 4
> 8 >> 2 = 2 //division by four
>
> 1 & 1 = 1 //modulus of 2
> 2 & 1 = 0
> 3 & 1 = 1
> 4 & 1 = 0
> 4 & 2 = 0 //modulus of 4


Any decent optimising compiler will do this optimisation when dealing
with division by a constant. So it is generally better to write what you
mean rather than making the code harder to read.
--
Flash Gordon
Living in interesting times.
Although my email address says spam, it is real and I read it.
 
Reply With Quote
 
 
 
 
Mars
Guest
Posts: n/a
 
      02-21-2005
Chris Croughton mentioned:
> On Mon, 21 Feb 2005 01:18:35 +0800, Mars
> <Mars@Mars> wrote:
>
>
>>I'm writing a program for listing all binary numbers of the same length
>>with the same number of 1s.

>
>
> That's not what the subject line says.
>
>
>>it works perfectly...
>>but it seems too slow even when calculating binary numbers of length 20...

>
>
> Yes, that's a million (and a bit) tests.
>
>
>>(as this is a program for the demo online acm contest, time limit is set...)

>
>
> Ah. Might it be that you are looking to use someone else's work in a
> contest? Might that be considered just a tad unethical?
>


Rest assured.
That's just a DEMO contest system, all questions are past questions used
in the real ACM Contest.
Everyone can go register and try them.

http://acm.uva.es/problemset/
 
Reply With Quote
 
 
 
 
Mars
Guest
Posts: n/a
 
      02-21-2005
Peter Nilsson mentioned:
>
> % type nmo.c
> long strtol(const char*,char**,int);void q1(unsigned q2,int
> q3){unsigned q4=(q3>0)? 1u<<(q3-1):-1u/2 +1;for(;q4;q4>>=1)
> putchar('0'+!!(q2&q4));}int q5(unsigned q2){int q6;for(q6=0
> ;q2;q2&= q2-1,q6++);return q6 ;}int main(int q7,char **q{
> long q3,q4;unsigned q2,q9, q10;if(q7!=3)return 0;q3=strtol(
> q8[1],0,0);q4=strtol(q8[2],0,0);if(q3<1||q4<1||q3<q4||q3>q5
> (-1u))return 0;q2=(1u<<(q4-1)<<1)-1;q9=q2<<(q3-q4);for(;{
> q1(q2,q3);putchar('\n');if(q2==q9)break;q10=q2&-q2;q2+=q10+
> ((((q2+q10)&-(q2+q10))/q10)-1)/2;}return 0;}
>
>





Thx for your answer~
......but I don't quite understand....



What does this mean??

unsigned q4=(q3>0)? 1u<<(q3-1):-1u/2 +1;



Thx again.







Mars.
 
Reply With Quote
 
Mars
Guest
Posts: n/a
 
      02-21-2005
Peter Nilsson mentioned:
> Peter Nilsson wrote:
>


And what's that "1u" mean in your program??

e.g.
q2=(1u<<(q4-1)<<1)-1;

Thx~



Mars
 
Reply With Quote
 
Michael Mair
Guest
Posts: n/a
 
      02-21-2005


Mars wrote:
> Peter Nilsson mentioned:
>
>>
>> % type nmo.c
>> long strtol(const char*,char**,int);void q1(unsigned q2,int
>> q3){unsigned q4=(q3>0)? 1u<<(q3-1):-1u/2 +1;for(;q4;q4>>=1)
>> putchar('0'+!!(q2&q4));}int q5(unsigned q2){int q6;for(q6=0
>> ;q2;q2&= q2-1,q6++);return q6 ;}int main(int q7,char **q{
>> long q3,q4;unsigned q2,q9, q10;if(q7!=3)return 0;q3=strtol(
>> q8[1],0,0);q4=strtol(q8[2],0,0);if(q3<1||q4<1||q3<q4||q3>q5
>> (-1u))return 0;q2=(1u<<(q4-1)<<1)-1;q9=q2<<(q3-q4);for(;{
>> q1(q2,q3);putchar('\n');if(q2==q9)break;q10=q2&-q2;q2+=q10+
>> ((((q2+q10)&-(q2+q10))/q10)-1)/2;}return 0;}

>
> Thx for your answer~
> .....but I don't quite understand....


This may be a good part of the intention.


> What does this mean??
>
> unsigned q4=(q3>0)? 1u<<(q3-1):-1u/2 +1;


Shift left by q3, then rotate right by 1. Store the result in q4.


Cheers
Michael
--
E-Mail: Mine is a gmx dot de address.

 
Reply With Quote
 
Michael Mair
Guest
Posts: n/a
 
      02-21-2005


Mars wrote:
> Peter Nilsson mentioned:
>
>> Peter Nilsson wrote:
>>

>
> And what's that "1u" mean in your program??
>
> e.g.
> q2=(1u<<(q4-1)<<1)-1;


You were not there when they were talking about constants...

1 (int)
1u, 1U (unsigned int)
1l, 1L (long)
1UL, 1ul, 1LU, 1lu ....
1.0 (double)
1.0F,1.0f (float)
1.0L,1.0l (long double)


-Michael
--
E-Mail: Mine is a gmx dot de address.

 
Reply With Quote
 
Chris Williams
Guest
Posts: n/a
 
      02-22-2005
Flash Gordon wrote:
> Chris Williams wrote:
> > 2 >> 1 = 1 //division by two
> > 4 >> 1 = 2
> > 6 >> 1 = 3
> > 8 >> 1 = 4
> > 8 >> 2 = 2 //division by four
> >
> > 1 & 1 = 1 //modulus of 2
> > 2 & 1 = 0
> > 3 & 1 = 1
> > 4 & 1 = 0
> > 4 & 2 = 0 //modulus of 4

>
> Any decent optimising compiler will do this optimisation when dealing


> with division by a constant. So it is generally better to write what

you
> mean rather than making the code harder to read.


True. It's a two second test, but indeed there might be no change if
your compiler was spitting your code out using shifts and ands in
secret.

Though I was never big on trusting the compiler to do anything past
predetermining all math between constants--e.g. time = y + 1000 * 60;
-> time = y + 60000; Just the general idea that between knowing how to
do it myself or having the best optimizing compiler, I'd rather know
what I'm doing. Though I would want one for any large project to deal
with the 99% of code that won't be used intensively.

-Chris

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Conversion of sequential time-sensitive algorithm to VHDL Oliver Mattos VHDL 8 02-12-2011 03:40 AM
Pascal to C string conversion algorithm needed Guilbert STABILO C Programming 9 03-04-2009 12:02 PM
Filtered Back Projection Algorithm (FBP Algorithm) Bapaiah Katepalli VHDL 1 06-23-2006 04:50 PM
Date conversion algorithm - Help needed Se'noj C++ 9 11-04-2004 05:09 PM
Key generation algorithm and Cipher algorithm Ahmed Moustafa Java 0 11-15-2003 06:35 AM



Advertisments