A table-based solution is fastest:
Code: Select all
31 ms for popcounting a total of 159997056 bits
31 ms for popcounting a total of 159982282 bits
31 ms for popcounting a total of 160004121 bits
30 ms for popcounting a total of 159992999 bits
31 ms for popcounting a total of 160005776 bits
31 ms for popcounting a total of 159994165 bits
32 ms for popcounting a total of 160011071 bits
31 ms for popcounting a total of 160002935 bits
31 ms for popcounting a total of 160013670 bits
31 ms for popcounting a total of 160008316 bits
This is
PopCount (assembly) for 10 Million random integers, approx. 16*10 Mio bits.
P.S.: Adapted to FB, 25 Mio integers:
Code: Select all
0.741 seconds 50599 popcnt
0.662 seconds 50599 popcnt8
0.991 seconds 50599 countbits
0.090 seconds 50599 PopCount asm
0.149 seconds 50599 PopCount FB
0.119 seconds 50599 PopCount asm
0.142 seconds 50599 PopCount FB
0.094 seconds 50599 PopCount asm
0.146 seconds 50599 PopCount FB
Full source (btw Do ... Loop until is a tick faster than While ... Wend):
Code: Select all
#define elements 25000000
Dim Shared As Integer values(elements)
for ct as integer=0 to elements
values(ct)=int(rnd*1000000000)
next
Function pop_cnt( Byval x As Ulongint ) As Integer ''richard
Dim As Integer count = 0
Do While x
If x And 1 Then count += 1
If x And 2 Then count += 1
If x And 4 Then count += 1
If x And 8 Then count += 1
x = x Shr 4
Loop
Return count
End Function
Function pop_cnt8( Byval x As Ulongint ) As Integer ''richard
Dim As Integer count = 0
Do While x
If x And 1 Then count += 1
If x And 2 Then count += 1
If x And 4 Then count += 1
If x And 8 Then count += 1
If x And 16 Then count += 1
If x And 32 Then count += 1
If x And 64 Then count += 1
If x And 128 Then count += 1
x = x Shr 8
Loop
Return count
End Function
function countbits(num as ulongint) as integer
dim as integer count
while num
count+= num and 1
num shr=1
wend
return count
end function
Dim Shared As Integer pcTable(256)
for ct as integer=0 to 255
pcTable(ct)=pop_cnt(ct)
next
function PopCountAsm naked cdecl (num as ulongint) as integer
asm
push esi
lea esi, pcTable[0]
mov ecx, [esp+8]
movzx edx, cl
mov eax, [esi+4*edx]
movzx edx, ch
add eax, [esi+4*edx]
bswap ecx
movzx edx, cl
add eax, [esi+4*edx]
movzx edx, ch
add eax, [esi+4*edx]
pop esi
ret
end asm
end function
function PopCount(num as ulongint) as integer
dim as integer count
#if 0
While num
count+=pcTable(num and 255)
num shr=8
Wend
#else
Do
count+=pcTable(num and 255)
num shr=8
Loop Until num=0
#endif
return count
end function
randomize 1
dim as double t
dim as long ctr
ctr=0
t=timer
For i As Integer = 0 To elements
if pop_cnt(values(i))=7 then ctr+=1 'richard's
Next i
print using "#.### seconds ##### pop_cnt"; timer-t; ctr
randomize 1
ctr=0
t=timer
For i As Integer = 0 To elements
if pop_cnt8(values(i))=7 then ctr+=1 'richard's
Next i
print using "#.### seconds ##### pop_cnt8"; timer-t; ctr
randomize 1
ctr=0
t=timer
For i As Integer = 0 To elements
if countbits(values(i))=7 then ctr+=1
Next i
print using "#.### seconds ##### countbits"; timer-t; ctr
for outerct as integer =0 to 2
randomize 1
ctr=0
t=timer
For i As Integer = 0 To elements
if PopCountAsm(values(i))=7 then ctr+=1
Next i
print using "#.### seconds ##### PopCount asm"; timer-t; ctr
randomize 1
ctr=0
t=timer
For i As Integer = 0 To elements
if PopCount(values(i))=7 then ctr+=1
Next i
print using "#.### seconds ##### PopCount FB"; timer-t; ctr
next
Sleep