[SOLVED!] Most Significant Bit function, someone? lazarus / 62-General ---------------------------------------------------------------------- EganSolo · 2020-02-22 06:33 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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function msbPos(const c: Cardinal) : byte;var i       : integer;     Mask : Cardinal;begin Result := 0;         // no dice. If c = 0 then exit; // don't waste time Mask := 1 << 31; // Start with the number 1 followed by 31 0s. For i := 31 downto 1 do   If (c and Mask) > 0   then begin    Result := i;      exit;  end  else Mask := Mask >> 1;end;  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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Program Project1; function msbPos(const c: Cardinal) : byte;var i       : integer;     Mask : Cardinal;begin Result := 0;         // no dice. If c = 0 then exit; // don't waste time Mask := 1 << 31; // Start with the number 1 followed by 31 0s. For i := 31 downto 1 do   If (c and Mask) > 0   then begin      Result := i;      exit;  end  else Mask := Mask >> 1; //move to next rightmost location and repeat.end;       //  3         2         1const // 10987654321098765432109876543210   c1 = %10000000000000000000000000000000; //msbpos = 31   c2 = %00000100000000000000000000000000; //msbpos = 26   c3 = %00000000000010000000000000000000; //mspos  = 19   c4 = %00000000000000000000001000000000; //mspos  = 09   c5 = %00000000000000000000000000000100; //mspos  = 02   c6 = %00000000000000000000000000000001; //mspos  = 00 var aPos : byte;Begin   aPos := msbPos(c1);   Writeln('Most significant position of c1 is ' , aPos);   aPos := msbPos(c2);   Writeln('Most significant position of c2 is ' , aPos);   aPos := msbPos(c3);   Writeln('Most significant position of c3 is ' , aPos);   aPos := msbPos(c4);   Writeln('Most significant position of c4 is ' , aPos);   aPos := msbPos(c5);   Writeln('Most significant position of c5 is ' , aPos);   aPos := msbPos(c6);   Writeln('Most significant position of c6 is ' , aPos);   Readln();End. ---------------------------------------------------------------------- ASerge · 2020-02-22 07:09 Quote from: EganSolo on February 22, 2020, 07:33:55 amI'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 · 2020-02-22 07:34 Quote from: ASerge on February 22, 2020, 08:09:31 amQuote from: EganSolo on February 22, 2020, 07:33:55 amI'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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i {$mode objfpc}{$H+}{$R-}uses sysutils;var a:dword = 0;begin  writeln(a.ToBinString); // shows the bitpattern  writeln(a.testbit(31)); // msb = 0  a.togglebit(31);  writeln(a.testbit(31)); // msb = 1  writeln(a.ToBinString);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 · 2020-02-22 07:37 @Aserge and @Thaddy: You guys rock! Thanks! ---------------------------------------------------------------------- Thaddy · 2020-02-22 07:44 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 · 2020-02-22 07:58 @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 · 2020-02-22 07:59 Quote from: EganSolo 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? 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 · 2020-02-22 08:23 @Thaddy: You're right, my bad. Thanks for clarifying. ---------------------------------------------------------------------- Thaddy · 2020-02-22 08:57 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 · 2020-02-22 09:37 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 · 2020-02-22 15:53 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 · 2020-03-02 05:33 Quote from: EganSolo on February 22, 2020, 07:33:55 amI'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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function msbPos(const c: Cardinal) : byte;var i       : integer;     Mask : Cardinal;begin Result := 0;         // no dice. If c = 0 then exit; // don't waste time Mask := 1 << 31; // Start with the number 1 followed by 31 0s. For i := 31 downto 1 do   If (c and Mask) > 0   then begin    Result := i;      exit;  end  else Mask := Mask >> 1;end;  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][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Program Project1; function msbPos(const c: Cardinal) : byte;var i       : integer;     Mask : Cardinal;begin Result := 0;         // no dice. If c = 0 then exit; // don't waste time Mask := 1 << 31; // Start with the number 1 followed by 31 0s. For i := 31 downto 1 do   If (c and Mask) > 0   then begin      Result := i;      exit;  end  else Mask := Mask >> 1; //move to next rightmost location and repeat.end;       //  3         2         1const // 10987654321098765432109876543210   c1 = %10000000000000000000000000000000; //msbpos = 31   c2 = %00000100000000000000000000000000; //msbpos = 26   c3 = %00000000000010000000000000000000; //mspos  = 19   c4 = %00000000000000000000001000000000; //mspos  = 09   c5 = %00000000000000000000000000000100; //mspos  = 02   c6 = %00000000000000000000000000000001; //mspos  = 00 var aPos : byte;Begin   aPos := msbPos(c1);   Writeln('Most significant position of c1 is ' , aPos);   aPos := msbPos(c2);   Writeln('Most significant position of c2 is ' , aPos);   aPos := msbPos(c3);   Writeln('Most significant position of c3 is ' , aPos);   aPos := msbPos(c4);   Writeln('Most significant position of c4 is ' , aPos);   aPos := msbPos(c5);   Writeln('Most significant position of c5 is ' , aPos);   aPos := msbPos(c6);   Writeln('Most significant position of c6 is ' , aPos);   Readln();End.  This is stupid to translate this from JAVA.  FPC is system programming so use BSR or LZCNT in assembly and you're good. ---------------------------------------------------------------------- Thaddy · 2020-03-02 07:55 Quote from: Basile-B on March 02, 2020, 06:33:08 amThis 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 · 2020-03-02 09:07 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 · 2020-03-02 09:11 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". ---------------------------------------------------------------------- Thaddy · 2020-03-02 09:26 Quote from: Basile-B on March 02, 2020, 10:11:39 am 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". That is true. Set operations in Pascal are a under-estimated feature of the language. WAY under-estimated.