Рассчитайте паритет байта в Ruby

Question

Как лучше всего рассчитать, есть ли у байта нечетное или даже паритет в Ruby? У меня работает версия:

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

Преобразование числа в строку и подсчет «1» S кажется плохим способом расчета паритета. Есть лучшие методы?

Я хочу иметь возможность рассчитать паритет ключа 3DES. В конце концов, я захочу конвертировать даже байтов в Odd.

Спасибо, Дэн

Answer 1

Если то, что у вас есть, недостаточно быстро, держите это. Это ясно и лаконично, и его производительность лучше, чем вы думаете.

Мы сравним все против массива, самый быстрый метод, который я проверил:

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

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

• Поиск массива вычисляет четность со скоростью 640 000 байтов в секунду.
• Код C Bowsersenior вычисляет паритет со скоростью 640 000 байтов в секунду.
• Ваш код вычисляет паритет со скоростью 284 000 байтов в секунду.
• Настоящий код Bowsersenior вычисляет паритет со скоростью 171 000 байтов в секунду.
• Укороченный код Тео вычисляет паритет со скоростью 128 000 байтов в секунду.

Answer 2

Вы посмотрели на Библиотека Rubydes? Это может устранить необходимость написать свою собственную реализацию.

Чтобы рассчитать паритет, вы можете использовать что -то вроде следующего:

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

Согласно простым тестам, версия Inline C в 3-4 раза быстрее, чем нативная версия Ruby

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

Вероятно, таблица поиска массива с 255 записями было бы самым быстрым «Рубинским» решением.

В CI замаскирует и сдвигается. Или, если у меня есть SSE4, я бы использовал инструкцию POPCNT с встроенным ассемблером. Если вам нужно, чтобы это было высокой производительности, напишите нативное расширение в C, которое делает любое из вышеперечисленного.

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

Answer 4

Как насчет использования вашего исходного решения с памятью? Это будет рассчитывать только один раз для каждого целочисленного значения.

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

который можно сократить до

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

Если вы хотите что -то нечитаемое ☺

Answer 6

Я бы построил одну таблицу из 16 записей (в виде 16 символов), соответствующей каждому шлам (половина) байтов. Записи 0,1,1,2,1,2, .... 4

Чтобы проверить свой байт,

Замаскируйте левый шляп и сделайте поиск, запомнив номер. Делать. Сдвиг вправо на 4 и сделайте второй поиск, добавив номер результата к предыдущему, чтобы предоставить сумму.

Затем протестируйте бит низкого порядка от суммы. Если это 1, байт нечетный, если он 0, байт равномерно. Если результат ровный, вы переворачиваете бит высокого порядка, используя инструкцию XOR. Этот метод поиска намного быстрее, чем с добавлением битов в байте по одному смену.

Напишите мне на простую функцию, чтобы сделать паритет на 8 байтов. 3des использует 3 группы по 8 байтов.