The MASM Forum Archive 2004 to 2012

Project Support Forums => GoAsm Assembler and Tools => Topic started by: donkey on October 13, 2011, 03:46:06 AM

Title: 64 bit population count
Post by: donkey on October 13, 2011, 03:46:06 AM
I needed to count the number of set bits in a 64 bit number in x86-64 mode and adapted the popcount function to handle 64 bits:

popcount64 FRAME Value
;mov rcx,[Value] // this is implied by fastcalll

mov r9,0x5555555555555555
mov r10,0x3333333333333333
mov r11,0x0F0F0F0F0F0F0F0F

mov rax,rcx
shr rax,1
and rax,r9
sub rcx,rax
mov rax,rcx
shr rax,2
and rcx,r10
and rax,r10
add rcx,rax
mov rax,rcx
shr rax,4
add rax,rcx
and rax,r11

mov rcx,rax
shr rcx,8
add rax,rcx
mov rcx,rax
shr rcx,16
add rax,rcx
mov rcx,rax
shr rcx,32
add rax,rcx

and rax,0x7F

RET
ENDF
Title: Re: 64 bit population count
Post by: drizz on October 13, 2011, 10:02:56 AM
Algo from "Hacker's Delight" book:
option prologue:none, epilogue:none
.code
BitCount proc Value
mov rax,rcx
mov rdx,rcx
mov rcx,07777777777777777h
mov r8,00F0F0F0F0F0F0F0Fh
mov r9,00101010101010101h
shr rdx,1
and rdx,rcx
sub rax,rdx
shr rdx,1
and rdx,rcx
sub rax,rdx
shr rdx,1
and rdx,rcx
sub rax,rdx
mov rdx,rax
shr rdx,4
add rax,rdx
and rax,r8
imul rax,r9
shr rax,64-8
ret
BitCount endp
end