请实现一个函数,输入一个整数,输出该数二进制表示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));
相关推荐:
위 내용은 javascript数据结构与算法详解의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!