Enhancement Request: Adding population count for Integers to the standard image

Richard A. O'Keefe ok at cs.otago.ac.nz
Thu Dec 9 01:13:20 UTC 2004


"Matthew Hamrick" <Matthew.Hamrick at gibson.com> wrote
(edited somewhat to take fewer lines and be more ASCII-friendly):

	popCount
	 "Answers the number of bits set in an integer."
	 | t1 t2 |
	 t1 := self.
	 t2 := 0.
	 [t1 == 0] whileFalse: [t1 := t1 bitAnd: t1 - 1. t2 := t2 + 1].
	 ^ t2

What is this supposed to do when the number is negative?

    -1 bitAnd: -2	=> -2
    -2 bitAnd: -3	=> -4
    -4 bitAnd: -5	=> -8

In Squeak 3.6-5429-full.image, (-1 popCount) eventually terminates because
    m := -1 bitShift: 31.
    m := m bitAnd: m - 1
sets m to 0, instead of to the correct value (-1 bitShift: 32).
First time I've ever had Squeak give me the wrong answer for an
integer calculation.

Notionally, a Squeak negative integer has infinitely many 1 bits, so I
suggest

    popCount
      "self >= 0 => answer the number of 1 bits in the binary representation.
       self <  0 => answer the number of 0 bits in the binary representation.
       Two's complement is assumed.
      "
      |m n|
      (m := self) < 0 ifTrue: [m := -1 - self].
      n := 0.
      [m == 0] whileFalse: [m := m bitAnd: m-1. n := n+1].
      ^n

Another alternative would be to make it an error to send #popCount to a
negative integer.




More information about the Squeak-dev mailing list