comparing msb

Discussion in 'C Programming' started by John, Apr 13, 2005.

  1. John

    John Guest

    I have two numbers a,b.

    I would like to compare if most significant bit of a is
    larger than most significant bit of b. Right now the code
    I am using looks like this

    int w1,w2;
    asm("bsr %0,%1" : "=r" (w1) : "r" (a));
    asm("bsr %0,%1" : "=r" (w2) : "r" (b));
    return w1 < w2;

    Anyone has any better ideas on how to do this. Seems
    like this code is pretty slow. Is there an easier way
    to compare the msb of two numbers? Maybe using one
    assembly command? Or maybe by doing something else
    compared to bsr?

    Thanks,
    --j
    John, Apr 13, 2005
    #1
    1. Advertising

  2. John

    Lew Pitcher Guest

    -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    In comp.lang.c, John wrote:
    > I have two numbers a,b.
    >
    > I would like to compare if most significant bit of a is
    > larger than most significant bit of b. Right now the code
    > I am using looks like this
    >
    > int w1,w2;
    > asm("bsr %0,%1" : "=r" (w1) : "r" (a));


    Oops. This doesn't compile because of a syntax error.
    Plus, there's no standard C function called asm()

    > asm("bsr %0,%1" : "=r" (w2) : "r" (b));


    See above

    > return w1 < w2;
    >
    > Anyone has any better ideas on how to do this.


    With a bit better definition of your requirements, yes.

    [snip]


    - --
    Lew Pitcher
    IT Specialist, Enterprise Data Systems,
    Enterprise Technology Solutions, TD Bank Financial Group

    (Opinions expressed are my own, not my employers')
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.2.4 (MingW32)

    iD8DBQFCXVVyagVFX4UWr64RAtEwAKDznc5u6qns4WvqdSxLr7grI0l/5wCfVu2a
    pPSZDi/y43XOmNO9kxdrdNc=
    =00Iy
    -----END PGP SIGNATURE-----
    Lew Pitcher, Apr 13, 2005
    #2
    1. Advertising

  3. John

    Ben Pfaff Guest

    "John" <> writes:

    > I have two numbers a,b.
    >
    > I would like to compare if most significant bit of a is
    > larger than most significant bit of b.


    If a and b are unsigned, then a > b is pretty close. If I am
    thinking correctly, it can only be wrong if a and b have the same
    MSB. Does that help?

    If a and b are signed, then I'm not sure what qualifies as the
    MSB.
    --
    "The lusers I know are so clueless, that if they were dipped in clue
    musk and dropped in the middle of pack of horny clues, on clue prom
    night during clue happy hour, they still couldn't get a clue."
    --Michael Girdwood, in the monastery
    Ben Pfaff, Apr 13, 2005
    #3
  4. John wrote:

    > I have two numbers a,b.
    >
    > I would like to compare if most significant bit of a is
    > larger than most significant bit of b. Right now the code
    > I am using looks like this
    >
    > int w1,w2;
    > asm("bsr %0,%1" : "=r" (w1) : "r" (a));
    > asm("bsr %0,%1" : "=r" (w2) : "r" (b));
    > return w1 < w2;
    >
    > Anyone has any better ideas on how to do this. Seems
    > like this code is pretty slow. Is there an easier way
    > to compare the msb of two numbers? Maybe using one
    > assembly command? Or maybe by doing something else
    > compared to bsr?
    >
    > Thanks,
    > --j
    >


    The safest method is to extract the most significant
    bits and compare them. This becomes a bit tricky
    with different bit-widths of variables and also
    for Endianism.

    In a header file, <limits.h>, is a symbol CHAR_BIT,
    which defines the number of bits in the type char.
    The "sizeof" operator will return the number of
    units (of type char) of a type or structure.
    Knowing this, the number of bits in an integer
    can be found.

    Let's define the most significant bit (MSB) as:
    msb = 1 << ((sizeof(int) * CHAR_BIT) - 1)
    which is a 1 left shifted to one less than the
    number of bits in an integer.

    The MSB can be isolated using this information
    and the bitwise AND operator.

    However, setting up the relationship in a truth
    table yields:
    ---------+----------+-------
    MSB of A | MSB of B | A > B
    ---------+----------+-------
    0 | 0 | False (0)
    ---------+----------+-------
    0 | 1 | False (0)
    ---------+----------+-------
    1 | 0 | True (1)
    ---------+----------+-------
    1 | 1 | False (0)
    ---------+----------+-------

    result = msb_a AND NOT msb_b.

    The implementation of this is left as an exercise
    for the O.P.

    --
    Thomas Matthews

    C++ newsgroup welcome message:
    http://www.slack.net/~shiva/welcome.txt
    C++ Faq: http://www.parashift.com/c -faq-lite
    C Faq: http://www.eskimo.com/~scs/c-faq/top.html
    alt.comp.lang.learn.c-c++ faq:
    http://www.comeaucomputing.com/learn/faq/
    Other sites:
    http://www.josuttis.com -- C++ STL Library book
    http://www.sgi.com/tech/stl -- Standard Template Library
    Thomas Matthews, Apr 14, 2005
    #4
  5. John

    Alex Fraser Guest

    "Ben Pfaff" <> wrote in message
    news:...
    > "John" <> writes:
    > > I have two numbers a,b.
    > >
    > > I would like to compare if most significant bit of a is
    > > larger than most significant bit of b.

    >
    > If a and b are unsigned, then a > b is pretty close. If I am
    > thinking correctly, it can only be wrong if a and b have the same
    > MSB.


    I think you're thinking correctly. I also think the exclusive-or operator
    can help you figure out the case where a and b have the same MSB.

    Alex
    Alex Fraser, Apr 14, 2005
    #5
  6. John

    pete Guest

    Thomas Matthews wrote:
    >
    > John wrote:
    >
    > > I have two numbers a,b.
    > >
    > > I would like to compare if most significant bit of a is
    > > larger than most significant bit of b. Right now the code
    > > I am using looks like this
    > >
    > > int w1,w2;
    > > asm("bsr %0,%1" : "=r" (w1) : "r" (a));
    > > asm("bsr %0,%1" : "=r" (w2) : "r" (b));
    > > return w1 < w2;
    > >
    > > Anyone has any better ideas on how to do this. Seems
    > > like this code is pretty slow. Is there an easier way
    > > to compare the msb of two numbers? Maybe using one
    > > assembly command? Or maybe by doing something else
    > > compared to bsr?
    > >
    > > Thanks,
    > > --j
    > >

    >
    > The safest method is to extract the most significant
    > bits and compare them. This becomes a bit tricky
    > with different bit-widths of variables and also
    > for Endianism.
    >
    > In a header file, <limits.h>, is a symbol CHAR_BIT,
    > which defines the number of bits in the type char.
    > The "sizeof" operator will return the number of
    > units (of type char) of a type or structure.
    > Knowing this, the number of bits in an integer
    > can be found.
    >
    > Let's define the most significant bit (MSB) as:
    > msb = 1 << ((sizeof(int) * CHAR_BIT) - 1)
    > which is a 1 left shifted to one less than the
    > number of bits in an integer.
    >
    > The MSB can be isolated using this information
    > and the bitwise AND operator.


    Wrong.
    1 << ((sizeof(int) * CHAR_BIT) - 1)
    is implementation defined if int has no padding.

    If int has any padding then it's especially wrong.

    A portable expression for an unsigned number
    with only the most significant bit set is:
    unsigned mask = ((unsigned)-1 >> 1) + 1;

    --
    pete
    pete, Apr 14, 2005
    #6
    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. =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=

    determining of the position of the MSB

    =?ISO-8859-1?Q?Johan_Bernsp=E5ng?=, Jul 27, 2004, in forum: VHDL
    Replies:
    20
    Views:
    3,003
    Jonathan Bromley
    Aug 2, 2004
  2. Replies:
    0
    Views:
    646
  3. Andi Hotz

    How to get the MSB?

    Andi Hotz, Nov 21, 2003, in forum: C++
    Replies:
    3
    Views:
    344
    Mike Wahler
    Nov 21, 2003
  4. DanSteph

    convert a double keeping msb ?

    DanSteph, Jun 24, 2004, in forum: C++
    Replies:
    12
    Views:
    1,945
    marbac
    Jun 26, 2004
  5. Ernst Berg

    GMP and finding MSB of type mpz_t

    Ernst Berg, Dec 6, 2003, in forum: C Programming
    Replies:
    6
    Views:
    521
    Ernst Berg
    Dec 12, 2003
Loading...

Share This Page