Kiểm tra số nguyên tố 2 (Power of Two) trong JavaScript

Kiểm tra số có phải lũy thừa của 2

Viết hàm isPowerOfTwo(n) trả về true nếu n = 2^k (k ≥ 0, số nguyên).

Đệ quy (Recursive) - Từ bài gốc

const isPowerOfTwo = num => {
    if (num === 1) return true;      // 2^0 = 1
    if (num % 2 !== 0) return false; // Số lẻ > 1 không phải
    return isPowerOfTwo(num / 2);    // Đệ quy chia 2
};

console.log(isPowerOfTwo(3));    // false
console.log(isPowerOfTwo(32));   // true (2^5)
console.log(isPowerOfTwo(2048)); // true (2^11)
console.log(isPowerOfTwo(256));  // true (2^8)
console.log(isPowerOfTwo(22));   // false

Cách tối ưu: Bitwise Operation (O(1))

Số lũy thừa của 2 trong nhị phân chỉ có **một bit 1**: 1 (1), 10 (2), 100 (4), 1000 (8)...

Đặc tính: n & (n - 1) === 0 (trừ khi n = 0).

const isPowerOfTwo = n => n > 0 && (n & (n - 1)) === 0;

// Test
console.log(isPowerOfTwo(0));    // false
console.log(isPowerOfTwo(1));    // true  (2^0)
console.log(isPowerOfTwo(2));    // true
console.log(isPowerOfTwo(3));    // false
console.log(isPowerOfTwo(4));    // true
console.log(isPowerOfTwo(16));   // true
console.log(isPowerOfTwo(1024)); // true
console.log(isPowerOfTwo(1023)); // false

Giải thích bitwise

n = 8    = 1000 (binary)
n-1 = 7  = 0111
n & (n-1) = 0000 = 0 ✓

n = 6    = 0110
n-1 = 5  = 0101
n & (n-1) = 0100 = 4 ≠ 0 ✗

Các cách khác

// 1. Math.log2 (có thể lỗi floating point)
const isPowerOfTwo = n => n > 0 && Number.isInteger(Math.log2(n));

// 2. Loop (iterative)
const isPowerOfTwo = n => {
    if (n <= 0) return false;
    while (n % 2 === 0) n /= 2;
    return n === 1;
};

// 3. Count bits (ES6: n.toString(2))
const isPowerOfTwo = n => n > 0 && n.toString(2).split('0').join('').length === 1;

So sánh hiệu suất

Ứng dụng thực tế

// Kích thước buffer, texture (GPU yêu cầu power of 2)
function validateTextureSize(width, height) {
    return isPowerOfTwo(width) && isPowerOfTwo(height);
}

// Memory allocation (page size, buffer size)
function allocateBuffer(size) {
    // Round up to next power of 2
    const pow2 = 1 << Math.ceil(Math.log2(size));
    return new ArrayBuffer(pow2);
}

// Bitmask flags
const READ = 1;    // 0001
const WRITE = 2;   // 0010
const EXEC = 4;    // 0100
// Mỗi flag là power of 2 -> combine bằng OR, check bằng AND