Velocity Reviews > the algorithm of decimal<->binary conversion

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

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/

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

......but I don't quite understand....

What does this mean??

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

Thx again.

Mars.

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

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

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

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.

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