How to find the most significative bit 2

[hyperbug]

I want to get this bit whithout a loop and testing each bit. I read that there is a formula to find it like
(number - 1) % y
or something like that.

 

[icrf]

If the number is signed, it's easy. Test if it's less than zero. If it's unsigned, you can test if it's less than it's bitwise left shift. Examples:
1101 << 1 = 1010 (13 < 10)
1010 << 1 = 0100 (10 < 4)
0100 << 1 = 1000 (4 !< 8)
One combined logical OR should suffice:

if((a < (a << 1)) || (a < 0))
    cout << &quot;High order bit is 1&quot; << endl;
else
    cout << &quot;High order bit is 0&quot; << endl;

I think this works in all cases. ----------------------------------------------------------------------------------
...but I'm just a C man trying to see the light

 

[lionelhill]

To be honest, I'd stick to the loop and test. I have a vague suspicion there might actually be an op-code to make the processor do this (locate the first set bit) - I used to enjoy perusing op-code lists over breakfast. But I also have a vague suspicion I took one look at it and turned over on the grounds that it was hideously slow.

Of course if you only need to handle a smallish range of numbers (like find the first set bit of a byte), you could make yourself a look-up table (an array of answers for the numbers 0 to 255), which would cut the loop and all the work. But this would only be appropriate for very special circumstances (small range of numbers to handle, need for lots of speed).

You could adapt the look-up for larger numbers and cut, but not eliminate, the amount of looping by doing the following (for a word. Scale up for dwords).

(1) Is high byte zero? If yes, go to (4)
(2) look up value for high-byte in our byte-lookup-table.
(3) Add 8 (for the number of bits in the low byte) and RETURN this value.

(4) Look up value for low-byte in our byte-lookup table, and RETURN this.

This approach needs one loop per byte rather than one loop per bit.

 

[Cagliostro]

My advice is

yourbit = ((signed)yournumber) < 0 ? 1 : 0;

or
yourbit =
((unsigned)yournumber) >> (sizeof(yournumber) * 8 - 1); Ion Filipski

filipski@excite.com

 

[lionelhill]

Dear hyperbug,

I misunderstood your question I think. From the title of the thread it looks like you want to find the state of the most significant bit, in which case of course looping is not necessary, and ionFilipski's method looks good, as is simply testing if the number is negative.

But I answered after reading your first post, which suggested you want to find the position of the first set bit.

Which did you mean??

(Anyway, doesn't matter, you've got answers for both!)

 

[hyperbug]

I have a 128 bit unsigned integer and I want to find the first bit set to one without a loop. Thank you

 

[Zyrenthian]

I assume you are using some sort of class/struct to allow you to have 128 bits? The highest I knew MSVC could go up to was 64 bit. Anyway, you should have some way of accessing the high 8 bits. Get the high 8 bits and if it is greater then 127, the high bit is 1, else it is zero. Also, going with the above post, you could get the high 32 bits as signed and if it is negative, the high bit is 1. This is also possible with the 8 bits but you must get it as a signed char, if that is negative, then it is 1.

Matt

 

[lionelhill]

Assuming you want to find the position of the first bit set to 1 in a 128 bit number, you cannot do it in a single step. OK, you may find someone's got a library function to do it (in which case go ahead and use their library function) but there's more than one step in it somewhere.

