Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > comparing msb

Reply
Thread Tools

comparing msb

 
 
John
Guest
Posts: n/a
 
      04-13-2005

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

 
Reply With Quote
 
 
 
 
Lew Pitcher
Guest
Posts: n/a
 
      04-13-2005
-----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)

iD8DBQFCXVVyagVFX4UWr64RAtEwAKDznc5u6qns4WvqdSxLr7 grI0l/5wCfVu2a
pPSZDi/y43XOmNO9kxdrdNc=
=00Iy
-----END PGP SIGNATURE-----

 
Reply With Quote
 
 
 
 
Ben Pfaff
Guest
Posts: n/a
 
      04-13-2005
"John" <(E-Mail Removed)> 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

 
Reply With Quote
 
Thomas Matthews
Guest
Posts: n/a
 
      04-13-2005
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

 
Reply With Quote
 
Alex Fraser
Guest
Posts: n/a
 
      04-14-2005
"Ben Pfaff" <(E-Mail Removed)> wrote in message
news:(E-Mail Removed)...
> "John" <(E-Mail Removed)> 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


 
Reply With Quote
 
pete
Guest
Posts: n/a
 
      04-14-2005
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

 
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
Parsing long with MSB set using Long.parseLong() sameergn@gmail.com Java 0 06-07-2005 06:49 AM
determining of the position of the MSB =?ISO-8859-1?Q?Johan_Bernsp=E5ng?= VHDL 20 08-02-2004 05:56 PM
convert a double keeping msb ? DanSteph C++ 12 06-26-2004 05:00 PM
GMP and finding MSB of type mpz_t Ernst Berg C Programming 6 12-12-2003 09:33 AM
How to get the MSB? Andi Hotz C++ 3 11-21-2003 07:30 PM



Advertisments