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?
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
(1- (integer-length x))
On Feb 1, 2021, at 1:24 AM, Marco Antoniotti 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?
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 Professor tel. +39 - 02 64 48 79 01 DISCo, Università Milano Bicocca U14 2043 http://bimib.disco.unimib.it http://bimib.disco.unimib.it/ Viale Sarca 336 I-20126 Milan (MI) ITALY
Duh!
On Mon, Feb 1, 2021 at 9:42 AM dbm@refined-audiometrics.com < dbm@refined-audiometrics.com> wrote:
(1- (integer-length x))
On Feb 1, 2021, at 1:24 AM, Marco Antoniotti 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?
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 Professor tel. +39 - 02 64 48 79 01 DISCo, Università Milano Bicocca U14 2043 http://bimib.disco.unimib.it Viale Sarca 336 I-20126 Milan (MI) ITALY
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 <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>> 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
Duh again!
MA
On Mon, Feb 1, 2021 at 7:47 PM Pascal Bourguignon 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 <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>> 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__
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 <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
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 pjb@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 <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), butwith
implementations in ℤ/2ⁿ instead of ℤ. Instead, you can extract the least significant 1 bit using (compose1+
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 hackingand 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 toimplement
>> such a function using the standard operations. >> >> Any ideas? >>b >> Note that it appears that most HW does have an instructionto 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__
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__
Le 02/02/2021 à 13:40, Martin Simmons a écrit :
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.
Yes, that's what I meant. Sorry for the confusion.
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.
Indeed.
Note: if we have access to the implementation of bignum (eg. if we patch the implementation to provide ffs "natively"), we can optimize even more by merging the two solutions.
(- x) would process the whole bignum, as would (logand x (- x)), but after this operation, we have only 0s on the left of the bignum.
Instead, we can process the bignum word by word (starting with the least significant word), computing: (+ (lognot (bignum-word-ref bignum i)) carry) -> i+1, new-carry and (logand (bignum-word-ref bignum i) (+ (lognot (bignum-word-ref bignum i)) carry)) while we get 0. Once we get a value ≠ 0, it has a single bit set which we can identify with integer-length or looping etc (we process a single word here), and stop processing now, because all the other words will give 0 as result.
On Tue, 2 Feb 2021 14:00:08 +0100, Pascal Bourguignon said:
Note: if we have access to the implementation of bignum (eg. if we patch the implementation to provide ffs "natively"), we can optimize even more by merging the two solutions.
(- x) would process the whole bignum, as would (logand x (- x)), but after this operation, we have only 0s on the left of the bignum.
Instead, we can process the bignum word by word (starting with the least significant word), computing: (+ (lognot (bignum-word-ref bignum i)) carry) -> i+1, new-carry and (logand (bignum-word-ref bignum i) (+ (lognot (bignum-word-ref bignum i)) carry)) while we get 0. Once we get a value ≠ 0, it has a single bit set which we can identify with integer-length or looping etc (we process a single word here), and stop processing now, because all the other words will give 0 as result.
Even better, we can just do logbitp ≠ 0 in word-sized chunks. I.e. scan from the least significant word until (bignum-word-ref bignum i) is non-zero and then, as you say, process that non-zero word in some way to find the first 1.
-
dbm＠refined-audiometrics.com -
Marco Antoniotti -
Martin Simmons -
Pascal Bourguignon -
Steve Haflich