Битовая манипуляция: определить, установлены ли как минимум 5 битов в байтах?

Question

Каков наилучший способ проверить, установлено ли минимальное количество бит в двоичном числе?

Например, мне нужно посмотреть, установлены ли хотя бы 5 битов в 1 в этой последовательности:

101100010

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

Любая помощь приветствуется.

Answer 1

С http://blog.faultylabs.com/2011.php?p=jsbitfun

/*
 popCnt(n)
 Returns the bit population count of n (that is: how many bits in n are set to 1)
 n must be an unsigned integer in the range [0..(2^32)-1]
 This lookup-table-free method is from Kernighan & Ritchie's "The C Programming Language"
 Exercise 2.9 (on page 62 of my copy). Not sure whether they (K&R) are the inventors.
*/
function popCnt(n) {
    n >>>= 0 /* force uint32 */
    for(var popcnt = 0; n; n &= n - 1) {
        popcnt++
    }
    return popcnt
}

См. http://en.wikipedia.org/wiki/Hamming_weight для получения подробной информации о других алгоритмах.

Answer 2

Если вы пытаетесь научиться работать с битами, поиграйтесь с битовыми масками.

Если вам нужно очень простое решение, просто преобразуйте целое число в строковое представление его двоичного значения и сосчитайте число 1:

var i = 0x1 +0x4 + 0x8 +0x80; // 10001101 in binary
var numberOf1s = i.toString(2).split('1').length-1; // 4

, так что для этого вам понадобится всего одна строка кода:

if(<insert your var>.toString(2).split('1').length-1 >=5) {
  //At least 5 bits are set
}

Answer 3

Сначала делайте это с битовыми масками, особенно если вы пытаетесь учиться.Это наиболее логически простой подход, если рассматривать его как последовательность битов.(Существует куча хитрых трюков, которые можно сделать, но сначала это первое, а с таким языком, как JS, с множеством движков, реализация может сделать умным, а не таким умным.)

Чтобы проверить, установлен ли бит b, он устанавливается, когда input & (1 << b) не равен 0, конечно 1 << b равно 00000001 (0x01), 00000010 (0x02), 00000100(0x04), 00001000 (0x08) и т. Д., Когда b равно 0, 1, 2, 3 и т. Д.(Примечание 1 равно 00000001 и как << перемещает шаблон влево на b бит).

Итак, для каждого 0 <= <code>b <8, см.бит установлен.Если это так, добавьте единицу к счетчику. </p>

Теперь мы знаем, сколько битов в первом октете установлено.

Также обратите внимание, что существует только небольшой конечный набор значений для b мы заботимся оТаким образом, мы можем исключить цикл и знать каждый 1 << b для каждой итерации цикла.(Некоторые браузеры, такие как Firefox, могут обрабатывать последовательность побитовых математических операций, таких как очень очень быстро при использовании одного выражения.)

Счастливое кодирование

---

Длявесело Я решил создать быстрый тестовый пример производительности popCnt (и strCount), как показано в других ответах, и специальный счетчик битов fastCount8, который использует только математические операции и не пытаетсябыть слишком умным и simpleCount8, как описано выше.

Разумеется, что оба fastCount8 (и simpleCount8) ограничены одним октетом (первым байтом), но для этого особенно case fastCount8 намного быстрее в определенных браузерах.(Это значительно быстрее в FF8, но лишь незначительно быстрее в IE9 и медленнее в Chrome 16.) Как и ожидалось, strCount значительно медленнее, чем popCnt и simpleCount8не намного лучше.

Вот jsperf test и fastCount8:

function fastCount8(n) {
    // >> has higher precedence than &
    return (n >> 0 & 1)
      + (n >> 1 & 1)
      + (n >> 2 & 1)
      + (n >> 3 & 1)
      + (n >> 4 & 1)
      + (n >> 5 & 1)
      + (n >> 6 & 1)
      + (n >> 7 & 1)
}

---

Обновлены тесты производительности для lookup8, lookupN (и некоторые варианты), fastCount8N и fastCount8N2.Результаты весьма впечатляющие: FF8 делает совершенно потрясающих математических оптимизаций, а другие браузеры (я тестировал) даже близко не следят за заданным выражением.Кроме того, другие результаты могут быть несколько удивительными и демонстрировать, как разные браузеры оптимизируют разные вещи ...

... в целом lookup8 и lookupN2b выглядят наиболее согласованново всех браузерах ... по крайней мере, с указанным диапазоном n.