Tính số bit 1 trong biểu diễn nhị phân các số trong JavaScript

Mô tả vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một số nguyên num làm đối số duy nhất. Hàm chuẩn bị một mảng cho mọi số từ 0 đến num (bao gồm cả hai), mỗi phần tử tương ứng là số lượng bit 1 trong biểu diễn nhị phân của số đó.

Ví dụ, nếu đầu vào là:

const num = 4;

Thì đầu ra nên là:

const output = [0, 1, 1, 2, 1];

Giải thích đầu ra

Vì 0 chứa 0 bit 1, 1 chứa 1, 2 (10) chứa 1, 3 (11) chứa 2, 4 (100) chứa 1.

Ví dụ minh họa

Mã thực hiện (tối ưu O(n)):

const num = 4; 
const mapBinary = (num = 0) => { 
  if (num === 0){ 
    return [0]; 
  }; 
  const res = [0]; 
  for (let i = 1; i <= num; i++) { 
    const n = i % 2 === 0 ? res[i/2] : res[Math.floor(i/2)] + 1; 
    res.push(n); 
  }; 
  return res; 
};

Giải thích mã

Khi tính số bit, có quy luật sau giúp tối ưu:

• số bit của n === số bit của 2*n (chỉ thêm bit 0 ở cuối).
• Nếu n chẵn, bit cuối là 0.
• Nếu n lẻ, kết quả = số bit của floor(n/2) + 1 (thay bit cuối bằng 1).

Đầu ra

Kết quả trong console sẽ là:

[ 0, 1, 1, 2, 1 ]