Recent

Author Topic: [SOLVED!] Most Significant Bit function, someone?  (Read 1075 times)

EganSolo

  • Full Member
  • ***
  • Posts: 158
[SOLVED!] Most Significant Bit function, someone?
« on: February 22, 2020, 07:33:55 am »
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.  

« Last Edit: February 22, 2020, 08:37:34 am by EganSolo »

ASerge

  • Hero Member
  • *****
  • Posts: 1665
Re: Most Significant Bit function, someone?
« Reply #1 on: February 22, 2020, 08:09:31 am »
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

  • Hero Member
  • *****
  • Posts: 10439
Re: Most Significant Bit function, someone?
« Reply #2 on: February 22, 2020, 08:34:47 am »
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)
« Last Edit: February 22, 2020, 08:42:23 am by Thaddy »
When you ask a question that is actually answered in the documentation, you are either lazy or a moron.

EganSolo

  • Full Member
  • ***
  • Posts: 158
Re: Most Significant Bit function, someone?
« Reply #3 on: February 22, 2020, 08:37:05 am »
@Aserge and @Thaddy: You guys rock!
Thanks!

Thaddy

  • Hero Member
  • *****
  • Posts: 10439
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #4 on: February 22, 2020, 08:44:53 am »
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
« Last Edit: February 22, 2020, 09:00:11 am by Thaddy »
When you ask a question that is actually answered in the documentation, you are either lazy or a moron.

EganSolo

  • Full Member
  • ***
  • Posts: 158
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #5 on: February 22, 2020, 08:58:13 am »
@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

  • Hero Member
  • *****
  • Posts: 10439
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #6 on: February 22, 2020, 08:59:40 am »
@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)
« Last Edit: February 22, 2020, 09:02:31 am by Thaddy »
When you ask a question that is actually answered in the documentation, you are either lazy or a moron.

EganSolo

  • Full Member
  • ***
  • Posts: 158
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #7 on: February 22, 2020, 09:23:08 am »
@Thaddy: You're right, my bad. Thanks for clarifying.

Thaddy

  • Hero Member
  • *****
  • Posts: 10439
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #8 on: February 22, 2020, 09:57:19 am »
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".
« Last Edit: February 22, 2020, 10:00:59 am by Thaddy »
When you ask a question that is actually answered in the documentation, you are either lazy or a moron.

EganSolo

  • Full Member
  • ***
  • Posts: 158
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #9 on: February 22, 2020, 10:37:34 am »
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

  • Hero Member
  • *****
  • Posts: 3507
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #10 on: February 22, 2020, 04:53:09 pm »
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.
The only true wisdom is knowing you know nothing

guest58172

  • Guest
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #11 on: March 02, 2020, 06:33:08 am »
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

  • Hero Member
  • *****
  • Posts: 10439
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #12 on: March 02, 2020, 08:55:00 am »
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.
When you ask a question that is actually answered in the documentation, you are either lazy or a moron.

guest58172

  • Guest
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #13 on: March 02, 2020, 10:07:43 am »
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

  • Guest
Re: [SOLVED!] Most Significant Bit function, someone?
« Reply #14 on: March 02, 2020, 10:11:39 am »
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".

 

TinyPortal © 2005-2018