comparing msb

[John]

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

 

[Lew Pitcher]

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

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

 

[Ben Pfaff]

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.

 

[Thomas Matthews]

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

 

[Alex Fraser]

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

 

[pete]

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;