Как сделать popcount или считать биты на произвольно длинной битовой последовательности в JavaScript

Question

Похоже, что это хорошо работает с целыми числами, которые находятся в пределах максимального целочисленного размера в JavaScript:

function bitCount (n) {
  var bits = 0
  while (n !== 0) {
    bits += bitCount32(n | 0)
    n /= 0x100000000
  }
  return bits
}

function bitCount32 (n) {
  n = n - ((n >> 1) & 0x55555555)
  n = (n & 0x33333333) + ((n >> 2) & 0x33333333)
  return ((n + (n >> 4) & 0xF0F0F0F) * 0x1010101) >> 24
}

Мне интересно, как вообще считать биты в потоке битов любого размера, эффективно, в идеалебез преобразования в строку.

Answer 1

Если вы знаете, что ваш буфер будет иметь длину, кратную 4,

let array32 = new Uint32Array(buffer);
let numBits = array32.reduce((a, e) => a + bitCount32(e), 0);

В противном случае, вероятно, предложение tevemadar лучше, используйте Uint8Array и считайте биты в байте, а не в слове.

Answer 2

Комментарий с таблицей поиска, примерно:

var lookup=new Uint8Array(256);
for(var i=0;i<256;i++){
  var c=0;
  for(var j=i;j;j>>=1)
    if(j&1)c++;
  lookup[i]=c;
}
function count(arr){
  var arr8=new Uint8Array(arr);
  return arr8.reduce((a,e)=>a+lookup[e],0);
}

console.log(count(new Uint8Array([0x12,0x34,0x56,0x78,0x9A,0xBC,0xDE,0xF])));
                                  //11   21   22   31   22   32   33   4 = 32

Конечно, поколение таблиц может использовать и вашу магию.