On Mon, 23 Apr 2007, Alan Bawden wrote:
> Date: Tue, 17 Apr 2007 21:03:57 +0100 (BST)
> From: Ben Harris <bjh21 at bjh21.me.uk>
>
> ... Also, for arguments that fit in a particular word
> size, the number of set bits in the argument represented
> in a word of that size can be obtained by taking the
> result modulo the word size, regardless of the sign of
> the argument.
>
> This can't be true. Since the number of bits set in a
> 32-bit word (for example) can be anything from 0 to 32
> -inclusive-, it cannot be true that you can count the set
> bits by taking something mod 32.
Ah, yes, I think I got carried away with the cuteness of the idea and
didn't bother to check it was actually true.
> 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. This would also make the
> claim in the subject actually true.
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.
--
Ben Harris
Received on Mon Apr 23 2007 - 18:50:04 UTC