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@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@informatimago.com
> <mailto:pjb@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@refined-audiometrics.com
>     <mailto:dbm@refined-audiometrics.com>
>      > <mailto:dbm@refined-audiometrics.com
>     <mailto:dbm@refined-audiometrics.com>> <dbm@refined-audiometrics.com
>     <mailto:dbm@refined-audiometrics.com>
>      > <mailto:dbm@refined-audiometrics.com
>     <mailto:dbm@refined-audiometrics.com>>> wrote:
>      >
>      >     (1- (integer-length x))
>      >
>      >
>      >>     On Feb 1, 2021, at 1:24 AM, Marco Antoniotti
>      >>     <marco.antoniotti@unimib.it
>     <mailto:marco.antoniotti@unimib.it>
>     <mailto:marco.antoniotti@unimib.it <mailto:marco.antoniotti@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__