Module: Simhilarity::Bits

Defined in:
lib/simhilarity/bits.rb

Constant Summary collapse

HAMMING8 = 
(0..0xff).map { |i| Bits.hamming(0, i) }
HAMMING16 = 
(0..0xffff).map { |i| HAMMING8[(i >> 8) & 0xff] + HAMMING8[(i >> 0) & 0xff] }

Class Method Summary collapse

Class Method Details

.hamming(a, b) ⇒ Object

Calculate the hamming distance between two integers. Not particularly fast.



8
9
10
11
12
13
14
15
 
# File 'lib/simhilarity/bits.rb', line 8

def self.hamming(a, b)
  x, d = 0, a ^ b
  while d > 0
    x += 1
    d &= d - 1
  end
  x
end

.hamming32(a, b) ⇒ Object

Calculate the hamming distance between two 32 bit integers using a lookup table. This is fast.



23
24
25
26
27
28
 
# File 'lib/simhilarity/bits.rb', line 23

def self.hamming32(a, b)
  x = a ^ b
  a = (x >> 16) & 0xffff
  b = (x >>  0) & 0xffff
  HAMMING16[a] + HAMMING16[b]
end