<div dir="ltr"><div>Duh again!</div><div><br></div><div>MA<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Feb 1, 2021 at 7:47 PM Pascal Bourguignon <<a href="mailto:pjb@informatimago.com">pjb@informatimago.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Le 01/02/2021 à 09:45, Marco Antoniotti a écrit :<br>
> Duh!<br>
<br>
What?<br>
<br>
(1- (integer-length x)) is not ffs.<br>
<br>
76543 10<br>
vvvvv vv<br>
#b11010100<br>
^<br>
2<br>
(ffs #b11010100) = 2<br>
(integer-length #b11010100) = 8<br>
(1- (integer-length #b11010100)) = 7<br>
<br>
(defun ffs/naive (n)<br>
(check-type n integer)<br>
(loop<br>
:for ffs :from 0<br>
:while (evenp n)<br>
:do (setf n (ash n -1))<br>
:finally (return ffs)))<br>
<br>
(ffs/naive #b11010100) ; --> 2<br>
<br>
The wikipedia page gives algorithms that are better than O(n), but with <br>
implementations in ℤ/2ⁿ instead of ℤ.<br>
<br>
Instead, you can extract the least significant 1 bit using (compose 1+ <br>
lognot) and logand:<br>
<br>
<br>
(progn<br>
(format t "~@{~32B~%~}"<br>
#b11010100<br>
(logand #xffffffff (lognot #b11010100))<br>
(logand #xffffffff (1+ (lognot #b11010100)))<br>
(logand #xffffffff (logand #b11010100<br>
(1+ (lognot #b11010100)))))<br>
(format t "~D~%"<br>
(truncate (log (logand #b11010100<br>
(1+ (lognot #b11010100))) 2)))<br>
(values))<br>
11010100<br>
11111111111111111111111100101011<br>
11111111111111111111111100101100<br>
100<br>
2<br>
<br>
(defun ffs (n)<br>
(check-type n integer)<br>
(truncate (log (logand n (1+ (lognot n))) 2)))<br>
<br>
(mapcar (function ffs)<br>
'(#b110101<br>
#b1101010<br>
#b11010100<br>
#b110101000<br>
#b1101010000))<br>
--> (0 1 2 3 4)<br>
<br>
<br>
<br>
> On Mon, Feb 1, 2021 at 9:42 AM <a href="mailto:dbm@refined-audiometrics.com" target="_blank">dbm@refined-audiometrics.com</a> <br>
> <mailto:<a href="mailto:dbm@refined-audiometrics.com" target="_blank">dbm@refined-audiometrics.com</a>> <<a href="mailto:dbm@refined-audiometrics.com" target="_blank">dbm@refined-audiometrics.com</a> <br>
> <mailto:<a href="mailto:dbm@refined-audiometrics.com" target="_blank">dbm@refined-audiometrics.com</a>>> wrote:<br>
> <br>
> (1- (integer-length x))<br>
> <br>
> <br>
>> On Feb 1, 2021, at 1:24 AM, Marco Antoniotti<br>
>> <<a href="mailto:marco.antoniotti@unimib.it" target="_blank">marco.antoniotti@unimib.it</a> <mailto:<a href="mailto:marco.antoniotti@unimib.it" target="_blank">marco.antoniotti@unimib.it</a>>><br>
>> wrote:<br>
>><br>
>> Hi<br>
>><br>
>> I am wasti.... devoting some time to recreational hacking and I<br>
>> bumped into an interesting bit fiddling operation.<br>
>><br>
>> I pored over the CLHS, but, while I may have missed something<br>
>> obvious, I am not sure what would be the best way to implement<br>
>> such a function using the standard operations.<br>
>><br>
>> Any ideas?<br>
>>b<br>
>> Note that it appears that most HW does have an instruction to do<br>
>> that directly.<br>
>> Find first set - Wikipedia<br>
>> <<a href="https://en.wikipedia.org/wiki/Find_first_set" rel="noreferrer" target="_blank">https://en.wikipedia.org/wiki/Find_first_set</a>><br>
>><br>
>> Thanks<br>
>> Marco<br>
>><br>
>> -- <br>
>> Marco Antoniotti, Associate Professortel.+39 - 02 64 48 79 01<br>
>> DISCo, Università Milano Bicocca U14<br>
>> 2043<a href="http://bimib.disco.unimib.it" rel="noreferrer" target="_blank">http://bimib.disco.unimib.it</a> <<a href="http://bimib.disco.unimib.it/" rel="noreferrer" target="_blank">http://bimib.disco.unimib.it/</a>><br>
>> Viale Sarca 336<br>
>> I-20126 Milan (MI) ITALY<br>
> <br>
> <br>
> <br>
> -- <br>
> Marco Antoniotti, Associate Professortel.+39 - 02 64 48 79 01<br>
> DISCo, Università Milano Bicocca U14 2043<a href="http://bimib.disco.unimib.it" rel="noreferrer" target="_blank">http://bimib.disco.unimib.it</a> <br>
> <<a href="http://bimib.disco.unimib.it/" rel="noreferrer" target="_blank">http://bimib.disco.unimib.it/</a>><br>
> Viale Sarca 336<br>
> I-20126 Milan (MI) ITALY<br>
<br>
<br>
-- <br>
__Pascal Bourguignon__<br>
<br>
</blockquote></div><br clear="all"><br>-- <br><div dir="ltr" class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">Marco Antoniotti, Associate Professor</span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">tel.</span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;word-spacing:0px;text-decoration:none;display:inline;float:none;white-space:pre"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">+39 - 02 64 48 79 01</span><br style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">DISCo, Università Milano Bicocca U14 2043</span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"> </span><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:pre;word-spacing:0px;text-decoration:none"></span><a href="http://bimib.disco.unimib.it/" style="font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px" target="_blank">http://bimib.disco.unimib.it</a><br style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">Viale Sarca 336</span><br style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none"><span style="color:rgb(0,0,0);font-family:Helvetica;font-size:14px;font-style:normal;font-weight:normal;letter-spacing:normal;text-align:start;text-indent:0px;text-transform:none;white-space:normal;word-spacing:0px;text-decoration:none;display:inline;float:none">I-20126 Milan (MI) ITALY</span><br></div></div></div></div>