javascript数据结构与算法详解

javascript数据结构与算法详解,第1张

请实现一个函数,输入一个整数,输出该数二进制表示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));

这个算法对于无符号数来说没有问题,可是对于有符号数问题就大了,极有可能造成死循环。当n为负数时,n右移在最高位补1(为了保证数据为负数),因而最终就会形成死循环。比如:0x80000000时,这时候就会出现问题,当右移一位的时候时,就变成了0xC0000000。因为是对负数的移位,所以必须保证移位后是个负数,所以最高位永远都会是1,所以也就意味这最终这个数字永远会死循环下去。

思路2:移动1,先判断最低位是不是1,然后把1移成2。再与整数比比较,就能判断倒数第二位是不是1,依次下去。。。这样最终就能达成一个效果,得到所有的1的个数。

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中文网其它相关文章!

文章来源:https://www.php.cn/faq/386938.html

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复