计算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中一个字节的奇偶校验位

回答

相关问题