幾個水桶？

這是來自 LIOJ 上的題目，因為解法很有趣，所以想記錄下來。

最原始的解法

這個方法最直覺，也是我最一開始的解法：

1. n = 水量
2. count = 水桶數量
3. 遍歷 2^0 到 2^31
4. 每當找到比 n 大的數字，更新 n 的值，count + 1
5. 重複 3-4，直到 n 為 0

function solve(lines) {
  // 所需水量
  let capacity = Number(lines[0])
  // 計數器
  let count = 0
  // 只要 capacity > 0，就會一直執行
  while (capacity) {
    // 找出最大的水桶
    let max = findMaxBucket(capacity)
    // 把水桶裝滿後，更新水量
    capacity -= 2**max
    // 計數器 + 1
    count++
  }
  // 印出幾個水桶
  console.log(count)
}
function findMaxBucket(n) {
  /* 
    找出最大值，最大值有兩個可能：
    1. 超過 n，代表前一個數字就是最大值
    2. 等於 n，代表這個數字就是最大值
  */
  for (let i=0; i<=31; i++) {
    // 等於 n
    if(2**i === n) {
      return i
    // 超過 n 
    } else if (2**i > n) {
      return i-1
    }    
  }
}
solve(['20'])  // 2

這樣做的缺點是「會有不同的回傳值」：

1. 超過 n 的情況回傳 i - 1
2. 等於 n 的情況回傳 i

在 findMaxBucket 裡面，因為兩種情況的回傳值不同，所以需要多做一層判斷。

其實可以反過來思考：不要「從小找到大」，而是「從大找到小」

在從小找到大時，因為實際上要的水桶是「前一個（i - 1）」，所以得回傳 i - 1；但如果是從大找到小，實際上要的水桶正好就是 i，所以可以直接回傳 i。

也就是說，不管小於或等於的情況，回傳的值都是 i，就不用多寫一層判斷，而是直接利用 <= 來判斷即可。

可以參考下面的解法。

聰明一點的解法

把剛剛的作法修正一下，寫出更簡潔的程式碼：

1. n = 水量
2. count = 水桶數量
3. 遍歷 2^31 ~ 2^0
4. 每當找到比 n 小的數字，更新 n 的值，count++
5. 重複 4-5，直到 n 為 0

function solve(lines) {
  // 所需水量
  let capacity = Number(lines[0])
  // 計數器
  let count = 0
  // 只要 capacity > 0，就會一直執行
  while (capacity) {
    // 找出最大的水桶
    let max = findMaxBucket(capacity)
    // 把水桶裝滿後，更新水量
    capacity -= 2**max
    // 計數器 + 1
    count++
  }
  // 印出幾個水桶
  console.log(count)
}

function findMaxBucket(n) {
  // 從大找到小
  for (let i=31; i>=0; i--) {
    // 不管小於等於的回傳值都是 i
    if(2**i <= n) {
      return i
    }
  }
}
solve(['20'])  // 2

有趣的做法

如果你懂二進位的話，你會發現這一題背後其實只是在問 「n 轉成二進位後有幾個 1」？

以 20 為例，20 的二進位是 10100。你仔細看的話就會發現 1 出現的次數正好就是最佳的水桶數量，所以解法就會是：

1. n = 水量
2. count = 水桶數量
3. 把 n 轉成二進位（字串）
4. 遍歷 n 的每一個字元，算出總共有幾個 1

function solve(lines) {
  // 所需水量
  let capacity = Number(lines[0])
  // 計數器
  let count = 0
  // 轉成二進位
  let binaryString = transToBinary(capacity)
  // 遍歷二進位值，算出有幾個 1
  for(let i=0; i<binaryString.length; i++) {
    if(binaryString[i] === '1') count++
  }
  console.log(count)
}
function transToBinary(n) {
  let result = ''
  /*
    只要 n > 0，繼續把 n 除以 2 求餘數
    把每一次除以 2 的餘數拼接到 result 
  */
  while(n) {
    result = (n%2) + result
    // 要記得去掉小數點
    n = Math.floor(n/2)
  }
  return result
}
solve(['20'])  // 2

提醒一下，let binaryString = transToBinary(capacity)

可以寫成： let binaryString = capacity.toString(2)，不用像我一樣傻傻的做轉換。

所以這一題就這樣解決囉。

還有更酷的作法？

其實就是剛剛的延伸，你可以直接利用「位移」和「位元運算」來計算一個數字有幾個 1。

注意：用這個方法就不用再把數字先轉成二進位了，因為位移跟位元運算會以「十進位」來解析數字。如果你又轉成二進位，例如 20 = 10100，這時候 10100 就會被當作十進位來解析。

1. 檢查最後一個數字是不是 1 n & 1
2. 是的話把 count++
3. 更新 n 的值 n >>= 1

function solve(lines) {
  // 所需水量
  let capacity = Number(lines[0])
  // 計數器
  let count = 0
  // capacity = 0 時才會停止
  while(capacity) {
    // 做 AND 位元運算 
    if(capacity & 1) {
      count++
    }
    // 利用位移更新 capacity 的值
    capacity >>= 1
  }
  console.log(count)
}