javascript資料結構與演算法詳解

請實作一個函數，輸入一個整數，輸出該數二進位表示1的個數。例如把9表示成二進位是1001，有2位是1。因此如果輸入9，則函數輸出2。首先對於二進位1的求解，在這裡，我們最應該想到的就是關於位元運算的一些運算子。總共有五種運算，分別是：與（&），或（|），異或（^），右移（>>），左移（<<）。

第一個可能會造成死循環的解法：
思路1：先對你所給的這個整數進行判斷，這個數的最右邊是不是1。如果是1，給一個計數器，給它加1。接著把輸入的整數右移一位，這樣一直進行移位，最後直到這個整數變成0為止，然後輸出計數器就好了。

function NumberOf1(n)
{
  let count = 0;
  while(n) {
    if(n & 1) {
      count ++;
    }
    n = n >> 1;
  }
  return count;
}
console.log(NumberOf1(9));</p>
<p>這個演算法對於無符號數來說沒有問題，可是對於有符號數問題就大了，極有可能造成死循環。當n為負數時，n右移在最高位補1（為了確保資料為負數），因而最終就會形成死循環。例如：0x80000000時，這時候就會出現問題，當右移一位的時候時，就變成了0xC0000000。因為是對負數的移位，所以必須確保移位後是個負數，所以最高位永遠都會是1，所以也就意味著這最終這個數字永遠會死循環下去。 </p>
<p>思路2：移動1，先判斷最低位是不是1，然後把1移成2。再與整數比比較，就能判斷倒數第二位是不是1，依序下去。 。 。這樣最終就能達成一個效果，得到所有的1的個數。 </p>
<pre class="brush:php;toolbar:false">function NumberOf1(n) {

  let count = 0;
  let flag = 1;
  while(flag) {
    if(n & flag) {
      count ++;
    }
    flag = flag << 1;
  }
  return count;
}
console.log(NumberOf1(9));

最後，我們提供出來一種最好的方法。

思路3：把一個整數減去了1，再和原整數做與運算，會把這個整數最右邊一個1變成0，並且把這個1後面的0都變成1。那麼一個整數的二進制有多少個1，就可以進行多少次這樣的操作，最後，透過把計數器確定運算次數，輸出計數器就好了。

//更好的解法
function NumberOf1(n) {
  let count = 0;
  while(n) {
    count ++;
    n = (n-1) & n;
  }
  return count;
}
console.log(NumberOf1(9));

相關推薦：

PHP中的資料結構:DS擴充詳解

php資料結構之順序鍊錶與鍊式線性表示例

JavaScript資料結構之單鍊錶與循環鍊錶實例分享

以上是javascript資料結構與演算法詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章！