[SOLVED!] Most Significant Bit function, someone?

[EganSolo]

I'm about to write a small little function that when given a cardinal returns the position of the most significant bit of a cardinal, 32 being the position of the leftmost bit and 1 that of the rightmost bit. Credit of this solution in C/Java is due to Michael McGowan and can be found here https://stackoverflow.com/questions/9117793/bitwise-most-significant-set-bit. I merely wrote it in object pascal.

Code: Pascal  [Select][+][-]

1. function msbPos(const c: Cardinal) : byte;
2. var i       : integer;
3.      Mask : Cardinal;
4. begin
5.  Result := 0;         // no dice.
6.  If c = 0 then exit; // don't waste time
7.  Mask := 1 << 31; // Start with the number 1 followed by 31 0s.
8.  For i := 31 downto 1 do
9.    If (c and Mask) > 0
10.    then begin
11.       Result := i;
12.       exit;
13.   end
14.   else Mask := Mask >> 1;
15. end;
16.  

Being paranoid, I'm wondering if there's an asm version of this lurking somewhere in the bowels of the Lazarus package? I've searched the web and pocked around the Math unit, checked the free pascal user manual and came up with nothing.

If you'd like to try it, you can run the following little test program:

Code: Pascal  [Select][+][-]

1. Program Project1;
2.  
3. function msbPos(const c: Cardinal) : byte;
4. var i       : integer;
5.      Mask : Cardinal;
6. begin
7.  Result := 0;         // no dice.
8.  If c = 0 then exit; // don't waste time
9.  Mask := 1 << 31; // Start with the number 1 followed by 31 0s.
10.  For i := 31 downto 1 do
11.    If (c and Mask) > 0
12.    then begin
13.       Result := i;
14.       exit;
15.   end
16.   else Mask := Mask >> 1; //move to next rightmost location and repeat.
17. end;
18.  
19.       //  3         2         1
20. const // 10987654321098765432109876543210
21.    c1 = %10000000000000000000000000000000; //msbpos = 31
22.    c2 = %00000100000000000000000000000000; //msbpos = 26
23.    c3 = %00000000000010000000000000000000; //mspos  = 19
24.    c4 = %00000000000000000000001000000000; //mspos  = 09
25.    c5 = %00000000000000000000000000000100; //mspos  = 02
26.    c6 = %00000000000000000000000000000001; //mspos  = 00
27.  
28. var aPos : byte;
29. Begin
30.    aPos := msbPos(c1);
31.    Writeln('Most significant position of c1 is ' , aPos);
32.    aPos := msbPos(c2);
33.    Writeln('Most significant position of c2 is ' , aPos);
34.    aPos := msbPos(c3);
35.    Writeln('Most significant position of c3 is ' , aPos);
36.    aPos := msbPos(c4);
37.    Writeln('Most significant position of c4 is ' , aPos);
38.    aPos := msbPos(c5);
39.    Writeln('Most significant position of c5 is ' , aPos);
40.    aPos := msbPos(c6);
41.    Writeln('Most significant position of c6 is ' , aPos);
42.    Readln();
43. End.
44.  

[ASerge]

I'm about to write a small little function that when given a cardinal returns the position of the most significant bit of a cardinal, 32 being the position of the leftmost bit and 1 that of the rightmost bit.

System.BsfDWord.

[Thaddy]

I'm about to write a small little function that when given a cardinal returns the position of the most significant bit of a cardinal, 32 being the position of the leftmost bit and 1 that of the rightmost bit.

System.BsfDWord.

In trunk we have added bitindex functions (after a long discussion) So you can test/set and clear any bit on any integer type, signed or not.
They are helpers in sysutils. We have itestbit(index), setbit(index), togglebit(index) and clearbit(index);

Code: Pascal  [Select][+][-]

1. {$mode objfpc}{$H+}{$R-}
2. uses sysutils;
3. var a:dword = 0;
4. begin
5.   writeln(a.ToBinString); // shows the bitpattern
6.   writeln(a.testbit(31)); // msb = 0
7.   a.togglebit(31);
8.   writeln(a.testbit(31)); // msb = 1
9.   writeln(a.ToBinString);
10. end.

 
Note you currently need {$R-} state to avoid rogue range errors. I am still working on a solution for that. (It was my idea so I feel responsible)

[EganSolo]

@Aserge and @Thaddy: You guys rock!
Thanks!

[Thaddy]

I have also helper functions for relative highest and lowest bit set, but did not submit those yet.

You might be interested in this:
https://graphics.stanford.edu/~seander/bithacks.html

[EganSolo]

@Thaddy: I'm using Free Pascal 3.0.4 and when I tried to run your sample project, I got five "Illegal qualifier" errors. The compiler did not recognize any of the a.xxx function calls.

Is there a switch that I need to toggle ? What am I missing?
 

[Thaddy]

@Thaddy: I'm using Free Pascal 3.0.4 and when I tried to run your sample project, I got five "Illegal qualifier" errors. The compiler did not recognize any of the a.xxx function calls.

Is there a switch that I need to toggle ? What am I missing?

I explicitly wrote this is only in fpc trunk, not in 3.0.4.
These are features I designed about 6 months ago. (Actually more than a year, but Michael committed them 6 months ago and Bart helped a lot with testing)

