計算Ruby中一個字節的奇偶校驗位

在Ruby中計算一個字節是奇數還是偶數的最好方法是什麼？我有一個版本的工作：計算Ruby中一個字節的奇偶校驗位

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

轉換一個數字，字符串和計數的「1」看起來雖然計算奇偶校驗的好辦法。有更好的方法嗎？

我想能夠計算3DES密鑰的奇偶性。最後，我想要將偶數字節轉換爲奇數。

感謝，丹

來源

2010-12-19 dkam

Thanks @Phrogz - updated。用於基準的 – dkam 2011-01-03 04:58:41

除非你有足夠的速度，否則保留它。它清晰簡潔，其表現比您想象的要好。

我們將針對陣列查找基準的一切，最快的方法我測試：

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

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

陣列查找計算以每秒64萬個字節的速度奇偶校驗。
Bowsersenior的C代碼以每秒640,000字節的速率計算奇偶校驗。
您的代碼以每秒284,000字節的速率計算奇偶校驗。
Bowsersenior的本地代碼以每秒171,000字節的速率計算奇偶校驗。
Theo的縮短代碼以每秒128,000字節的速率計算奇偶校驗。

來源

2010-12-19 14:31:08

+1！ – 2010-12-19 20:33:43

+1好的基準。 – bowsersenior 2010-12-19 20:54:39

用於基準測試。 – EnabrenTane 2010-12-20 16:43:09

也許數組的255個條目的查詢表是最快的「在Ruby」的解決方案。

在C我會掩飾和轉移。或者如果我有SSE4，我會使用內嵌彙編器的POPCNT指令。如果你需要這樣的高性能，那麼在C語言中寫一個本地擴展就可以完成上面的任何一個。

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

來源

2010-12-19 07:00:09 EnabrenTane

你已經採取了看看RubyDES library？這可能不需要編寫自己的實現。

計算奇偶校驗，您可以使用類似以下內容：

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

根據簡單的基準測試，內嵌C版是3-4倍，比天然紅寶石版本

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

來源

2010-12-19 07:25:41 bowsersenior

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

快

可以縮短爲

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

如果你想要的東西是不可讀的☺

來源

2010-12-19 10:19:40 Theo

如何使用您的原始解決方案與memoization？這隻會爲每個整數值計算一次。

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? 
    [email protected]@parity[self] 
    end 
end 

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

來源

2010-12-19 17:22:38 Phrogz

我會構造一個16個條目（作爲16個字符表），對應於每個字節的半字節（一半）的單個表。條目是0,1,1,2,1,2，... 4

要測試字節，

屏蔽掉左邊四位，並做了查找，記憶的數量。做。向右移動4並進行第二次查找，將結果編號添加到前一個來提供總和。

然後測試總和的低位。如果它是1，則該字節是奇數，如果它是0，則該字節是偶數。如果結果是偶數，則使用異或指令翻轉高位。這種查找方法比通過單次移位將字節中的位加起來要快得多。

通過電子郵件給我一個簡單的函數來完成8字節的奇偶校驗。 3DES使用3組8個字節。

來源

2012-08-18 20:01:37

計算Ruby中一個字節的奇偶校驗位

回答

相關問題