Количество бит для представления числа - PullRequest
Новая
       42

Количество бит для представления числа

9 голосов
/ 21 июня 2010

Я пытаюсь написать функцию, которая возвращает число бит положительное целое число меньше, чем предел Javascript (2 ^ 53) -1.Однако он сталкивается с проблемами точности и хочет избежать больших целочисленных библиотек.

Метод 1: 

function bitSize(num)
{
return Math.floor( Math.log(num) / Math.log(2) ) + 1;
}

Pass: bitSize( Math.pow(2, 16) -1 ) = 16
Pass: bitSize( Math.pow(2, 16) ) = 17
Fail (Should be 48): bitSize( Math.pow(2, 48) -1 ) = 49 
Pass: bitSize( Math.pow(2, 48) ) = 49

Метод 2: 

function bitSize(num)
{
var count = 0;
while(num > 0)
{
    num = num >> 1;
    count++;
}
return count;
}

Pass: bitSize( Math.pow(2, 16) -1 ) = 16
Pass: bitSize( Math.pow(2, 16) ) = 17
Fail (Should be 48): bitSize( Math.pow(2, 48) -1 ) = 1
Fail (Should be 49): bitSize( Math.pow(2, 48) ) = 1

Оба метода не в состояниивопросы точности, я думаю.

Может кто-нибудь предложить альтернативный метод, который будет работать для чисел между 0 -> 2 ^ 53-1

Спасибо.

Ответы [ 5 ]

10 голосов
/ 21 июня 2010

Битовые операции будут надежно работать только в Javascript для «целых чисел» до 32 бит. Цитировать из Полная ссылка на номер JavaScript :

Побитовые операции - это что-то вроде хака в Javascript.Поскольку все числа в Javascript являются числами с плавающей запятой, а побитовые операторы работают только с целыми числами, Javascript немного скрывает магию, чтобы казалось, что побитовые операции применяются к 32-битному целому числу со знаком.

В частности, Javascript принимаетчисло, над которым вы работаете, и занимает целую часть числа.Затем он преобразует целое число в наибольшее количество бит, которое представляет это число, до 31 бита (1 бит для знака).Таким образом, 0 создаст двухбитное число (1 для знака и 1 бит для 0), аналогично 1 создаст два бита.2 создаст 3-битное число, 4 создаст 4-битное число и т. Д. *

Важно понимать, что вам не гарантируется 32-битное число, например, если вы работаете не с нуля, теоретически следует преобразоватьОт 0 до 4 294 967 295, вместо этого он вернет -1 по двум причинам. Первая состоит в том, что все числа подписаны в Javascript, поэтому «not» всегда меняет знак, а второй Javascript не может сделать больше одного бита из числа ноль и неноль становится единым.Следовательно, ~ 0 = -1.

Таким образом, побитовые знаки в Javascript имеют длину до 32 бит.

Как отмечает Анураг, вы должны просто использовать встроенный num.toString(2) в этомвместо этого ситуация, которая выводит строку минимальной длины ASCII '1' с и '0' с, которую вы можете просто взять длиной.

9 голосов
/ 21 июня 2010

Вы можете сделать: 

function bitSize(num) {
    return num.toString(2).length;
}

Метод toString() для Number принимает основание в качестве необязательного аргумента.

Вот некоторые тесты . Работает на Chrome, Safari, Opera и Firefox. Нет доступа к IE, извините.

2 голосов
/ 20 апреля 2016

Стандарт ES6 приносит Math.clz32(), поэтому для чисел в диапазоне 32 бита вы можете написать: 

num_bits = 32 - Math.clz32(0b1000000);

Проверьте это в этом фрагменте: 

var input = document.querySelector('input');
var bits = document.querySelector('#bits');

input.oninput = function() {
    var num = parseInt(input.value);
    bits.textContent = 32 - Math.clz32(num);
};
Number (Decimal): <input type="text"><br>
Number of bits: <span id="bits"></span>

При MDN документации Math.clz32 предоставляется поли-заполнение: 

Math.imul = Math.imul || function(a, b) {
  var ah = (a >>> 16) & 0xffff;
  var al = a & 0xffff;
  var bh = (b >>> 16) & 0xffff;
  var bl = b & 0xffff;
  // the shift by 0 fixes the sign on the high part
  // the final |0 converts the unsigned value into a signed value
  return ((al * bl) + (((ah * bl + al * bh) << 16) >>> 0)|0);
};

