Статьи

Целые числа и операторы сдвига в JavaScript


JavaScript имеет только числа с плавающей точкой.
Этот пост объясняет, как обрабатываются целочисленные операции, в частности операции битового сдвига. Это также ответит на вопрос, является ли n >>> 0 хорошим способом преобразования числа в неотрицательное целое число.

Препараты

Поскольку мы будем часто рассматривать двоичные числа, мы определим следующие методы, чтобы помочь нам:

    String.prototype.bin = function () {
        return parseInt(this, 2);
    };
    Number.prototype.bin = function () {
        var sign = (this < 0 ? "-" : "");
        var result = Math.abs(this).toString(2);
        while(result.length < 32) {
            result = "0" + result;
        }
        return sign + result;
    }

The methods in use:

    > "110".bin()
    6
    > 6..bin()
    '00000000000000000000000000000110'

Целые числа в JavaScript

Все целочисленные операции (такие как любые виды побитовых манипуляций) следуют одному и тому же шаблону: преобразуйте операнды в числа с плавающей запятой, затем в целые числа; выполнить вычисления; преобразовать целочисленный результат обратно в число с плавающей запятой. Есть четыре целочисленных типа, используемых внутри:

  • Целое число: значение в диапазоне [−2 53 , +2 53 ]. Используется для: большинства целочисленных аргументов (индексы, даты и т. Д.).
  • Uint16: 16-разрядные целые числа без знака в диапазоне [0, 2 16 −1]. Используется для: кодов символов.
  • Uint32: 32-разрядные целые числа без знака в диапазоне [0, 2 32 −1]. Используется для: длины массива.
  • Int32: 32-разрядные целые числа со знаком в диапазоне [−2 31 , 2 31 −1]. Используется для: побитового нет, двоичных побитовых операторов, беззнакового сдвига.

Преобразование чисел в целое число

Число
n преобразуется в целое число по следующей формуле:


знак (
n ) ⋅ этаж (абс (
n ))

Интуитивно, каждый удаляет все десятичные дроби. Трюк со знаком и abs необходим, потому что floor преобразует число с плавающей запятой в следующее
нижнее целое число:

    > Math.floor(3.2)
    3
    > Math.floor(-3.2)
    -4

Преобразование в целое число может быть реализовано без функции знака следующим образом:

function ToInteger(x) {
        x = Number(x);
        return x < 0 ? Math.ceil(x) : Math.floor(x);
    }

Мы отклоняемся от обычной практики, позволяющей функциям (не являющимся конструкторами) начинаться со строчной буквы, чтобы соответствовать именам, используемым в спецификации ECMAScript 5.1.

Преобразование чисел в Uint32

В качестве первого шага преобразуйте число в целое число. Если это в пределах диапазона Uint32, мы сделали. Если это не так (например, потому что это отрицательно), то мы применяем к нему модуль 2
32 . Обратите внимание, что в отличие от оператора остатка JavaScript в%, результат оператора по модулю имеет знак второго операнда. Следовательно, модуль 2
32 всегда положителен. Интуитивно, каждый добавляет или вычитает 2
32, пока число не окажется в диапазоне [0, 2
32 -1]. Ниже приведена реализация ToUint32.

function modulo(a, b) {
        return a - Math.floor(a/b)*b;
    }
    function ToUint32(x) {
        return modulo(ToInteger(x), Math.pow(2, 32));
    }

 
Операция по модулю становится очевидной при числах, близких к целому числу, кратному 2 32 .

    > ToUint32(Math.pow(2,32))
    0
    > ToUint32(Math.pow(2,32)+1)
    1

    > ToUint32(-Math.pow(2,32))
    0
    > ToUint32(-Math.pow(2,32)-1)
    4294967295
    
    > ToUint32(-1)
    4294967295

Результат преобразования отрицательного числа имеет больше смысла, если мы посмотрим на его двоичное представление. Чтобы отменить двоичное число, вы инвертируете каждую из его цифр, а затем добавляете одну. Инверсия называется
дополнением к одному, добавление одного превращает его в дополнение к
двум . Иллюстрируя процесс с 4 цифрами:

    0001   1
    1110   ones’ complement of 1
    1111   −1, twos’ complement of 1
   10000   −1 + 1

Последняя строка объясняет, почему дополнение двойки действительно является отрицательным числом, если цифры фиксированы: результат добавления 1 к 1111 равен 0, игнорируя пятую цифру. ToUint32 создает дополнение для 32 битов:

    > ToUint32(-1).bin()
    '11111111111111111111111111111111'

Преобразование чисел в Int32

Чтобы преобразовать число в Int32, сначала нужно преобразовать его в Uint32. Если установлен его старший бит (если он больше или равен 2 31 ), то 2 32 вычитается, чтобы превратить его в отрицательное число (2 32 равно 4294967295 + 1).

    function ToInt32(x) {
        var uint32 = ToUint32(x);
        if (uint32 >= Math.pow(2, 31)) {
            return uint32 - Math.pow(2, 32)
        } else {
            return uint32;
        }
    }

