Another (stupid) question: "find first set" (or "find first zero")
Martin Simmons
martin at lispworks.com
Tue Feb 2 12:40:20 UTC 2021
>>>>> 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 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__
>
--
Martin Simmons
LispWorks Ltd
http://www.lispworks.com/
More information about the pro
mailing list