Как получить длину в битах 32-битного целого - PullRequest
Новая
       30

Как получить длину в битах 32-битного целого

0 голосов
/ 17 февраля 2019

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

assert(countIntegerBits(4), 3) // 100
assert(countIntegerBits(8), 4) // 1000
assert(countIntegerBits(20), 5) // 10100
assert(countIntegerBits(100), 7) // 1100100

// https://stackoverflow.com/questions/43122082/efficiently-count-the-number-of-bits-in-an-integer-in-javascript
function countIntegerBits(integer) {
  var length = 0

  while (integer = Math.floor(integer)) {
    if (integer & 1) {
      length++
    }

    integer /= 2
  }

  return length
}

function countIntegerBits(integer) {
  // var length = 0
  // while (integer !== 0) {
  //   length += countIntegerBits32(integer | 0)
  //   integer /= 0x100000000
  // }
  // return length
  //
  // or perhaps this:
  // https://gist.github.com/everget/320499f197bc27901b90847bf9159164#counting-bits-in-a-32-bit-integer
}

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

function countStringBits(string) {
  // looks like this / 8 would be good enough
  // https://codereview.stackexchange.com/questions/37512/count-byte-length-of-string
  var length = 0;
  for (var i = 0; i < normal_val.length; i++) {
    var c = normal_val.charCodeAt(i);
    length += c < (1 <<  7) ? 1 :
               c < (1 << 11) ? 2 :
               c < (1 << 16) ? 3 :
               c < (1 << 21) ? 4 :
               c < (1 << 26) ? 5 :
               c < (1 << 31) ? 6 : Number.NaN
  }
  return length;
}

function countFloatBits(float) {
  // looks too complicated for an SO question
  // http://binary-system.base-conversion.ro/real-number-converted-from-decimal-system-to-32bit-single-precision-IEEE754-binary-floating-point.php?decimal_number_base_ten=1.23&sign=0&exponent=01111111&mantissa=00111010111000010100011
}

function assert(a, b) {
  if (a !== b) throw new Error(a + ' != ' + b)
}

Чего я хочу избежать, так это хака с преобразованием в строку 

var length = integer.toString(2).split('').length

Единственное, что я могу подумать - это проверьте, установлен ли бит , пока не дойдете до первого 1, затем начните отсчет оттуда. 

assert(countIntegerBits(4), 3) // 100
assert(countIntegerBits(8), 4) // 1000
assert(countIntegerBits(20), 5) // 10100
assert(countIntegerBits(100), 7) // 1100100

function countIntegerBits(integer) {
  var i = 0
  while (true) {
    if (integer & (1 << i)) {
      return 31 - i
    }

    i++
  }
}

function assert(a, b) {
  if (a !== b) throw new Error(a + ' != ' + b)
}

Но это не совсем верно, потому что я не уверен, что все целые числа представлены как 32-битные под капотом, например, (4).toString(2) дает "100", а не 00000000000000000000000000000100, поэтому не уверен.

Там я изучил, как проверить длину строки в битах, и то же самое с помощью чисел с плавающей запятой, но в то время как строки кажутся простыми, если это кодировка utf-8Кажется, что float - это большая вещь, поэтому мой вопрос касается только целых чисел вплоть до максимума, который поддерживает JavaScript.Для всех практических целей на данный момент я буду рассматривать только целые числа примерно до 1 миллиарда, поэтому для него не нужно учитывать 123e456 bigints или что-то еще, только цифры до нескольких миллиардов или до базовыхМакс. 32-разрядное целое число в JavaScript.

1 Ответ

0 голосов
/ 17 февраля 2019

Существует связь между натуральным логом (ну, лог на любую базу) и логом на другую базу.Для получения журнала базы-2: 

const log2 = n => Math.log(n) / Math.log(2);

Вы хотите округлить после добавления 1: 

const bits = n => Math.floor(log2(n) + 1);
...