[R6RS] a better spec for bitwise-bit-count

William D Clinger will at ccs.neu.edu
Wed May 9 13:55:57 EDT 2007

Here's a suggestion that I think we should adopt.
Can we add it to the agenda for tomorrow?



Alan Bawden wrote [1]:
> If bitwise-bit-count was defined as:
>   (define (bitwise-bit-count n)
>     (if (negative? n)
> 	(- (+ 1 (bitwise-bit-count (bitwise-not n))))
> 	<whatever>))
> Then you could count the bits set in an N-bit word by taking
> the bitwise-bit-count mod N+1.

Ben Harris, who had inspired Alan's suggestion, replied [2]:
> Indeed, and it wouldn't break the other nice property I'd produced.  It 
> loses a little symmetry, in that (- (bitwise-bit-count x)) is no longer 
> equal to (bitwise-bit-count (bitwise-not x)), but two's-complement 
> arithmetic is inherently asymmetric like this, so I'm not sure that's a 
> bad thing.

To which Alan responded [3]:
> You want symmetry?  I'll give you symmetry...  Under the revised definition
> (bitwise-not (bitwise-bit-count x)) is equal to
> (bitwise-bit-count (bitwise-not x))!
> In fact I could have written the definition this way:
>    (define (bitwise-bit-count n)
>      (if (negative? n)
> 	 (bitwise-not (bitwise-bit-count (bitwise-not n)))
> 	 <whatever>))

Finally, Ben Harris wrote [4]:
> I can't take credit for the original idea -- it was suggested to me by 
> Simon Tatham.

[1] http://lists.r6rs.org/pipermail/r6rs-discuss/2007-April/002288.html
[2] http://lists.r6rs.org/pipermail/r6rs-discuss/2007-April/002292.html
[3] http://lists.r6rs.org/pipermail/r6rs-discuss/2007-April/002293.html
[4] http://lists.r6rs.org/pipermail/r6rs-discuss/2007-April/002294.html

More information about the R6RS mailing list