JavaScript: заметка о побитовых операторах и числах с плавающей точкой

[lexasss]

console.log(isPositive(-3000000000)) // true

console.log(isPositive(3000000000)) // false

В TS лучше сразу так:

type Bit = 0 | 1;

function updateBit(n: number, bitPosition: number, bitValue: Bit): number { }

[aio350]

Побитовые операторы манипулируют 32-битными целыми числами от -2_147_483_647 до 2_147_483_647 включительно. С большими/меньшими значениями (например, 3_000_000_000) они работают некорректно. По поводу TS согласен.

[speshuric]

Функция определения количества установленных битов

Кроме простого "просдвигивания" числа вправо есть как минимум 2 других подхода: алгоритм Брайана Кернигана и параллельное суммирование через маску и сдвиг.

Алгоритм Кернигана базируется на том, что n&(n-1) очищает верхний бит (в статьеэто использовано в "является ли число степенью числа 2"). Его выгодно использовать, если известно, что чаще установлено мало битов. Что-то типа

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

Источник (если честно, лень искать и проверять - кидаю первый попавшийся похожий на правильный код)

Параллельное суммирование через маску и сдвиг чуть мудрёнее, но оно не содержит циклов и требует меньше операций в худшем случае. Подробно описано тут, тут и тут. На C наиболее понятно можно идею выразить так:

int count_one(int x){
    x = (x & (0x55555555)) + ((x >> 1) & (0x55555555));
    x = (x & (0x33333333)) + ((x >> 2) & (0x33333333));
    x = (x & (0x0f0f0f0f)) + ((x >> 4) & (0x0f0f0f0f));
    x = (x & (0x00ff00ff)) + ((x >> 8) & (0x00ff00ff));
    x = (x & (0x0000ffff)) + ((x >> 16) & (0x0000ffff));
    return x;
}

Но это можно немного улучшить, что обсуждается в том числе по ссылкам выше. В реальных JS движках не тестировал скорость, но на платформах без инструкции popcnt такие штуки применяются и в напрямую компилируемых языках.

Идейно близкие хаки есть и для "Функция определения количества битов"

[faultedChip]

Алгоритм Кернигана базируется на том, что n&(n-1) очищает верхний бит

Либо я не понимаю терминологию, либо очищает он всё-же самый нижний бит (т.е. самый правый установленный бит).

[speshuric]

Это опечатка, да, нижний, конечно.