Эффективное получение старшего и младшего бита в javascript - PullRequest
Новая
       66

Эффективное получение старшего и младшего бита в javascript

1 голос
/ 29 мая 2020

В виде 64-битного целого числа. Я пытаюсь получить индекс крайнего левого ненулевого бита. Я использовал наивный метод перебора всех 64 бита, чтобы вычислить это. 

function getLowestBitPosition(bitstring) {
    for (a = 0; a < bitstring.length; a++) if (bitstring[a] === "1") return a; 
}

Точно так же я повторил итерацию в обратном направлении, чтобы получить индекс крайнего правого ненулевого бита. Я почти уверен, что есть более эффективный способ реализовать это. Я видел методы в C, требующие небольшой итерации. Однако во всех этих примерах используются C библиотечные функции. Есть ли лучший способ получить индекс в javascript?

Ответы [ 3 ]

2 голосов
/ 29 мая 2020

Портировано / адаптировано из этого ответа , это хороший, не требующий строк, l oop и условно свободный способ получения позиции MSB или LSB из BigInt. 

const deBruijn = [0, 48, -1, -1, 31, -1, 15, 51, -1, 63, 5, -1, -1, -1, 19, -1, 23, 28, -1, -1, -1, 40, 36, 46, -1, 13, -1, -1, -1, 34, -1, 58, -1, 60, 2, 43, 55, -1, -1, -1, 50, 62, 4, -1, 18, 27, -1, 39, 45, -1, -1, 33, 57, -1, 1, 54, -1, 49, -1, 17, -1, -1, 32, -1, 53, -1, 16, -1, -1, 52, -1, -1, -1, 64, 6, 7, 8, -1, 9, -1, -1, -1, 20, 10, -1, -1, 24, -1, 29, -1, -1, 21, -1, 11, -1, -1, 41, -1, 25, 37, -1, 47, -1, 30, 14, -1, -1, -1, -1, 22, -1, -1, 35, 12, -1, -1, -1, 59, 42, -1, -1, 61, 3, 26, 38, 44, -1, 56];
const multiplicator = BigInt("0x6c04f118e9966f6b");

const
  b1 = BigInt(1),
  b2 = BigInt(2),
  b4 = BigInt(4),
  b8 = BigInt(8),
  b16 = BigInt(16),
  b32 = BigInt(32),
  b57 = BigInt(57);

function msb(v) {
  v |= v >> b1;
  v |= v >> b2;
  v |= v >> b4;
  v |= v >> b8;
  v |= v >> b16;
  v |= v >> b32;
  return deBruijn[
    BigInt.asUintN(
      64,
      (BigInt.asUintN(
        64,
        (v * multiplicator))) >> b57)
  ];
}

function lsb(v) {
  v = -v | v;
  return deBruijn[
    BigInt.asUintN(
      64,
      (BigInt.asUintN(
        64,
        (~(v) * multiplicator))) >> b57)
  ];
}
console.log(lsb(BigInt(18)))
console.log(msb(BigInt(18)))
1 голос
/ 31 мая 2020

Поймите, что ответ на этот вопрос уже был выбран, но обнаружил, что это интересная проблема, которую, вероятно, лучше всего решить с помощью веб-сборки (WASM). К сожалению, похоже, что WASM не поддерживает параметры i64, поэтому пришлось согласиться на отправку BigInt как lo / hi (i32 / i32) и сшивание вместе как i64 в WASM перед поиском MSB.

Код WASM довольно прост, он использует https://pengowray.github.io/wasm-ops/ для определения правильных кодов операций. Кроме того, используется https://webassembly.github.io/wabt/demo/wat2wasm/ для создания, отладки и компиляции текста веб-сборки (WAT) в WASM. Операция i64.clz - это то место, где происходит настоящий маг c. Весь предыдущий код состоит в том, чтобы сшить два числа i32 вместе, чтобы сформировать фактическое число i64 для проверки. Также обратите внимание, что WASM немного похож на калькулятор RPN ...

main.wat чуть ниже скомпилирован в main.wasm

(module
  (func $lz (param $lo i32) (param $hi i32) (result i32)
    get_local $hi
    i64.extend_i32_u
    i64.const 32
    i64.shl

    get_local $lo
    i64.extend_i32_u
    i64.add

    i64.clz
    i32.wrap_i64
  )
  (export "lz" (func $lz))
)

Список ниже включает ответ для De Bruijn решение, чтобы проверить относительную производительность.

EDIT Также наткнулся на Какой самый эффективный способ получить позицию младшего бита числа в javascript? , который указывает на функцию Math.clz32 (!). Скомбинируйте несколько вспомогательных функций для поддержки поиска MSB для 64-битного BigInt и выполнили тесты с этим третьим вариантом.

ВНИМАНИЕ! Выполнение приведенного ниже кода создаст 10 миллионов BigInt для работы с решениями Math.clz32, WASM и De Bruijn. На моем ноутбуке Acer при нескольких запусках решения Math.clz32 проходят через 10M MSB проверок за ~ 1,8 с, решение WASM за ~ 3,4 с и решение Де Брюйна за ~ 15,1 с.

ВНИМАНИЕ! При запуске этого кода будет выполнено 30 миллионов тестов, и будет пауза, прежде чем вы увидите какие-либо результаты в журнале консоли.

1 голос
/ 29 мая 2020

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

Скорее всего, встроенный -in functions indexOf () и lastIndexOf () будет быстрее, чем for-l oop.

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

...