欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  web前端

javascript数据结构与算法详解

程序员文章站 2022-03-25 20:44:22
...
请实现一个函数,输入一个整数,输出该数二进制表示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数据结构与算法详解的详细内容,更多请关注其它相关文章!