VB.NET - How to calculate the parity bit of a byte array

Question

What is the most efficient way calculate the parity bit (if the number of active bits are odd or even) in a byte array? I have though about iterating through all the bits and summing up the active bits, but that would be very impractical purely based on the number of iterations required on larger byte arrays/files.

Answer 1

For your convenience (and my curiosity), I have done some timing tests with a parity lookup table compared to the other two methods suggested so far:

Module Module1

    Dim rand As New Random

    Dim parityLookup(255) As Integer

    Sub SetUpParityLookup()
        ' setBitsCount data from http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer

        Dim setBitsCount = {
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
    }
        For i = 0 To 255
            parityLookup(i) = setBitsCount(i) And 1
        Next

    End Sub

    ' Method using lookup table
    Function ParityOfArray(a() As Byte) As Integer
        Dim parity As Integer = 0 ' use an Integer because they are faster
        For i = 0 To a.Length - 1
            parity = parity Xor parityLookup(a(i))
        Next

        Return parity

    End Function

    ' Method by Alireza
    Function ComputeParity(bytes() As Byte) As Byte
        Dim parity As Boolean = False
        For i As Integer = 0 To bytes.Length - 1
            Dim b As Byte = bytes(i)
            While b <> 0
                parity = Not parity
                b = CByte(b And (b - 1))
            End While
        Next
        Return Convert.ToByte(parity)
    End Function

    ' Method by dbasnett
    Function CountBits(byteArray As Byte()) As Integer
        Dim rv As Integer = 0
        For Each b As Byte In byteArray
            Dim count As Integer = b
            count = ((count >> 1) And &H55) + (count And &H55)
            count = ((count >> 2) And &H33) + (count And &H33)
            count = ((count >> 4) And &HF) + (count And &HF)
            rv += count
        Next
        Return rv
    End Function

    Sub FillWithRandomBytes(ByRef a() As Byte)
        rand.NextBytes(a)
    End Sub

    Sub Main()
        SetUpParityLookup()

        Dim nBytes = 10000
        Dim a(nBytes - 1) As Byte
        FillWithRandomBytes(a)

        Dim p As Integer

        Dim sw As New Stopwatch

        sw.Start()
        p = ParityOfArray(a)
        sw.Stop()

        Console.WriteLine("ParityOfArray - Parity: {0} Time: {1}", p, sw.ElapsedTicks)

        sw.Restart()
        p = ComputeParity(a)
        sw.Stop()

        Console.WriteLine("ComputeParity - Parity: {0} Time: {1}", p, sw.ElapsedTicks)

        sw.Restart()
        p = CountBits(a)
        sw.Stop()

        ' Note that the value returned from CountBits should be And-ed with 1.
        Console.WriteLine("CountBits     - Parity: {0} Time: {1}", p And 1, sw.ElapsedTicks)

        Console.ReadLine()

    End Sub

End Module

Typical ouput:

ParityOfArray - Parity: 0 Time: 386
ComputeParity - Parity: 0 Time: 1014
CountBits     - Parity: 0 Time: 695

Answer 2

An efficient way to do this is to use the x & (x - 1) operation in a loop, until x becomes zero. This way you will loop only by the number of bits set to 1.

In VB.NET for a byte array:

Function ComputeParity(bytes() As Byte) As Byte
    Dim parity As Boolean = False
    For i As Integer = 0 To bytes.Length - 1
        Dim b As Byte = bytes(i)
        While b <> 0
            parity = Not parity
            b = b And (b - 1)
        End While
    Next
    Return Convert.ToByte(parity)
End Function

Answer 3

Here is a function that counts bits.

Private Function CountBits(byteArray As Byte()) As Integer
    Dim rv As Integer = 0
    For x As Integer = 0 To byteArray.Length - 1
        Dim b As Byte = byteArray(x)
        Dim count As Integer = b
        count = ((count >> 1) And &H55) + (count And &H55)
        count = ((count >> 2) And &H33) + (count And &H33)
        count = ((count >> 4) And &HF) + (count And &HF)
        rv += count
    Next
    Return rv
End Function

Note: this code came from a collection of bit twiddling hacks I found some years ago. I converted it to VB.