[EganSolo]

@Thaddy: You're right, my bad. Thanks for clarifying.

[Thaddy]

Note I have a separate unit that achieves the same and works with 3.0.4. Just ask if you need it. (I believe I already posted it somewhere, though)
Note that that unit is not exactly like the implementation  in trunk: Bart pointed out several issues so we changed a lot. It is still not "perfect".

[EganSolo]

No issues. I'll wait. For right now I've been able to take care of my needs with an and and a <<. So thanks!

[jamie]

testing for the MSB is very simple...

Just type cast with the appropriate integer...

I don't know what the type is that is being tested but I can assume for now it to be a integer which is a 32 bit..

 If Integer(My32BitSomething) < 0 Then …

or what ever type that fits the bill..

 shortInt, SmallInt, Integer, Int64 etc..

and if that is not abstract you can do the logic stuff...

 If (SomewhatEver and $80000000)<> 0 Then …

etc

 doing bit testing is simply if you know which bit position you need...

 I prefer doing this over using some provided helper that bloats things.

[guest58172]

I'm about to write a small little function that when given a cardinal returns the position of the most significant bit of a cardinal, 32 being the position of the leftmost bit and 1 that of the rightmost bit. Credit of this solution in C/Java is due to Michael McGowan and can be found here https://stackoverflow.com/questions/9117793/bitwise-most-significant-set-bit. I merely wrote it in object pascal.

Code: Pascal  [Select][+][-]

1. function msbPos(const c: Cardinal) : byte;
2. var i       : integer;
3.      Mask : Cardinal;
4. begin
5.  Result := 0;         // no dice.
6.  If c = 0 then exit; // don't waste time
7.  Mask := 1 << 31; // Start with the number 1 followed by 31 0s.
8.  For i := 31 downto 1 do
9.    If (c and Mask) > 0
10.    then begin
11.       Result := i;
12.       exit;
13.   end
14.   else Mask := Mask >> 1;
15. end;
16.  

Being paranoid, I'm wondering if there's an asm version of this lurking somewhere in the bowels of the Lazarus package? I've searched the web and pocked around the Math unit, checked the free pascal user manual and came up with nothing.

If you'd like to try it, you can run the following little test program:

Code: Pascal  [Select][+][-]

1. Program Project1;
2.  
3. function msbPos(const c: Cardinal) : byte;
4. var i       : integer;
5.      Mask : Cardinal;
6. begin
7.  Result := 0;         // no dice.
8.  If c = 0 then exit; // don't waste time
9.  Mask := 1 << 31; // Start with the number 1 followed by 31 0s.
10.  For i := 31 downto 1 do
11.    If (c and Mask) > 0
12.    then begin
13.       Result := i;
14.       exit;
15.   end
16.   else Mask := Mask >> 1; //move to next rightmost location and repeat.
17. end;
18.  
19.       //  3         2         1
20. const // 10987654321098765432109876543210
21.    c1 = %10000000000000000000000000000000; //msbpos = 31
22.    c2 = %00000100000000000000000000000000; //msbpos = 26
23.    c3 = %00000000000010000000000000000000; //mspos  = 19
24.    c4 = %00000000000000000000001000000000; //mspos  = 09
25.    c5 = %00000000000000000000000000000100; //mspos  = 02
26.    c6 = %00000000000000000000000000000001; //mspos  = 00
27.  
28. var aPos : byte;
29. Begin
30.    aPos := msbPos(c1);
31.    Writeln('Most significant position of c1 is ' , aPos);
32.    aPos := msbPos(c2);
33.    Writeln('Most significant position of c2 is ' , aPos);
34.    aPos := msbPos(c3);
35.    Writeln('Most significant position of c3 is ' , aPos);
36.    aPos := msbPos(c4);
37.    Writeln('Most significant position of c4 is ' , aPos);
38.    aPos := msbPos(c5);
39.    Writeln('Most significant position of c5 is ' , aPos);
40.    aPos := msbPos(c6);
41.    Writeln('Most significant position of c6 is ' , aPos);
42.    Readln();
43. End.
44.  

This is stupid to translate this from JAVA.  FPC is system programming so use BSR or LZCNT in assembly and you're good.

[Thaddy]

This is stupid to translate this from JAVA.  FPC is system programming so use BSR or LZCNT in assembly and you're good.

No need for any assembler. The tricks from Stanford are all you need to know:
https://graphics.stanford.edu/~seander/bithacks.html

FreePascal generates near optimal code on most processors.

[guest58172]

BTW does JAVA have a system of intrinsics for BSR,LZCNT ? (never danced JAVA  ). I suppose it has instrinsics for other funcs because otherwise things like trigo op would be soft emulated which would be crazy...

So assuming there could be intrinsics for fast bitop, why in the original SO link they dont use a intrinsic for leading zero counting ?

Just casual conversation, now that the problem is solved

[guest58172]

Mmmh after reading carefully it looks like this was suggested : https://stackoverflow.com/a/9117869, but the guy wanted to do it with basic bitops to learn. That's understandable. In the Pascal world i'm sure that many people don't have a clue of what are the bitops behind "set of", "include" and "exclude".