EnableExplicit
Procedure.l PopCount0 (k.l)
! mov eax, [p.v_k]
! popcnt eax, eax
ProcedureReturn
EndProcedure
Procedure.l PopCount1 (k.l)
; -- wilbert
!xor eax, eax
!mov edx, [p.v_k]
!and edx, edx
!jz popcount_m2_done
!popcount_m2_loop:
!inc eax
!lea ecx, [edx - 1]
!and edx, ecx
!jnz popcount_m2_loop
!popcount_m2_done:
ProcedureReturn
EndProcedure
Procedure.l PopCount2 (k.l)
; -- luis
!mov edx, [p.v_k]
!xor eax, eax
!mov ecx, 32
!popcount2:
!shl edx, 1
!adc eax, 0
!dec ecx
!jnz popcount2
ProcedureReturn
EndProcedure
Procedure.l PopCount3 (k.l)
; -- luis
!mov edx, [p.v_k]
!xor eax, eax
!mov ecx, 32
!popcount3:
!shl edx, 1
!adc eax, 0
!loop popcount3
ProcedureReturn
EndProcedure
Procedure.l PopCount4 (k.l)
; -- LJ
! mov edx, [p.v_k]
! xor eax, eax
! mov ecx, 32
! popcount_again:
! dec ecx
! bt edx, ecx
! jnc popcount_notset
! inc eax
! popcount_notset:
! or ecx, ecx
! jnz popcount_again
ProcedureReturn
EndProcedure
Procedure.l PopCount5 (v.l, i = 0)
; -- Trond
If i < 32
ProcedureReturn (v & 1 << i) >> i + PopCount5(v, i+1)
EndIf
EndProcedure
Procedure.l PopCount6 (v.l)
; -- Trond
Protected i.i, Agg.l
For i = 0 To 31
Agg + (v & 1 << i) >> i
Next
ProcedureReturn Agg
EndProcedure
Procedure.l Popcount7 (x.l)
; -- idle (adapted for 32 bit)
;x - (x >> 1) & $55555555
!mov eax, [p.v_x]
!mov edx, eax
!shr edx, 1
!and edx, 0x55555555
!sub eax, edx
;x = (x & $33333333) + ((x >> 2) & $33333333)
!mov edx, eax ;x
!and eax, 0x33333333
!shr edx, 2
!and edx, 0x33333333
!add eax, edx
;x = (x + (x >> 4)) & $0f0f0f0f0f
!mov edx, eax
!shr edx, 4
!add eax, edx
!and eax, 0x0f0f0f0f
;x * 0x01010101 >> 24
!imul eax, 0x01010101
!shr eax, 24
ProcedureReturn
EndProcedure
Procedure.l Popcount8(v.l)
; --- Trond without a loop
Protected y.l
y = (v & 1 << 0) >> 0 +
(v & 1 << 1) >> 1 +
(v & 1 << 2) >> 2 +
(v & 1 << 3) >> 3 +
(v & 1 << 4) >> 4 +
(v & 1 << 5) >> 5 +
(v & 1 << 6) >> 6 +
(v & 1 << 7) >> 7 +
(v & 1 << 8) >> 8 +
(v & 1 << 9) >> 9 +
(v & 1 << 10) >> 10 +
(v & 1 << 11) >> 11 +
(v & 1 << 12) >> 12 +
(v & 1 << 13) >> 13 +
(v & 1 << 14) >> 14 +
(v & 1 << 15) >> 15 +
(v & 1 << 16) >> 16 +
(v & 1 << 17) >> 17 +
(v & 1 << 18) >> 18 +
(v & 1 << 19) >> 19 +
(v & 1 << 20) >> 20 +
(v & 1 << 21) >> 21 +
(v & 1 << 22) >> 22 +
(v & 1 << 23) >> 23 +
(v & 1 << 24) >> 24 +
(v & 1 << 25) >> 25 +
(v & 1 << 26) >> 26 +
(v & 1 << 27) >> 27 +
(v & 1 << 28) >> 28 +
(v & 1 << 29) >> 29 +
(v & 1 << 30) >> 30 +
(v & 1 << 31) >> 31
ProcedureReturn y
EndProcedure
Procedure popcount9(i.l)
Protected j.i
j = (i >> 1) & $55555555;
i = i - j; // (A)
i = (i & $33333333) + ((i >> 2) & $33333333); // (B)
i = (i & $0F0F0F0F) + ((i >> 4) & $0F0F0F0F); // (C)
i = i * $01010101; // (D)
ProcedureReturn i >> 24;
EndProcedure
Procedure NumOfBitsSet(N.q)
;=======================================================
;Counts the number of bits set in N and returns the
;count as an integer.
;=======================================================
Protected Count.i
If N < 0
ProcedureReturn -1
Else
While N > 0
If N & 1 = 1
Count + 1
EndIf
N >> 1
Wend
ProcedureReturn Count
EndIf
EndProcedure
; ---- Initialisation ----
Define.i i, x, rep=10000000
Define.i t0, t1, t2, t3, t4, t5, t6, t7, t8, t9, ta
Dim Rnd.l(rep)
For i = 1 To rep
Rnd(i) = Random(2147483647)
Next
; ---- Small check whether all procedures return the same results ----
For i = 1 To 100
x = PopCount0(Rnd(i))
If x <> PopCount1(Rnd(i)) Or
x <> PopCount2(Rnd(i)) Or
x <> PopCount3(Rnd(i)) Or
x <> PopCount4(Rnd(i)) Or
x <> PopCount5(Rnd(i)) Or
x <> PopCount6(Rnd(i)) Or
x <> PopCount7(Rnd(i)) Or
x <> PopCount8(Rnd(i)) Or
x <> PopCount9(Rnd(i)) Or
x <> NumOfBitsSet(Rnd(i))
MessageRequester("Error",
"Different results for PopCount(" + Rnd(i) + ")")
End
EndIf
Next
; ---- Speed test ----
t0 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount0(Rnd(i))
Next
t0 = ElapsedMilliseconds() - t0
t1 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount1(Rnd(i))
Next
t1 = ElapsedMilliseconds() - t1
t2 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount2(Rnd(i))
Next
t2 = ElapsedMilliseconds() - t2
t3 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount3(Rnd(i))
Next
t3 = ElapsedMilliseconds() - t3
t4 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount4(Rnd(i))
Next
t4 = ElapsedMilliseconds() - t4
t5 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount5(Rnd(i))
Next
t5 = ElapsedMilliseconds() - t5
t6 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount6(Rnd(i))
Next
t6 = ElapsedMilliseconds() - t6
t7 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount7(Rnd(i))
Next
t7 = ElapsedMilliseconds() - t7
t8 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount8(Rnd(i))
Next
t8 = ElapsedMilliseconds() - t8
t9 = ElapsedMilliseconds()
For i = 1 To rep
x = PopCount9(Rnd(i))
Next
t9 = ElapsedMilliseconds() - t9
ta = ElapsedMilliseconds()
For i = 1 To rep
x = NumOfBitsSet(Rnd(i))
Next
ta = ElapsedMilliseconds() - ta
MessageRequester("PopCount speed test",
"t0 = " + t0 + " ms (" + Int(100*t0/t1) + "%) (Intel)" + #LF$ +
"t1 = " + t1 + " ms (100%) (wilbert)" + #LF$ +
"t2 = " + t2 + " ms (" + Int(100*t2/t1) + "%) (luis)" + #LF$ +
"t3 = " + t3 + " ms (" + Int(100*t3/t1) + "%) (luis2)" + #LF$ +
"t4 = " + t4 + " ms (" + Int(100*t4/t1) + "%) Little John)" + #LF$ +
"t5 = " + t5 + " ms (" + Int(100*t5/t1) + "%) (Trond)" + #LF$ +
"t6 = " + t6 + " ms (" + Int(100*t6/t1) + "%) (Trond2)" + #LF$ +
"t7 = " + t7 + " ms (" + Int(100*t7/t1) + "%) (idle)" + #LF$ +
"t8 = " + t8 + " ms (" + Int(100*t8/t1) + "%) (said version of trond unrolled)" + #LF$ +
"t9 = " + t9 + " ms (" + Int(100*t9/t1) + "%) (idle-PB)" + #LF$ +
"ta = " + ta + " ms (" + Int(100*ta/t1) + "%) (davido)")
or in x64
Procedure PopCount64(x.q)
!mov rax, [p.v_x]
!mov rdx, rax
!shr rdx, 1
!and rdx, [popcount64_v55]
!sub rax, rdx
;x = (x & $3333333333333333) + ((x >> 2) & $3333333333333333)
!mov rdx, rax ;x
!and rax, [popcount64_v33]
!shr rdx, 2
!and rdx, [popcount64_v33]
!add rax, rdx
;x = (x + (x >> 4)) & $0f0f0f0f0f0f0f0f0f0f
!mov rdx, rax
!shr rdx, 4
!add rax, rdx
!and rax, [popcount64_v0f]
;x * $0101010101010101 >> 56
!imul rax, [popcount64_v01]
!shr rax, 56
ProcedureReturn
!popcount64_v01: dq 0x0101010101010101
!popcount64_v0f: dq 0x0f0f0f0f0f0f0f0f
!popcount64_v33: dq 0x3333333333333333
!popcount64_v55: dq 0x5555555555555555
EndProcedure
;---------------------------------------------
x = Random($FFFFFFFF)
Debug Bin(x)
Debug Popcount64(x)
from: PureBasic Forum (http://www.purebasic.fr/english/viewtopic.php?f=35&t=62235&start=15)