the algorithm of decimal<->binary conversion

Discussion in 'C Programming' started by Mars, Feb 20, 2005.

  1. Mars

    Mars Guest

    I'm writing a program for listing all binary numbers of the same length
    with the same number of 1s.

    e.g.
    0011
    0101
    0110
    1001
    1010
    1100

    my algorithm is as follows...
    0. use a formula to calculate the number of numbers
    1. temp=1; outputed=0;
    2. count from 1 to 2 to the power of the required length
    2.1 convert temp to a binary number in a char[]
    2.1.1 temp/2 get remainder
    2.1.2 blah blah blah.........
    2.1.2.1 if no. of 1s == required no., output+1, printf
    2.2 temp+1;
    2.3 if output>=the value calculated, break

    it works perfectly...
    but it seems too slow even when calculating binary numbers of length 20...
    (as this is a program for the demo online acm contest, time limit is set...)

    how can I make it more efficient????


    Thx~~~~



    Mars.
    Mars, Feb 20, 2005
    #1
    1. Advertising

  2. Mars

    infobahn Guest

    Mars wrote:
    >
    > I'm writing a program for listing all binary numbers of the same length
    > with the same number of 1s.
    >

    <snip>
    >
    > it works perfectly...
    > but it seems too slow even when calculating binary numbers of length 20...
    > (as this is a program for the demo online acm contest, time limit is set...)
    >
    > how can I make it more efficient????


    Make sure you are using an efficient algorithm.
    Use a profiler to identify the principal bottleneck.
    Rewrite the bottleneck code.
    Iterate until fast enough.
    infobahn, Feb 20, 2005
    #2
    1. Advertising

  3. Mars

    Mars Guest

    infobahn mentioned:
    > Mars wrote:
    >
    >>I'm writing a program for listing all binary numbers of the same length
    >>with the same number of 1s.
    >>

    >
    > <snip>
    >
    >>it works perfectly...
    >>but it seems too slow even when calculating binary numbers of length 20...
    >>(as this is a program for the demo online acm contest, time limit is set...)
    >>
    >>how can I make it more efficient????

    >
    >
    > Make sure you are using an efficient algorithm.
    > Use a profiler to identify the principal bottleneck.
    > Rewrite the bottleneck code.
    > Iterate until fast enough.




    ummm....
    is this good enough??



    typedef struct
    {
    char bits[2000];
    int pointer;
    int length;

    }conv;

    conv convert(long long input)
    {
    int pass;
    conv rconv;

    rconv=init();

    while (1)
    {
    if ((input!=1)&&(input!=0))
    {
    pass=input%2;
    input/=2;
    }
    else
    {
    rconv.bits[rconv.pointer]=input+48;
    rconv.pointer++;
    if (input==1)
    rconv.length++;
    break;
    }

    if (pass==1)
    {
    rconv.bits[rconv.pointer]='1';
    rconv.pointer++;
    rconv.length++;
    }
    else
    {
    rconv.bits[rconv.pointer]='0';
    rconv.pointer++;
    }
    }
    Mars, Feb 20, 2005
    #3
  4. 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?

    > how can I make it more efficient????


    Change your algorithm to a more efficient one. Hint: instead of an
    exponential time with the number of bits, it can be done O(M*N) (where M
    is the number of bits set and N is the total number of bits). In fact
    it can be done better than that. Think shifts...

    Chris C
    Chris Croughton, Feb 20, 2005
    #4
  5. Mars

    Michael Mair Guest

    Chris Croughton wrote:
    > On Mon, 21 Feb 2005 01:18:35 +0800, Mars
    > <Mars@Mars> wrote:

    [Request for an improvement of program/algorithm to output all
    numbers representable with N bits where M bits are set]

    >>how can I make it more efficient????

    >
    > Change your algorithm to a more efficient one. Hint: instead of an
    > exponential time with the number of bits, it can be done O(M*N) (where M
    > is the number of bits set and N is the total number of bits). In fact
    > it can be done better than that. Think shifts...


    Hmmm, I cannot follow:
    The number of numbers is
    / N \
    | |
    \ M /
    with a maximum at M = N/2.
    If I use M = 3 and consider N=n and N=2*n, I get first
    n*(n-1)*(n-2)/6
    and then
    4*(2n-1)*n*(n-1)/6 > 8*n*(n-1)*(n-2)/6
    which is by no means linear in N. We have to output
    considerably more than O(M*N) numbers -- how do you plan
    to do that in at most quadratic time?

    -Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
    Michael Mair, Feb 20, 2005
    #5
  6. In article <>,
    Chris Croughton <> wrote:
    :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.

    :Hint: instead of an
    :exponential time with the number of bits, it can be done O(M*N) (where M
    :is the number of bits set and N is the total number of bits). In fact
    :it can be done better than that. Think shifts...

    M bits set out of N is (N choose N), which will be N! / (M! (N-M)!)
    That's a bit bigger than O(M*N). For example, 8 bits 3 set, you
    predict O(8*3), but instead it is O((8*7*6)/(1*2*3)) = O(56):

    00000111 00001011 00001101 00001110 00010011 00010101 00010110 00011001
    00011010 00011100 00100011 00100101 00100110 00101001 00101010 00101100
    00110001 00110010 00110100 00111000 01000011 01000101 01000110 01001001
    01001010 01001100 01010001 01010010 01010100 01011000 01100001 01100010
    01100100 01101000 01110000 10000011 10000101 10000110 10001001 10001010
    10001100 10010001 10010010 10010100 10011000 10100001 10100010 10100100
    10101000 10110000 11000001 11000010 11000100 11001000 11010000 11100000
    --
    Pity the poor electron, floating around minding its own business for
    billions of years; and then suddenly Bam!! -- annihilated just so
    you could read this posting.
    Walter Roberson, Feb 20, 2005
    #6
  7. Mars wrote:
    > I'm writing a program for listing all binary numbers of the same

    length
    > with the same number of 1s.
    >
    > e.g.
    > 0011
    > 0101
    > 0110
    > 1001
    > 1010
    > 1100


    Use bit manipulations. Given a valid number, add the last bit to
    the original, then put enough 1s in the low end to keep the total
    1-bits consistent.

    % 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 **q8){
    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;}

    % gcc -ansi -pedantic nmo.c -o nmo.exe

    % nmo 4 2
    0011
    0101
    0110
    1001
    1010
    1100

    %

    --
    Peter
    Peter Nilsson, Feb 20, 2005
    #7
  8. Peter Nilsson wrote:
    > Mars wrote:
    > > I'm writing a program for listing all binary numbers of the same

    > length
    > > with the same number of 1s.
    > >
    > > e.g.
    > > 0011
    > > 0101
    > > 0110
    > > 1001
    > > 1010
    > > 1100

    >
    > Use bit manipulations. Given a valid number, add the last bit to
    > the original, then put enough 1s in the low end to keep the total
    > 1-bits consistent.


    Alternatively, if you want to deal with strings...

    http://groups-beta.google.com/group/comp.lang.c/msg/98c0260bb56e83f2

    --
    Peter
    Peter Nilsson, Feb 21, 2005
    #8
  9. 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.) 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.
    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

    -Chris
    Chris Williams, Feb 21, 2005
    #9
  10. On Sun, 20 Feb 2005 21:37:18 +0100, Michael Mair
    <> wrote:

    > Chris Croughton wrote:
    >> On Mon, 21 Feb 2005 01:18:35 +0800, Mars
    >> <Mars@Mars> wrote:

    > [Request for an improvement of program/algorithm to output all
    > numbers representable with N bits where M bits are set]
    >
    >>>how can I make it more efficient????

    >>
    >> Change your algorithm to a more efficient one. Hint: instead of an
    >> exponential time with the number of bits, it can be done O(M*N) (where M
    >> is the number of bits set and N is the total number of bits). In fact
    >> it can be done better than that. Think shifts...

    >
    > Hmmm, I cannot follow:
    > The number of numbers is
    > / N \
    > | |
    > \ M /
    > with a maximum at M = N/2.
    > If I use M = 3 and consider N=n and N=2*n, I get first
    > n*(n-1)*(n-2)/6
    > and then
    > 4*(2n-1)*n*(n-1)/6 > 8*n*(n-1)*(n-2)/6
    > which is by no means linear in N. We have to output
    > considerably more than O(M*N) numbers -- how do you plan
    > to do that in at most quadratic time?


    Yes, you're right, it's worse than I was thinking, it's something better
    than O(N^M) (O(N^m) for any given M=m). Which is still better than
    O(2^N), it's permutation not exponential, for N=20 and M=2 it will be
    n(n-1)/2 = 190, for N=40 M=3 it will be n(n-1)(n-2)/6 = 9880 rather than
    1,048,576 and 1,099,511,627,776 respectively.

    (Using ^ as exponentiation operator above, just in case anyone was
    wondering why N xor M would give meaningful result!)

    (My O(M*N) was right for at least one case, M=1 <g>...)

    Chris C
    Chris Croughton, Feb 21, 2005
    #10
  11. Mars

    Flash Gordon Guest

    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.
    Flash Gordon, Feb 21, 2005
    #11
  12. Mars

    Mars Guest

    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, Feb 21, 2005
    #12
  13. Mars

    Mars Guest

    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 **q8){
    > 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.
    Mars, Feb 21, 2005
    #13
  14. Mars

    Mars Guest

    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
    Mars, Feb 21, 2005
    #14
  15. Mars

    Michael Mair Guest

    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 **q8){
    >> 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.
    Michael Mair, Feb 21, 2005
    #15
  16. Mars

    Michael Mair Guest

    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.
    Michael Mair, Feb 21, 2005
    #16
  17. 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
    Chris Williams, Feb 22, 2005
    #17
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. kelvSYC
    Replies:
    2
    Views:
    4,695
    Brad BARCLAY
    Dec 30, 2003
  2. Raja
    Replies:
    2
    Views:
    14,965
  3. lei
    Replies:
    1
    Views:
    582
    John W. Kennedy
    Dec 30, 2006
  4. bob
    Replies:
    6
    Views:
    747
    Peter Shaggy Haywood
    Mar 21, 2006
  5. Ven
    Replies:
    3
    Views:
    1,322
Loading...

Share This Page