;;; -*- Mode: Scheme -*-

;;

#>
/* Number of 1 bits */
static C_uword
C_uword_bits( C_uword n )
{
# define TWO( c )       ( ((C_uword) 1u) << (c))
# define MASK( c )      (((C_uword) -1) / (TWO( TWO( c ) ) + 1u))
# define COUNT( x, c )  ((x) & MASK( c )) + (((x) >> (TWO( c ))) & MASK( c ))

  if (0 == n) return 0;

	n = COUNT( n, 0 );
	n = COUNT( n, 1 );
	n = COUNT( n, 2 );
	n = COUNT( n, 3 );
	n = COUNT( n, 4 );
# ifdef C_SIXTY_FOUR
	n = COUNT( n, 5 );
# endif

	return n;

# undef COUNT
# undef MASK
# undef TWO
}
<#

;;

(define *uword-size* (foreign-type-size "C_uword"))

(define uword-bit-count
  (foreign-lambda* integer ((integer n))
    "return( C_uword_bits( (C_uword) n ) );"))

(: bit-count (number --> fixnum))

(define (bit-count i)
  ;Brian Kernighan’s Algorithm
  (let count ((i i) (c 0))
    (if (positive? i)
      (if (fixnum? i)
        (+ c (uword-bit-count i))
        (count (bitwise-and i (sub1 i)) (add1 c)) )
      c ) ) )

;FIXME handle negative bignums (split into uword chunks
;#ints = (modulo (integer-length (- i)) (sizeof uword))
;repeat for #ints: mask low uword bits, count low uword bits, i >> (sizeof uword)
;
;NOTE (integer-length -1) = 0