Sức mạnh gần nhất nhanh của 2 trong JavaScript?

Question

Có nhanh hơn thay thế cho các biểu thức sau đây:

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

Đó là, chụp gần nhất (nhỏ hơn) số nguyên sức mạnh của 2 của một đôi? Tôi có biểu hiện như vậy trong một vòng lặp bên trong. Tôi nghi ngờ nó có thể nhanh hơn nhiều, xem xét người ta chỉ có thể lấy phần định trị từ đại diện IEEE 754 của đôi.

Answer 1

Tận dụng ES6 của Math.clz32(n) để đếm số không hàng đầu của 32-bit số nguyên:

// 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

Answer 2

Thật không may, bạn sẽ cần tương đương với hàm C frexp. Điều tốt nhất tôi có thể tìm thấy là ở số JSFiddle và mã của nó sử dụng Math.pow.

Có một vài lựa chọn thay thế, bạn có thể điểm chuẩn, sử dụng dữ liệu thực tế, cùng với nỗ lực hiện tại của bạn:

1. Bắt đầu từ 1.0, nhân nhiều lần bằng 2,0 cho đến khi nó lớn hơn hoặc bằng với đầu vào, sau đó nhân với 0,5 cho đến khi nó nhỏ hơn hoặc bằng đầu vào. Bạn sẽ cần xử lý đặc biệt cho các giá trị ở đầu của dãy kép.
2. Lưu trữ mảng giá trị tăng dần của tất cả các lũy thừa chính xác của hai trong phạm vi kép và thực hiện tìm kiếm nhị phân.

Cách đầu tiên có thể nhanh nhất nếu dữ liệu của bạn thường gần bằng 1.0. Cái thứ hai yêu cầu lên đến 11 nhánh có điều kiện.

Answer 3

Đây là một giải pháp thay thế khác, với điểm chuẩn. Trong khi cả hai có vẻ là tương đương, tôi thích có thể để sàn hoặc ceil.

function pow2floor(v){ 
 
    v++; 
 
    var p = 1; 
 
    while (v >>= 1) {p <<= 1;} 
 
    return p; 
 
} 
 
function pow2ceil(v){ 
 
    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){ 
 
    for(var i=0; i<10000000; i++){ 
 
     fn(val); 
 
    } 
 
} 
 

 
var then; 
 
var source = 123456789; 
 

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

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

Attempting to post the results into the HTML here is altering the results. Look in your browsers console fore results.