数据结构与算法（位运算） --javascript语言描述

maxmin 发布于2019-08-26 11:45 / 2700人阅读

摘要：例如把表示成二进制是，有位是。首先对于二进制的求解，在这里，我们最应该想到的就是关于位运算的一些操作符。总共有五种运算，分别是与，或，异或，右移，左移。当为负数时，右移在最高位补为了保证数据为负数，因而最终就会形成死循环。

二进制中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));

GPU云服务器云服务器位运算位运算详解按位运算 bit位运算

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/107497.html

【算法技巧】位运算装逼指南

摘要：位算法的效率有多快我就不说，不信你可以去用亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这些技巧，当然，采用位运算，也是可以装逼的，不信，你往下看。位算法的效率有多快我就不说，不信你可以去用 10 亿个数据模拟一下，今天给大家讲一讲位运算的一些经典例子。不过，最重要的不是看懂了这些例子就好，而是要在以后多去运用位运算这...

_ang 2019-05-22 14:28 评论0 收藏0
常用加密算法探寻

摘要：在开发过程中，常常用到各种加密方法和算法，本文总结了几种常用加密方法的原理。非对称加密原理非对称加密算法需要两个密钥公开密钥和私有密钥。在开发过程中，常常用到各种加密方法和算法，本文总结了几种常用加密方法的原理。对称加密 showImg(https://segmentfault.com/img/bVbacxw?w=1128&h=468); 原理：加密和解密数据使用同一个密钥，适...

Yu_Huang 2019-06-21 16:46 评论0 收藏0
面试算法实践与国外大厂习题指南

摘要：面试算法实践与国外大厂习题指南翻译自维护的仓库，包含了在线练习算法概述与大厂习题实战等内容。面试算法实践与国外大厂习题指南在线练习在线面试编程数据结构链表即是由节点组成的线性集合，每个节点可以利用指针指向其他节点。面试算法实践与国外大厂习题指南翻译自 Kevin Naughton Jr. 维护的仓库 interviews，包含了在线练习、算法概述与大厂习题实战等内容。笔者发现正好和...

genedna 2019-08-14 17:46 评论0 收藏0
Nodejs进阶：crypto模块中你需要掌握的安全基础知识

摘要：加解密伪代码加密解密非对称加密又称公开秘钥加密。常见的非对称加密算法。通常来说对称加密速度要快于非对称加密。在之后的通讯阶段，可以使用对称加密算法对数据进行加密，秘钥则是握手阶段生成的。确认信息完整未被篡改。一、文章概述互联网时代，网络上的数据量每天都在以惊人的速度增长。同时，各类网络安全问题层出不穷。在信息安全重要性日益凸显的今天，作为一名开发者，需要加强对安全的认识，并通过技...

xzavier 2019-06-21 16:40 评论0 收藏0