Another (stupid) question: "find first set" (or "find first zero")

[Pascal Bourguignon]

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> <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>>
>>     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>
>>
>>     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/>
>>     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/>
> Viale Sarca 336
> I-20126 Milan (MI) ITALY


-- 
__Pascal Bourguignon__