Another (stupid) question: "find first set" (or "find first zero")

[Marco Antoniotti]

Duh again!

MA

On Mon, Feb 1, 2021 at 7:47 PM Pascal Bourguignon <pjb at informatimago.com>
wrote:

> Le 01/02/2021 à 09:45, Marco Antoniotti a écrit :
> > Duh!
>
> What?
>
> (1- (integer-length x)) is not ffs.
>
>    76543 10
>    vvvvv vv
> #b11010100
>         ^
>         2
> (ffs #b11010100) = 2
> (integer-length #b11010100) = 8
> (1- (integer-length #b11010100)) = 7
>
> (defun ffs/naive (n)
>    (check-type n integer)
>    (loop
>      :for ffs :from 0
>      :while (evenp n)
>      :do (setf n (ash n -1))
>      :finally (return ffs)))
>
> (ffs/naive #b11010100) ; --> 2
>
> The wikipedia page gives algorithms that are better than O(n), but with
> implementations in ℤ/2ⁿ instead of ℤ.
>
> Instead, you can extract the least significant 1 bit using (compose 1+
> lognot) and logand:
>
>
> (progn
>    (format t "~@{~32B~%~}"
>            #b11010100
>            (logand #xffffffff (lognot #b11010100))
>            (logand #xffffffff (1+ (lognot #b11010100)))
>            (logand #xffffffff (logand #b11010100
>                                  (1+ (lognot #b11010100)))))
>    (format t "~D~%"
>            (truncate (log (logand #b11010100
>                                  (1+ (lognot #b11010100))) 2)))
>    (values))
>                          11010100
> 11111111111111111111111100101011
> 11111111111111111111111100101100
>                               100
> 2
>
> (defun ffs (n)
>    (check-type n integer)
>    (truncate (log (logand n (1+ (lognot n))) 2)))
>
> (mapcar (function ffs)
>          '(#b110101
>            #b1101010
>            #b11010100
>            #b110101000
>            #b1101010000))
> --> (0 1 2 3 4)
>
>
>
> > On Mon, Feb 1, 2021 at 9:42 AM dbm at refined-audiometrics.com
> > <mailto:dbm at refined-audiometrics.com> <dbm at refined-audiometrics.com
> > <mailto:dbm at refined-audiometrics.com>> wrote:
> >
> >     (1- (integer-length x))
> >
> >
> >>     On Feb 1, 2021, at 1:24 AM, Marco Antoniotti
> >>     <marco.antoniotti at unimib.it <mailto:marco.antoniotti at unimib.it>>
> >>     wrote:
> >>
> >>     Hi
> >>
> >>     I am wasti....  devoting some time to recreational hacking and I
> >>     bumped into an interesting bit fiddling operation.
> >>
> >>     I pored over the CLHS, but, while I may have missed something
> >>     obvious, I am not sure what would be the best way to implement
> >>     such a function using the standard operations.
> >>
> >>     Any ideas?
> >>b
> >>     Note that it appears that most HW does have an instruction to do
> >>     that directly.
> >>     Find first set - Wikipedia
> >>     <https://en.wikipedia.org/wiki/Find_first_set>
> >>
> >>     Thanks
> >>     Marco
> >>
> >>     --
> >>     Marco Antoniotti, Associate Professortel.+39 - 02 64 48 79 01
> >>     DISCo, Università Milano Bicocca U14
> >>     2043http://bimib.disco.unimib.it <http://bimib.disco.unimib.it/>
> >>     Viale Sarca 336
> >>     I-20126 Milan (MI) ITALY
> >
> >
> >
> > --
> > Marco Antoniotti, Associate Professortel.+39 - 02 64 48 79 01
> > DISCo, Università Milano Bicocca U14 2043http://bimib.disco.unimib.it
> > <http://bimib.disco.unimib.it/>
> > Viale Sarca 336
> > I-20126 Milan (MI) ITALY
>
>
> --
> __Pascal Bourguignon__
>
>

-- 
Marco Antoniotti, Associate Professor         tel. +39 - 02 64 48 79 01
DISCo, Università Milano Bicocca U14 2043 http://bimib.disco.unimib.it
Viale Sarca 336
I-20126 Milan (MI) ITALY
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/pro/attachments/20210201/e3f807ff/attachment.html>