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__
