Быстрая ближайшая мощность 2 в JavaScript?

Есть ли более быстрая альтернатива следующему выражению:

Math.pow(2,Math.floor(Math.log(x)/Math.log(2)))

То есть, взяв самую близкую (меньшую) целую степень 2 двойника? У меня такое выражение во внутреннем цикле. Я подозреваю, что это может быть намного быстрее, учитывая, что можно просто взять мантиссу из представления IEEE 754 двойника.

Ответ 1

Использование ES6 Math.clz32 (n) для подсчета ведущих нулей 32-разрядного целого числа:

// Compute nearest lower power of 2 for n in [1, 2**31-1]:
function nearestPowerOf2(n) {
  return 1 << 31 - Math.clz32(n);
}

// Examples:
console.log(nearestPowerOf2(9));  // 8
console.log(nearestPowerOf2(33)); // 32

Ответ 2

Здесь другая альтернатива, с ориентирами. Хотя оба они кажутся сопоставимыми, мне нравится, когда я могу пол или потолок.

function pow2floor(v) {
  var p = 1;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function pow2ceil(v) {
  var p = 2;
  while (v >>= 1) {
    p <<= 1;
  }
  return p;
}

function MATHpow2(v) {
  return Math.pow(2, Math.floor(Math.log(v) / Math.log(2)))
}

function runner(fn, val) {
  var res;
  for (var i = 0; i < 10000000; i++) {
    fn(val);
  }
  return
}

var then;
var source = 3000;

then = new Date().getTime();
var a = runner(pow2floor, source);
console.log(" a result: " + pow2floor(source));
console.log(" pow2floor: " + (new Date().getTime() - then));

then = new Date().getTime();
var b = runner(MATHpow2, source);
console.log(" b result: " + MATHpow2(source));
console.log(" MATHpow2: " + (new Date().getTime() - then));

// my results (results vary by system and browser)
//  pow2floor: 217 (ms) winner!
//  MATHpow2: 2773 (ms) loser

Ответ 3

К сожалению, вам понадобится эквивалент функции C frexp. Лучшее, что я смог найти, находится в JSFiddle, а в его коде используется Math.pow.

Есть несколько альтернатив, которые вы могли бы сравнить, используя реальные данные, вместе с вашей текущей попыткой:

Начиная с 1.0, умножайте его на 2.0 до тех пор, пока оно больше или равно входу, а затем умножьте его на 0,5, пока оно не станет меньше или равно входу. Вам понадобится специальная обработка значений на концах двойного диапазона.
Сохраняйте массив возрастающих значений всех точных степеней двух в двойном диапазоне и выполняйте двоичный поиск.

Первый, скорее всего, будет самым быстрым, если ваши данные, как правило, близки к 1.0. Второй требует до 11 условных ветвей.