Полученные результаты:

    > ToInt32(-1)
    -1
    > ToInt32(4294967295)
    -1

Операторы сдвига

В JavaScript есть три оператора сдвига:

  • Подпись сдвиг влево <<
  • Подпись вправо >>
  • Сдвиг без знака вправо >>>

Подпись вправо сдвиг

Сдвиги вправо со знаком х совпадают с делением на 2 ^ х.

    > -4 >> 1
    -2
    > 4 >> 1
    2

На двоичном уровне мы видим, как цифры сдвигаются вправо, в то время как старшая цифра остается неизменной.

    > ("10000000000000000000000000000010".bin() >> 1).bin()
    '11000000000000000000000000000001'

Беззнаковое смещение вправо

Беззнаковое смещение вправо просто: просто сдвиньте биты, смещаясь по нулям слева.

    > ("10000000000000000000000000000010".bin() >>> 1).bin()
    '01000000000000000000000000000001'

Знак не сохраняется, результатом всегда является Uint32:

    > -4 >>> 1
    2147483646

Сдвиг влево

Сдвиг влево на x цифр такой же, как умножение на 2 ^ x.

    > 4 << 1
    8
    > -4 << 1
    -8

Для сдвигов влево операции со знаком и без знака неразличимы.

    > ("10000000000000000000000000000010".bin() << 1).bin()
    '00000000000000000000000000000100'

Чтобы понять почему, мы снова обратимся к 4-значным двоичным числам и однозначным сдвигам. Сдвиг влево со знаком означает, что если наибольшая цифра равна 1 до сдвига, она также равна 1 после сдвига. Если бы было число, в котором мы могли бы наблюдать разницу между знаковыми и беззнаковыми левыми сдвигами, то его вторая по величине цифра должна была бы быть 0 (в противном случае самая высокая цифра была бы 1 в любом случае). То есть это должно было бы выглядеть так:

    10__

Результат беззнакового левого сдвига 0__0. Для сдвига со знаком на одну цифру мы предположили бы, что он пытался сохранить отрицательный знак и, таким образом, оставил самую высокую цифру в 1. Учитывая, что такой сдвиг должен быть умножением на 2, мы не сможем привести пример сдвига 1001 (- 7) до 1010 (−6).

Другой способ взглянуть на это состоит в том, что для отрицательных чисел самая высокая цифра равна 1. Чем меньше оставшихся цифр, тем меньше число. Например, самое низкое 4-значное отрицательное число

    1000   (−8, the twos’ complement of itself)

Любое число 10__ равно -5 или ниже (-5, -6, -7, -8). Но умножение одного из этих чисел на 2 выведет его за пределы диапазона. Поэтому подписанный сдвиг не имеет смысла.

Альтернативные реализации ToUint32 и ToInt32

Смены без знака конвертируют свою левую сторону в Uint32, а смены со знаком конвертируют в Int32. Сдвиг на 0 цифр возвращает преобразованное значение.

function ToUint32(x) {
        return x >>> 0;
    }
    function ToInt32(x) {
        return x >> 0;
    }

Уроки выучены

Вам когда-нибудь понадобится выполнить одно из трех преобразований ToInteger, ToUint32, ToInt32, показанных здесь? Из трех только ToInteger полезен для обычных приложений. Но у вас есть другие варианты для преобразования в целое число:

  • Math.floor () преобразует свой аргумент в ближайшее нижнее целое число.
        > Math.floor(3.8)
        3
        > Math.floor(-3.8)
        -4
    
  • Math.ceil () преобразует свой аргумент в ближайшее ближайшее целое число.
        > Math.ceil(3.2)
        4
        > Math.ceil(-3.2)
        -3
    
  • Math.round () преобразует свой аргумент в ближайшее целое число. Примеры:
        > Math.round(3.2)
        3
        > Math.round(3.5)
        4
        > Math.round(3.8)
        4
    

    Результат округления -3,5 немного неожиданный.

        > Math.round(-3.2)
        -3
        > Math.round(-3.5)
        -3
        > Math.round(-3.8)
        -4
    

    Поэтому Math.round (x) такой же, как

        Math.ceil(x + 0.5)
    

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

Операции по модулю, выполняемые ToUint32 и ToInt32, редко бывают полезными на практике. Следующий эквивалент ToUint32 иногда используется для преобразования любого значения в неотрицательное целое число.

    value >>> 0

Это много магии для одного выражения! Обычно лучше разделить это на несколько утверждений или выражений. Вы можете даже вызвать исключение, если значение меньше 0 или не число. Это также позволило бы избежать некоторых из более неожиданных результатов оператора >>>:

    > -1 >>> 0
    4294967295