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