javascript数据结构与算法详解

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));

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