Эффективно подсчитывать количество бит в целочисленном выражении в JavaScript

Скажем, у меня есть целое число я и хочу получить счет 1s в его двоичной форме.

В настоящее время я использую следующий код.

Number(i.toString(2).split("").sort().join("")).toString().length;

Есть ли более быстрый способ сделать это? Я думаю об использовании побитовых операторов. Любые мысли?

ПРИМЕЧАНИЕ. i находится в пределах 32-разрядного ограничения.

Ответы

Ответ 1

Вы можете использовать стратегию из этой коллекции Bit Twiddling Hacks:

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

console.log(bitCount(0xFF)) //=> 8

Ответ 2

Очень хороший, но медленный рекурсивный способ:

    function count1(n, accumulator=0) {
      if (n === 0) {
        return accumulator
      }
      return count1(n/2, accumulator+(n&1))
    }

console.log(count1(Number.MAX_SAFE_INTEGER));

Ответ 3

Ниже работает отлично с любым числом:

var i=8823475632,count=0;while (i=Math.floor(i)) i&1?count++:0,i/=2
console.log(count); //17

Ответ 4

Делая n = n & (n - 1) вы удаляете последний 1 бит в номере. В соответствии с этим вы можете использовать следующий алгоритм:

function getBitCount(n) {
  var tmp = n;
  var count = 0;
  while (tmp > 0) {
    tmp = tmp & (tmp - 1);
    count++;
  }
  return count;
}

console.log(getBitCount(Math.pow(2, 10) -1));

Ответ 5

Учитывая, что вы создаете, сортируете и присоединяете массив, если он буквально быстрее вы хотите, вам, вероятно, лучше делать это скучно:

console.log(countOnes(8823475632));

function countOnes(i) {
  var str = i.toString(2);
  var n;
  var count = 0;
  for (n = 0; n < str.length; ++n) {
    if (str[n] === "1") {
      ++count;
    }
  }
  return count;
}

Ответ 6

Вы можете пропустить Number, sort и второй toString. Используйте filter, чтобы рассмотреть только 1 (истинное значение) в массиве, а затем получить, сколько из них прошли через length.

i.toString(2).split('').filter(v => +v).length