Calculate the parity of a byte in Ruby

Question

What's the best way to calculate if a byte has odd or even parity in Ruby? I've got a version working:

result = "AB".to_i(16).to_s(2).count('1').odd?
=> true

Converting a number to a string and counting the "1"s seems a poor way of calculating parity though. Any better methods?

I want to be able to calculate the parity of a 3DES key. Eventually, I'll want to convert even bytes to odd.

Thanks, Dan

Answer 1

Unless what you have is not fast enough, keep it. It's clear and succinct, and its performance is better than you think.

We'll benchmark everything against array lookup, the fastest method I tested:

ODD_PARITY = [
  false,
  true,
  true,
  ...
  true,
  false,
]

def odd_parity?(hex_string)
  ODD_PARITY[hex_string.to_i(16)]
end

• Array lookup computes the parity at a rate of 640,000 bytes per second.
• Bowsersenior's C code computes parity at a rate of 640,000 bytes per second.
• Your code computes parity at a rate of 284,000 bytes per second.
• Bowsersenior's native code computes parity at a rate of 171,000 bytes per second.
• Theo's shortened code computes parity at a rate of 128,000 bytes per second.

Answer 2

Have you taken a look at the RubyDES library? That may remove the need to write your own implementation.

To calculate parity, you can use something like the following:

require 'rubygems'
require 'inline'  # RubyInline (install with `gem install RubyInline`)

class Fixnum
  # native ruby version: simpler but slow
  # algorithm from: 
  #   http://graphics.stanford.edu/~seander/bithacks.html#ParityParallel      
  def parity_native
    (((self * 0x0101010101010101) & 0x8040201008040201) % 0x1FF) & 1
  end

  class << self
    # inline c version using RubyInline to create c extension
    # 4-5 times faster than native version
    # use as class method: 
    #   Fixnum.parity(0xAB)
    inline :C do |builder|
      builder.c <<-EOC
      int parity_c(int num) {  
        return (
            ((num * 0x0101010101010101ULL) & 0x8040201008040201ULL) % 0x1FF
          ) & 1;
      }
      EOC
    end
  end

  def parity
    self.class.parity_c(self)
  end

  def parity_odd?
    1 == parity
  end
  def parity_even?
    0 == parity
  end
end

0xAB.parity        # => 1 
0xAB.parity_odd?   # => true 
0xAB.parity_even?  # => false
(0xAB + 1).parity  # => 0

According to simple benchmarks, the inline c version is 3-4 times faster than the native ruby version

require 'benchmark'
n = 10000
Benchmark.bm do |x|
  x.report("inline c") do
    n.times do 
      (0..255).map{|num| num.parity}
    end
  end

  x.report("native ruby") do
    n.times do 
      (0..255).map{|num| num.parity_native}
    end
  end
end
# inline c     1.982326s
# native ruby  7.044330s

Answer 3

Probably a lookup table of an Array with 255 entries would be fastest "In Ruby" solution.

In C I would mask and shift. Or if I have SSE4 I would use the POPCNT instruction with inline assembler. If you need this to be high performance write a native extension in C which does either of the above.

http://en.wikipedia.org/wiki/SSE4

Answer 4

How about using your original solution with memoization? This will only calculate once for each integer value.

class Fixnum
  # Using a class variable for simplicity, and because subclasses of
  # Fixnum—while very uncommon—would likely want to share it. 
  @@parity = ::Hash.new{ |h,i| h[i] = i.to_s(2).count('1').odd? }
  def odd_parity?
    @@parity[self]
  end
  def even_parity?
    !@@parity[self]
  end
end

"AB".to_i(16).odd_parity?
#=> true

Answer 5

x = 'AB'.to_i(16)
p = 0
until x == 0
  p += x & 1
  x = x >> 1
end
puts p # => 5

which can be shortened to

x = 'AB'.to_i(16)
p = x & 1
p += x & 1 until (x >>= 1) == 0

if you want something that is unreadable ☺

Answer 6

I would construct a single table of 16 entries (as a 16 character table), corresponding to each nibble (half) of a bytes. Entries are 0,1,1,2,1,2,....4

To test your byte,

Mask out the left nibble and do a lookup, memorizing the number. Do. a shift to the right by 4 and do a second lookup, adding the result number to the previous one to provide a sum.

Then test the low order bit from the sum. If it is 1, the byte is odd, if it is a 0, the byte is even. If result is even, you flip the high order bit, using the xor instruction. THis lookup method is much faster than adding up the bits in a byte by single shifts.

email me for a simple function to do the parity for 8 bytes. 3DES uses 3 groups of 8 bytes.