<div dir="ltr">For completeness, contemplate this function which similarly returns the position of the first significant zero bit, or nil, if there is no such zero bit:<div><br></div><div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><blockquote style="margin:0 0 0 40px;border:none;padding:0px"></blockquote></blockquote>(defun first0 (n)<br> ;; Return the integer bit position of the most significant zero-bit in the<br> ;; argument integer, or nil if there is no such zero bit.<br> (let ((r (1- (integer-length (logandc1 n (1- (ash 1 (integer-length n))))))))<br> (and (>= r 0) r)))</div><div><br></div><div>Curiously, this definition works correctly for negative integers.</div><div><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><blockquote style="margin:0 0 0 40px;border:none;padding:0px"><br></blockquote></blockquote></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Feb 1, 2021 at 11:13 AM 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 à 19:51, Marco Antoniotti a écrit :<br>
> Duh again!<br>
<br>
What?<br>
<br>
<br>
Note that the naive version is not necessarily worse than the "smart" <br>
one, on bignums. On numbers like (+ (expt 2 1000) (expt 2 10)), <br>
logand, lognot and even 1+ will have to process the whole bignum, with a <br>
lot of memory accesses, while the naive loop would access only one word.<br>
<br>
<br>
> MA<br>
> <br>
> On Mon, Feb 1, 2021 at 7:47 PM Pascal Bourguignon <<a href="mailto:pjb@informatimago.com" target="_blank">pjb@informatimago.com</a> <br>
> <mailto:<a href="mailto:pjb@informatimago.com" target="_blank">pjb@informatimago.com</a>>> wrote:<br>
> <br>
> 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>><br>
> > <mailto:<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>><br>
> > <mailto:<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><br>
> <mailto:<a href="mailto:marco.antoniotti@unimib.it" target="_blank">marco.antoniotti@unimib.it</a>><br>
> <mailto:<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>
> <<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><br>
> <<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>
> <<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<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>
> > <<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>
> __Pascal Bourguignon__<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>