# Compute parity of a bit vector

**URL:** <https://discourse.julialang.org/t/compute-parity-of-a-bit-vector/28453>\
**Category:** Numerics\
**Created:** [September 6, 2019, 2:11am UTC](https://discourse.julialang.org/t/compute-parity-of-a-bit-vector/28453 "2019-09-06T02:11:31Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![Deniz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/deniz/32/10151_2.png) [@Deniz](https://discourse.julialang.org/u/Deniz)\
**Post date:** [September 6, 2019, 2:11am UTC](https://discourse.julialang.org/t/compute-parity-of-a-bit-vector/28453/1 "2019-09-06T02:11:31Z")

</div>

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.?

---

<div class="post-metadata">

**Author:** ![hildebrandmw](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/hildebrandmw/32/3850_2.png) [@hildebrandmw](https://discourse.julialang.org/u/hildebrandmw)\
**Post date:** [September 6, 2019, 2:34am UTC](https://discourse.julialang.org/t/compute-parity-of-a-bit-vector/28453/2 "2019-09-06T02:34:19Z")

</div>

I think the following might do what you want:

```julia
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
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]
; └

```

---

<div class="post-metadata">

**Author:** ![Deniz](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/deniz/32/10151_2.png) [@Deniz](https://discourse.julialang.org/u/Deniz)\
**Post date:** [September 6, 2019, 4:36am UTC](https://discourse.julialang.org/t/compute-parity-of-a-bit-vector/28453/3 "2019-09-06T04:36:19Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![jling](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/jling/32/212909_2.png) [@jling](https://discourse.julialang.org/u/jling)\
**Post date:** [September 6, 2019, 10:11am UTC](https://discourse.julialang.org/t/compute-parity-of-a-bit-vector/28453/4 "2019-09-06T10:11:10Z")

</div>

> [@hildebrandmw](#):
>
> count\_ones

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