Berechnen Sie die Parität eines Bytes in Ruby

Question

Was ist der beste Weg, zu berechnen, wenn ein Byte ungerade oder gerade Parität in Ruby hat? Ich habe eine Version Arbeits bekam:

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

eine Zahl in einen String konvertieren und die „1“ zu zählen scheint eine schlechte Art und Weise Parität der Berechnung though. Irgendwelche bessere Methoden?

Ich möchte die Parität eines 3DES Schlüssel berechnen können. Schließlich werde ich auch Bytes auf ungerade konvertieren möchten.

Danke, Dan

Answer 1

Es sei denn, was Sie haben nicht schnell genug ist, halten Sie es. Es ist klar und prägnant, und seine Leistung ist besser als Sie denken.

Wir werden Benchmark alles gegen Array-Lookup, die schnellste Methode, die ich getestet:

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

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

• Array-Lookup berechnet die Parität mit einer Rate von 640.000 Bytes pro Sekunde.
• Bowsersenior der C-Code berechnet Parität mit einer Rate von 640.000 Bytes pro Sekunde.
• Ihr Code berechnet Parität mit einer Rate von 284.000 Bytes pro Sekunde.
• Bowsersenior nativen Code berechnet Parität mit einer Rate von 171.000 Bytes pro Sekunde.
• Theos verkürzten Code berechnet Parität mit einer Rate von 128.000 Bytes pro Sekunde.

Answer 2

Haben Sie einen Blick auf die RubyDES Bibliothek ? Das kann die Notwendigkeit entfernen, um Ihre eigene Implementierung zu schreiben.

zu berechnen Parität, Sie so etwas wie die folgenden verwendet werden:

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

Nach einfacher Benchmarks, die Inline-c Version ist 3-4 mal schneller als die 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

Wahrscheinlich eine Lookup-Tabelle eines Array mit 255 Einträgen wäre schnellste "In Ruby" Lösung.

In C würde ich maskieren und Verschiebung. Oder wenn ich SSE4 Ich würde die POPCNT Anweisung mit Inline-Assembler verwenden. Wenn Sie diese in C Hochleistungsschreib eine native Erweiterung sein, die entweder von der obigen Fall ist.

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

Answer 4

Wie wäre Ihre ursprüngliche Lösung mit memoization mit? Dies wird nur einmal für jeden ganzzahligen Wert berechnen.

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

, die

kürzbar

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

Wenn Sie etwas, das nicht lesbar ist ?

Answer 6

I würde eine einzelne Tabelle von 16 Einträgen (als eine 16-Zeichentabelle) konstruieren, zu jedem Halbbyte (die Hälfte), entsprechend einer Byte. Einträge sind 0,1,1,2,1,2 .... 4

Ihr Byte testen,

Maske aus der linken knabbern und eine Lookup tun, die Zahl auswendig zu lernen. Tun. eine Verschiebung nach rechts um 4 und eine zweite Lookup, das Ergebnis Anzahl zum vorherigen eine Summe bereitzustellen hinzufügen.

testen Sie dann das niederwertige Bit aus der Summe. Wenn es 1 ist, ist das Byte ungerade ist, wenn es eine 0 ist, das Byte selbst ist. Wenn das Ergebnis gerade ist, können Sie die höherwertigen Bit-Flip, die xor Anweisung verwendet wird. Diese Suche Methode ist viel schneller als die Bits in einem Byte von einzelnen Schichten addieren.

E-Mail mich für eine einfache Funktion, um die Parität für 8 Bytes zu tun. 3DES verwendet 3 Gruppen von 8 Bytes.