剑指offer – 二进制中1的个数 – JavaScript
专注前台与算法的系列干货分享,欢迎关注(???):
「微信公众号:心谭博客」| xxoo521.com | GitHub
题目形容
输入一个整数,输出该数二进制表示中 1 的个数。其中负数用补码表示。
解法 1: 判断每一位
依次判断数字的每一位,统计其中 1 的数量。整体思路如下:
- 数字先和 1 相与,结果为 0 说明改位是 1,结果为 1 说明该位是 1
- 将 1 左移一位,再和数字相与。这次判断的是倒数第二位能否位 1
- 将 1 总共左移 32 次(由于数字底层是 32 位),统计总数就可
注意:尽量规避让原数字右移动,有符号位的问题,可能会陷入死循环。尽量采取左移而不是右移。
时间复杂度 O(1), 空间复杂度 O(1)。代码如下:
// 原文地址:https://xxoo521.com/2019-12-31-number-of-one/// ac地址:https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8/** * @param {number} n * @return {number} */function NumberOf1(n) { let count = 0; let flag = 1; let times = 0; while (times++ < 32) { if (flag & n) { count += 1; } flag = flag << 1; } return count;}解法 2: n & (n - 1)
解法 2 采用n & (n - 1)的做法,这种做法的可行起因是:能将数字 n 的二进制表示中,最右边的 1 变成 0。
举个例子,以 5 为例,其二进制是 101:
101 & 100=>100100 & 011=>0
因而,整体思路是:
- n 和 n-1 相与的结果赋给 n
- n 假如为 0,结束;否则回到第 1 步
和解法 1 相比,空间复杂度是 O(1),但是解法 1 肯定需要循环 32 次,但是解法 2 的循环次数就是数字中 1 的个数,优于解法 1。
// 原文地址:https://xxoo521.com/2019-12-31-number-of-one/// ac地址:https://www.nowcoder.com/practice/8ee967e43c2c4ec193b040ea7fbb10b8/** * @param {number} n * @return {number} */function NumberOf1(n) { let count = 0; while (n) { n = n & (n - 1); ++count; } return count;}专注前台与算法的系列干货分享,欢迎关注(???)
image
说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 剑指offer – 二进制中1的个数 – JavaScript
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 剑指offer – 二进制中1的个数 – JavaScript