Math.clz32 = Math.clz32 || (function () {
  'use strict';

  var table = [
    32, 31,  0, 16,  0, 30,  3,  0, 15,  0,  0,  0, 29, 10,  2,  0,
     0,  0, 12, 14, 21,  0, 19,  0,  0, 28,  0, 25,  0,  9,  1,  0,
    17,  0,  4,   ,  0,  0, 11,  0, 13, 22, 20,  0, 26,  0,  0, 18,
     5,  0,  0, 23,  0, 27,  0,  6,  0, 24,  7,  0,  8,  0,  0,  0]

  // Adapted from an algorithm in Hacker's Delight, page 103.
  return function (x) {
    // Note that the variables may not necessarily be the same.

    // 1. Let n = ToUint32(x).
    var v = Number(x) >>> 0

    // 2. Let p be the number of leading zero bits in the 32-bit binary representation of n.
    v |= v >>> 1
    v |= v >>> 2
    v |= v >>> 4
    v |= v >>> 8
    v |= v >>> 16
    v = table[Math.imul(v, 0x06EB14F9) >>> 26]

    // Return p.
    return v
  }
})();

document.body.textContent = 32 - Math.clz32(0b1000000);
1 голос
/ 28 мая 2016

Поздно до вечеринки, но я хочу дополнить 32-битный ответ Trincot более быстрым, простым и лучше поддерживаемым полным 53-битным методом.

Следующие 2 примера будут просто читать / анализировать и возвращать значение экспоненты с плавающей точкой.

Для современных браузеров, которые поддерживают ES6 ArrayBuffer и DataView (не заботится о порядковости платформы , но с меньшей унаследованной совместимостью): 

reqBits4Int = (function(d){ 'use strict';
  return function(n){
    return n && (                         // return 0 if n===0 (instead of 1)
      d.setFloat64(0, n),                 // OR set float to buffer and
      d.getUint16(0) - 16352 >> 4 & 2047  // return float's parsed exponent
    );                                    // Offset 1022<<4=16352; 0b1111111=2047
  };                                      // DataView methods default to big-endian
})( new DataView(new ArrayBuffer(8)) );   // Pass a Buffer's DataView to IFFE


Пример для чуть более старых браузеров, которые поддерживают Float64Array и Uint16Array (но не DataView, так что порядок байтов зависит от платформы, и этот фрагмент предполагает использование «стандартного» мало обратный порядок байт): 

reqBits4Int = (function(){ 'use strict';
  var f = new Float64Array(1),            // one 8-byte element (64bits)
      w = new Uint16Array(f.buffer, 6);   // one 2-byte element (start at byte 6)
  return function(n){ 
    return ( f[0] = n                     // update float array buffer element
                                          // and return 0 if n===0 (instead of 1)
           ) && w[0] - 16352 >> 4 & 2047; // or return float's parsed exponent
  };  //NOTE : assumes little-endian platform
})(); //end IIFE


Обе версии выше возвращают положительное целое число Number, представляющее максимум битов, необходимых для хранения целого числа Number, которое было передано в качестве аргумента.
Они работают без ошибок во всем диапазоне [-2 53 , 2 53 ] и выше, охватывая полный диапазон значений с плавающей запятой положительных показателей с плавающей запятой за исключением , где на входе уже произошло округление Number (например, 2 55 -1) равно , сохранено как 2 55 (что очевидно, что делает равным 56 битам).

Объяснение формата IEEE 754 на самом деле выходит за рамки этого ответа, но для тех, у кого есть базовое понимание, я включил свернутый фрагмент ниже, который содержит вычисление в форме таблицы, из которого можно увидеть / объяснить логику фактически мы просто берем первое слово с плавающей точкой (16 старших разрядов, содержащие знак и полный показатель степени), вычитаем смещение на 4 бита и смещение нуля (сохраняя нам 2 операции), сдвиг и результат маски в качестве вывода. 0 позаботится в функции. 

<xmp> PREVIEW of data to be generated: 

Float value :  S_exponent__MMMM :  # -(1022<<4)#### :  #   >> 4     :    & 2047    : Result integer
         -9 :  1100000000100010 :  1000000001000010 :  100000000100 :          100 :     4
         -8 :  1100000000100000 :  1000000001000000 :  100000000100 :          100 :     4
         -7 :  1100000000011100 :  1000000000111100 :  100000000011 :           11 :     3
         -6 :  1100000000011000 :  1000000000111000 :  100000000011 :           11 :     3
         -5 :  1100000000010100 :  1000000000110100 :  100000000011 :           11 :     3
         -4 :  1100000000010000 :  1000000000110000 :  100000000011 :           11 :     3
         -3 :  1100000000001000 :  1000000000101000 :  100000000010 :           10 :     2
         -2 :  1100000000000000 :  1000000000100000 :  100000000010 :           10 :     2
         -1 :  1011111111110000 :  1000000000010000 :  100000000001 :            1 :     1
          0 :                 0 :   -11111111100000 :   -1111111110 :  10000000010 :  1026
          1 :    11111111110000 :             10000 :             1 :            1 :     1
          2 :   100000000000000 :            100000 :            10 :           10 :     2
          3 :   100000000001000 :            101000 :            10 :           10 :     2
          4 :   100000000010000 :            110000 :            11 :           11 :     3
          5 :   100000000010100 :            110100 :            11 :           11 :     3
          6 :   100000000011000 :            111000 :            11 :           11 :     3
          7 :   100000000011100 :            111100 :            11 :           11 :     3
          8 :   100000000100000 :           1000000 :           100 :          100 :     4
          9 :   100000000100010 :           1000010 :           100 :          100 :     4

