On Mon, 1 Feb 2021 20:12:48 +0100, Pascal Bourguignon said:
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.
Really?
The naive version below repeatedly does (setf n (ash n -1)), which most likely accesses the whole bignum and allocates a new one each time. A better naive version would use logbitp instead of evenp and not modify n.
I think this definition does reasonably well too:
(defun ffs (x) (1- (integer-length (logand x (- x)))))
I would avoid using log because it may get floating-point overflow for large values.
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__