[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: another operation



 | From: sebastian.egner@xxxxxxxxxxx
 | Date: Tue, 4 Jan 2005 10:18:14 +0100
 | 
 | 1. As it turns out, I frequently need the following operation missing
 | in SRFI-60:
 | 
 |         (FOO x) ==> i ; this is not my proposal for the procedure's
 |         name ;-)
 | 
 |         i >= 0 is the index of the least significant bit set in
 |         integer x in case x > 0,
 | 
 |         or in -x-1 if x < 0. If x = 0 then [choose: i = -1 OR (error
 |         ...) OR i = #f OR ...]
 | 
 |            In other words, i = max {k >= 0 : 2^k divides x} for x > 0.

I added log2-binary-factors to SRFI-60.  How about a better name for
it?

			      -=-=-=-=-

log2-binary-factors is a useful function which is simple but non-obvious:

(define (log2-binary-factors n)
  (+ -1 (integer-length (logand n (- n)))))

				 ...

_Function:_ *log2-binary-factors* /n/
    Returns the number of factors of two of integer n. This value is
    also the bit-index of the least-significant `1' bit in n.

(require 'printf)
(do ((idx 0 (+ 1 idx)))
      ((> idx 16))
    (printf "%s(%3d) ==> %-5d %s(%2d) ==> %-5d\n"
            'log2-binary-factors
            (- idx) (log2-binary-factors (- idx))
            'log2-binary-factors
            idx (log2-binary-factors idx)))
-|
log2-binary-factors(  0) ==> -1    log2-binary-factors( 0) ==> -1   
log2-binary-factors( -1) ==> 0     log2-binary-factors( 1) ==> 0    
log2-binary-factors( -2) ==> 1     log2-binary-factors( 2) ==> 1    
log2-binary-factors( -3) ==> 0     log2-binary-factors( 3) ==> 0    
log2-binary-factors( -4) ==> 2     log2-binary-factors( 4) ==> 2    
log2-binary-factors( -5) ==> 0     log2-binary-factors( 5) ==> 0    
log2-binary-factors( -6) ==> 1     log2-binary-factors( 6) ==> 1    
log2-binary-factors( -7) ==> 0     log2-binary-factors( 7) ==> 0    
log2-binary-factors( -8) ==> 3     log2-binary-factors( 8) ==> 3    
log2-binary-factors( -9) ==> 0     log2-binary-factors( 9) ==> 0    
log2-binary-factors(-10) ==> 1     log2-binary-factors(10) ==> 1    
log2-binary-factors(-11) ==> 0     log2-binary-factors(11) ==> 0    
log2-binary-factors(-12) ==> 2     log2-binary-factors(12) ==> 2    
log2-binary-factors(-13) ==> 0     log2-binary-factors(13) ==> 0    
log2-binary-factors(-14) ==> 1     log2-binary-factors(14) ==> 1    
log2-binary-factors(-15) ==> 0     log2-binary-factors(15) ==> 0    
log2-binary-factors(-16) ==> 4     log2-binary-factors(16) ==> 4