popcount-fast.coffee

# https://blogs.msdn.microsoft.com/jeuge/2005/05/03/bit-fiddling-2/
fast = do ->
  t = [
    0
    1
    1,2
    1,2,2,3
    1,2,2,3,2,3,3,4
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7
    1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8
  ]
  (x) ->
    t[x       & 0xff] +
    t[x >> 8  & 0xff] +
    t[x >> 16 & 0xff] +
    t[x >> 24 & 0xff]

# https://blogs.msdn.microsoft.com/jeuge/2005/06/08/bit-fiddling-3/
# In JS this fails on sign bit; e.g. x > 0x7fffffff
parallel = (x) ->
  xc = x - (x >> 1 & 0xdb6db6db) - (x >> 2 & 0x49249249)
  ((xc + (xc >> 3)) & 0xc71c71c7) % 63