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

[Steve Haflich]

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:

(defun first0 (n)
  ;; Return the integer bit position of the most significant zero-bit in the
  ;; argument integer, or nil if there is no such zero bit.
  (let ((r (1- (integer-length (logandc1 n (1- (ash 1 (integer-length
n))))))))
    (and (>= r 0) r)))

Curiously, this definition works correctly for negative integers.



On Mon, Feb 1, 2021 at 11:13 AM Pascal Bourguignon <pjb at informatimago.com>
wrote:

> Le 01/02/2021 à 19:51, Marco Antoniotti a écrit :
> > Duh again!
>
> What?
>
>
> Note that the naive version is not necessarily worse than the "smart"
> one, on bignums.   On numbers like (+ (expt 2 1000) (expt 2 10)),
> logand, lognot and even 1+ will have to process the whole bignum, with a
> lot of memory accesses, while the naive loop would access only one word.
>
>
> > MA
> >
> > On Mon, Feb 1, 2021 at 7:47 PM Pascal Bourguignon <pjb at informatimago.com
> > <mailto: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>
> >      > <mailto:dbm at refined-audiometrics.com
> >     <mailto:dbm at refined-audiometrics.com>> <dbm at refined-audiometrics.com
> >     <mailto:dbm at refined-audiometrics.com>
> >      > <mailto: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>
> >     <mailto: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
> >     <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> <http://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>
> >      > <http://bimib.disco.unimib.it/ <http://bimib.disco.unimib.it/>>
> >      > Viale Sarca 336
> >      > I-20126 Milan (MI) ITALY
> >
> >
> >     --
> >     __Pascal Bourguignon__
> >
> >
> >
> > --
> > 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__
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.common-lisp.net/pipermail/pro/attachments/20210201/c54f8f2e/attachment-0001.html>