Easy way to count the number of 1's in a long?

Rayman

Ok, so I have two longs and I want to count the total number of binary 1's in both of them.

It seems that there should be a direct way to do it in Spin, but it escapes me...

In my particular problem the result is between 0 and 8. (Chess bitboard)

I'm thinking that a look with the Spin "bitwise encode" operator will be the fastest method of doing this.

But, I have a feeling that I'm missing something...

Anybody see a simple way to do this?

CJ

it would just be a tight loop in assembly
mov sample, temp1
mov temp2, #32
mov temp3, #0
loop: shr temp1, #1 wc
if_c add temp3, #1
djnz temp2, #loop:

the result will be in temp3

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.

Phil Pilgrim (PhiPi)

In Spin, try this:

PUB Count(sample)

  repeat while sample
    result += lookupz(sample & %1111: 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4)
    sample >>= 4

It chunks the long into 4-bit blocks and adds the results from a pre-computed lookup table for each of them.

-Phil

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
'Still some PropSTICK Kit bare PCBs left!

Post Edited (Phil Pilgrim (PhiPi)) : 8/30/2008 3:27:42 AM GMT

CJ

nifty!

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Parallax Forums - If you're ready to learn, we're ready to help.

rokicki

If you don't expect too many bits to be set, you can use:

r := 0
while x
   r++
   x &= x-1

Tracy Allen

I was going to suggest,

n := 0
while x
   n++
   x := x - |< (>|  x -1)   ' encode decode knock down bits

but x &= x-1 is much niftier. There is also,

x := (x & $55555555) + (x>>1 & $55555555)
x := (x & $33333333) + (x>>2 & $33333333)
x := (x & $0F0F0F0F) + (x>>4 & $0F0F0F0F)
x := (x & $00FF00FF) + (x>>8 & $00FF00FF)
x := (x & $0000FFFF) + (x>>16)  ' x now is the bit count

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Tracy Allen
www.emesystems.com

Rayman

Thanks! Great ideas. Now, I just have to figure out which is fastest...

MikeK

You can unroll Phil's loop to remove the loop overhead. You'd end up with 15 instructions, since you don't need the last shift.

Post Edited (MikeK) : 8/30/2008 2:14:50 PM GMT

Phil Pilgrim (PhiPi)

Rayman,

If you do unroll my loop, create an array of bytes in the DAT area and index them, instead of using LOOKUPZ, to save memory.

Tracy,

Wow! A log n solution. I knew there had to be a way but couldn't quite get there. Guys, if you haven't yet taken the time to understand Tracy's second method, do so now. It's a work of art!

-Phil

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
'Still some PropSTICK Kit bare PCBs left!