Compute parity of a bit vector

Specific Domains Numerics
1

Iā€™m trying to compute the dot product of two UInt8 bit vectors. First I bitwise-xor them, then I have to compute the parity of the result.

Is there a simple way to compute the parity of a single byte stored in a UInt8, using only elementary operations like xor, and, shifts, etc.?

2

I think the following might do what you want:

julia> parity(x::T) where {T} = T(isodd(count_ones(x)))

julia> parity(UInt8(1))
0x01

julia> parity(UInt8(2))
0x01

julia> parity(UInt8(3))
0x00

This also generates some nice machine code, so should be pretty quick.

julia> code_native(parity, (UInt8,); syntax = :intel)
	.section	__TEXT,__text,regular,pure_instructions
; ā”Œ @ REPL[17]:1 within `parity'
; ā”‚ā”Œ @ REPL[17]:1 within `count_ones'
	movzx	eax, dil
	popcnt	eax, eax
; ā”‚ā””
; ā”‚ā”Œ @ boot.jl:712 within `Type'
; ā”‚ā”‚ā”Œ @ boot.jl:659 within `toUInt8'
	and	al, 1
; ā”‚ā””ā””
	ret
	nop	dword ptr [rax + rax]
; ā””
2 Likes
3

Amazing, the compiler just uses popcnt directly. No cumbersome function calls. Thanks!

1 Like
4

it really just comes with https://github.com/JuliaLang/julia/blob/c6da87ff4bc7a855e217856757ad3413cf6d1f79/base/int.jl#L354

1 Like