Bit functions: Retrieving the rank of a term in a geometric sequence

[Legacy_Kato -]

               Hi,

In the process of completing an include file dedicated to bit functions, I'm not too sure about the right formula for retrieving the rank of a bit. I have seen on the web that the first 2 bits + the highest bit must be retrieved, but the formula is somewhat strangely explained(for a math noob like me I guess) in the docs I have found so far. 

To get the highest bit(or rather bitwise value), I have found:

int GetHighestBit(int nBitArray)
{
   nBitArray |= (nBitArray >> 1);
   nBitArray |= (nBitArray >> 2);
   nBitArray |= (nBitArray >> 4);
   nBitArray |= (nBitArray >> ;
   nBitArray |= (nBitArray >> 16);
   return nBitArray - (nBitArray >> 1);
}

It works well for 32 bit numbers, although it might possibly be simplified. So now, to retrieve the rank of a bit, I'm using this(shortened for the purposes of this post), until I get or correctly assess the right formula:

int GetBitRank(int nBit)
{
     switch(nBit)
     {
        case 32: return 6;
        case 16: return 5;
        case 8: return 4;
        case 4: return 3;
        case 2: return 2;
        case 1: return 1;        
     }
     return 0;
} 

Thanks for any insight '>

Kato
               
               

               

                     Modifié par Kato_Yang, 12 août 2012 - 04:52 .
                     
                  

            

[Legacy_henesua]

               I unfortunately do not have insight on this.

But I was wondering why you would need to return the rank pf the highest bit. I haven't had need of that before.
               
               

               
            

[Legacy_Lightfoot8]

               Unfortunately,  NWScript does not have verry good functions for doing this.   With flay in the >> operator I would not trust it much for this kind of work.   The simplest approach would be to take the base 2 log of the number to return the hiest bit.  There again we have a problem with NWScript since it does not have a log base 2 function.   So I had to do some research and came accross this page:  


Log base 2 - Yes


with this information your function can now look like this;



int GetHighestBitRank(int nNum)
{
           if (nNum==0) return -1;  // Error case no bits set.
           if (nNum <0 )return 31;  // High bit set.
           return FloatToInt(log(nNum*1.0)/log(2.0)); // return for bits 0 - 30
}

...
Note:  Your function above was off it should have read


int GetBitRank(int nBit)
{
     switch(nBit)
     {
        ...
        case 32: return 5;
        case 16: return 4;
        case 8: return 3;
        case 4: return 2;
        case 2: return 1;
        case 1: return 0;        
     }
     return -1;
} 

bits are 0 based in there positions, bits 0-31 for a 32 bit number, not bits 1 -32. so a return of -1 on an error makes the most since.

Hope that helps.
 
Edit: Edited my function for my error on the 31st bit not always being -1
               
               

               

                     Modifié par Lightfoot8, 12 août 2012 - 05:16 .
                     
                  

            

[Legacy_Kato -]

               @Lightfoot8: Thanks a lot for the infos and corrections. The switch in GetBitRank() is not a problem but I'll search for the formula which could replace it(as a math practice).


@Henesua: I'm using bit math in this case for a custom portal stone system, storing/retrieving the available destinations(bitwise values) in/from a single variable.

Kato
               
               

               

                     Modifié par Kato_Yang, 12 août 2012 - 06:05 .
                     
                  

            

[Legacy_Lightfoot8]

               

Kato_Yang wrote...

@Lightfoot8: Thanks a lot for the infos and corrections. The switch in GetBitRank() is not a problem but I'll search for the formula which could replace it(as a math practice).
Kato

Ok, I am confused now. ( Not hard to do, by the way.) you wrote.  

In the process of completing an include file dedicated to bit functions, I'm not too sure about the right formula for retrieving the rank of a bit. I have seen on the web that the first 2 bits + the highest bit must be retrieved, but the formula is somewhat strangely explained(for a math noob like me I guess) in the docs I have found so far... 

... It works well for 32 bit numbers, although it might possibly be simplified. So now, to retrieve the rank of a bit, I'm using this(shortened for the purposes of this post), ...

...Thanks for any insight '>

If I understand you correctly, I guess I did not give enough insight.   

First I have not tested your formula for GetHighestBit(ByValue),  There is only one concern I have on that function, that being if the 31 bit  is set ( any negtive number),  I do not know if it will retrive the correct value., with the way the >> operator is bugged in NWScript.


the concern I have with the  GetBitRank function is the number of comparisons that need to be done.  We are looking at 32 comparisons if only the first bit is set.  This will increase the chance of a "too many instructions" error if this function is ever used in a loop.    

The function I posted will use less VM instructions to do the same thing.  

I would also not be supprised if it could be used to get the get the highest bit value faster. 

example. 

int GetHighestBitByPosition(int nNum)
{
           if (nNum==0) return -1;  // Error case no bits set.
           if (nNum <0 )return 31;  // High bit set.
           return FloatToInt(log(nNum*1.0)/log(2.0)); // return for bits 0 - 30
}


int GetHighestBitByValue(int nNum)
{
   if(!nNum) return 0;
  return 1 << GetHighestBitRankByPosition(int nNum)  
}

Also if you feed the function a number with only a single bit set, it would by default be the highest bit set.  

If that is not what you are asking, I am still confused
               
               

               
            

[Legacy_Kato -]

               Yes, this is helpful indeed. Actually the initial function GetHighestBit() was used to return the value instead of the position(i.e. passing 7 returns 4), but the function you posted can do it too if I raise 2 to the power of the rank returned by it(or if using the function GetHighestBitByValue() in the example you posted), and since yours is optimized I'll of course use it instead.

I had not fully assessed the problems coming from replacing the switch by a formula in GetBitRank(), so I'll stick to the switch, thanks for the corrections on this one too. Just as an info, the formula I have seen is: an = a1 * pow(r, n-1), used for geometric sequences.

Thank you once more, L8


Kato
               
               

               

                     Modifié par Kato_Yang, 13 août 2012 - 03:06 .