I still think a quick approach would be to access each byte of your 128 bits in turn (so 16 bytes in total. Sorry, you'll either have to write the same code 16 times or accept a 16-cycle loop), and do a look-up for each byte in a 256 byte table. You can potentially improve things by checking dwords first to see if they are zero, in which case you can cut out 4 goes round the loop...

The positive/negative thing will tell you the state of the first bit in your number. It will do so irrespective of the total length of the number (in fact it doesn't even need to know how long the number is!). Positive/negative tests will give you access to the high bit of any byte along your number, if you want, but won't tell you anything about the remaining 7 bits.

But frankly unless your application is very speed-critical, I'd be inclined to accept the loop: check if negative/positive, and multiply by 2 (actually, shift left) until negative with max of 128 goes.

 

[mingis]

the formula is log2(x) or
log(x)/log(2)

 

[palbano]

there we go!!! thanks mingis! -There are only 10 types of people in the world, those who understand binary and those who don't-

-pete

 

[icrf]

Let the idiots fluster long enough, eventually the wise men come down and grace us with their presence. Have another star. ----------------------------------------------------------------------------------
...but I'm just a C man trying to see the light

 

[mingis]

But the loop is thousand times faster

 

[lionelhill]

Well done Mingis, for pointing out both the log and the thousand-times faster.

And I am not drastically happy at being called an idiot, icrf.

In any case, the original question was to do it without a loop, and using a log merely moves the loop somewhere where you can't see it: calculating a log is almost certainly going to be done by a looping approximation method, and the loop for calculating a log will have a whole lot more calculation in it than a simple bit-search.

It's good to know there are people like Mingis who both know something and have a little courtesy. Pity there are others who can't be bothered.

 

[icrf]

My apologies, no offense was intended, just jest. I was thinking and working along, too, and was included in that group.

The question asked for finding it without a loop and preferably with a simple formula, meaning it was one more of math and computer architecture than programming (the route everyone else took). Efficiency was never mentioned, it appeared academic from the start.

Again, I don't really think you guys are idiots. Mood and intent is so hard to read or portray in pain text. ----------------------------------------------------------------------------------
...but I'm just a C man trying to see the light

 

[palbano]

ok so im anal but i had to try this. i am dubious of my performance counter method, but it shows it to be about 33% faster than a sequential loop.


#define SETBIT( bit) ( ( 0x00000001 << bit ) )
#define BITON( bit, v) ( SETBIT( bit) & v )
// return true if the bit is the most significant in lval
#define MSB( bit, lval) ( BITON( bit, lval) && SETBIT( bit + 1) > lval )

// most significant bit one based
int msb( unsigned long lval){

if( !lval) return 0;
if( lval & 0x80000000) return 32;

int upper = 31, lower = 0, pos = 16, msb = 0;

while( !msb){
// check this bit
if( MSB(pos, lval) ) msb = pos + 1;
// check left and right
else if( MSB((pos + 1), lval) ) msb = pos + 2;
else if( MSB( (pos -1), lval) ) msb = pos;

else if( SETBIT(pos) < lval){ // position is less than the most significant bit
lower = pos;
pos += ((upper - lower) / 2);
}else{ // position is greater than the most significant bit
upper = pos;
pos -= ((upper - lower) / 2);
}
}

return msb;
}
-There are only 10 types of people in the world, those who understand binary and those who don't-

-pete

 

[lionelhill]

Sorry icrf, I was just feeling a bit raw yesterday. Nice thread, though; I'm learning lots.
Now I'll go an penitentially have a go at digging out some old code-timing stuff and see if I can understand palbano's cunning posting. Thanks all.

 

[palbano]

lionhill,

>> cunning posting

i don't think i would call it cunning. more than likely its garbage. i just had to try it.

it is just a binary search for the most significant bit rather than a sequential search. it reduces the number of times the loop will run. however there is a lot more going on inside the loop which is why i question my findings. -There are only 10 types of people in the world, those who understand binary and those who don't-

-pete

 

[beetee]

int GetMsb(unsigned Value)
{
int MsbPos = 1;

while (Value)
{
++MsbPos;
Value >>= 1;
}
return MsbPos - 1;
}

 

[beetee]

another version for larger items. (assuming an 8 bit char)

int GetMsb(unsigned Value)
{
int MsbPos = 1;

while (Value)
{
++MsbPos;
Value >>= 1;
}
return MsbPos - 1;
}

int AnotherGetMsb(unsigned char *MyValue, int ValueSize)
{
MyValue = &MyValue[ValueSize - 1];
while (ValueSize)
{
--ValueSize;
int RetVal = GetMsb(*MyValue);
if (RetVal)
return RetVal + (ValueSize * 8);
--MyValue;
}
return 0;
}