iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 12
0
自我挑戰組

菜鳥工程師的奇幻漂流:跟著kata活化手指和意識系列 第 12

Bit Counting

今日kata

原始題目如下:(6kyu)
Write a function that takes an integer as input, and returns the number of bits that are equal to one in the binary representation of that number. You can guarantee that input is non-negative.

翻譯:
將十進位數字轉為二進位表示,計算其中包含幾個1

範例:

數字1234 二進位表示為10011010010,其中出現5次1,結果需回傳5
The binary representation of 1234 is 10011010010, so the function should return 5 in this case

構想&解法

var countBits = function(n) {
 return n.toString(2).split('').filter(item=>item>0).length
};

使用Number.toString(2),將數字轉為二進位表示的字串。

(1234).toString(2)="10011010010"

拆解字串成陣列,過濾只留下不為0的元素。

"10011010010".split('')=["1", "0", "0", "1", "1", "0", "1", "0", "0", "1", "0"]

["1", "0", "0", "1", "1", "0", "1", "0", "0", "1", "0"].filter(item->item>0)=["1", "1", "1", "1", "1"]

最後陣列長度即為1出現的數量。


其他解法觀摩

countBits = n => n.toString(2).split('0').join('').length;

不使用filter,反而是使用0來切割二進位的字串。省下filter過程~


function countBits(n) {
  for(c=0;n;n>>=1)c+=n&1
  return c;
}

如果出現很多疑問....不用擔心...我也是
深呼吸...試著找出一點蛛絲馬跡....

  • >>& 都屬於位元運算子,肯定充分使用了位元的概念來解題
  • >> a>>b,將a的二進位表示法右移 b (< 32) 位元,拋棄被移出的位元。
a = 8 // 1 0 0 0
a>>1  // 0 1 0 0  =4
a>>1=4 即是將數字8以位元表示後,往右移1位元

For loop解釋:

 for(c=0;n!=0;n=n>>1){
     c=c+(n&1)
 }
  • 初始狀態宣告c=0,c用來計算1出現的次數(count)
  • loop執行的終止條件為n不為0 (0:false; 1:true)
  • n和1做位元比較 (當最右邊的位元為1時,c+1)
  • 每執行完一次,n>>1 (轉為位元表示並右移一位元)

Ex:位元運算

// & 位元AND
// 3 = 0 1 1
// 1 = 0 0 1
// &:當對應位元皆為1時,回傳1
// 3&1 = 0 0 1

// >> 位元右移
// 3>>1
// 3 = 0 1 1
// 3>>1 = 0 0 1

小結:
n和1做&位元運算,如果n的最右側位元等於1,count數加1。接著n右移一位元,繼續和1做&位元運算,n一直一直往右移一位元,直到n=0。

位元運算真的太強大了....../images/emoticon/emoticon02.gif

以上為今日分享的內容,若有錯誤或是建議,請再隨時和我聯繫。


上一篇
給自己愛的鼓勵
下一篇
Your order, please
系列文
菜鳥工程師的奇幻漂流:跟著kata活化手指和意識30

尚未有邦友留言

立即登入留言