after 18 the generated list will only show 3 values before and after the exponent change
</xmp>

<script> //requires dataview, if not available see post how to rewrite or just examine example above
firstFloatWord = (function(d){ 
  return function(n){
    return d.setFloat64(0, n), d.getUint16(0);
  };
})( new DataView(new ArrayBuffer(8)) );

function pad(v, p){
  return ('                    '+v).slice(-p);
}

for( var r= '',   i=-18, c=0, t
   ; i < 18014398509481984
   ; i= i>17 && c>=5
      ? (r+='\n', c=0, (i-2)*2-3)
      : (++c, i+1) 
   ){
  r+= pad(i, 19) + ' : '   
    + pad((t=firstFloatWord(i)).toString(2), 17) + ' : '
    + pad((t-=16352).toString(2), 17) + ' : '
    + pad((t>>=4).toString(2), 13) + ' : '
    + pad((t&=2047).toString(2), 12) + ' : '
    + pad(t, 5) + '\n';
}

document.body.innerHTML='<xmp>        Float value :  S_exponent__MMMM :  # -(1022<<4)#### : '
                       + ' #   >> 4     :    & 2047    : Result integer\n' + r + '</xmp>';
</script>

Варианты отката:

ECMAScript (javascript) позволяет разработчикам свободно выбирать, как реализовать язык. Таким образом, в мире дикого x-браузера нужно иметь дело не только с различиями округления, но и с различными алгоритмами, такими как, например, Math.log и Math.log2 и т. Д.
Как вы уже заметили (ваш метод 1), распространенный пример, где log2 (polyfill) может не работать, равен 2 48 (= 49, то есть один к большому, когда загружен), но это не единственный пример.
Некоторые версии Chrome, например, даже испортили значительно меньшие числа, такие как: Math.log2(8) = 2.9999999999999996 (от одного до меньшего, когда настил).
Узнайте больше об этом в этом стеке потока Q / A: Точность Math.log2 в Chrome .
изменилась Это означает, что мы не можем знать, когда подвести или потолковать наш логарифмический результат (или легко предсказать, когда мы уже один раз за до округления).

Таким образом, вы можете посчитать, как часто вы можете разделить входное число на 2, прежде чем оно станет меньше 1 в цикле (очень похоже на ваш подсчитанный 32-битный метод сдвига 2): 

function reqBits4Int(n){ for(var c=0; n>=1; ++c, n/=2); return c }

Но это довольно грубая сила (и может также привести к проблемам с округлением). Вы можете улучшить это, используя некоторое разделение и завоевание, и пока вы это делаете, разверните цикл: 

function reqBits4Int(n){ 'use strict';
  var r= 4294967295 < n  ? ( n= n/4294967296 >>>   0,      32 ) : 0 ;
              65535 < n && (               n >>>= 16,  r+= 16 );
                255 < n && (               n  >>=  8,  r+=  8 );
                 15 < n && (               n  >>=  4,  r+=  4 );
  //              3 < n && (               n  >>=  2,  r+=  2 ); 
  //              1 < n && (               n  >>=  1,  r+=  1 ); 
  // return r + n;

  // OR using a lookup number instead of the lines comented out above
  // position: 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0  = 16 values
  //   binary: 11 11 11 11 11 11 11 11 10 10 10 10 01 01 00 00  = 4294945360 dec

  return (n && (4294945360 >>> n * 2 & 3) + 1) + r;
}

Форматирование предназначено, чтобы помочь понять алгоритм. Это минимизирует довольно круто!
Это имеет положительный целочисленный диапазон [0, 2 53 ] без ошибки (и до 2 64 с таким же предсказуемым округлением-'ошибкой').

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

Самым простым и коротким (но потенциально более медленным, по сравнению с приведенным выше фрагментом расчета) является строковое вычисление числа и подсчет итоговой длины строки, как в ответе Анурага, по существу: return n && n.toString(2).length; (в предположении браузеров) может дать результат до (как минимум) 53 бит).

1 голос
/ 21 июня 2010

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

...