题目
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
思路
把一个整数减去1,再和原整数做与运算,会把整数最右边一个1变成0.那么一个整数的二进制表示中有多少个1,就可以进行多次这样的操作。
代码
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int NumberOf1(int n){
int count = 0;
while(n){
n &= (n-1);
++count;
}
return count;
}
};
int main(){
Solution s;
int n;
while(cin>>n){
int result = s.NumberOf1(n);
cout<<result<<endl;
}
return 0;
}
思路二
我们可能很快就有一个思路:先判断整数二进制表示中最右边一位是不是1.接着把输入的整数右移一位,此时原来处于从右边数起第二位被移到最右边了,再判断是不是1。这样每次移动一位,直到整个整数变成0为止。基于这个思路我们写完下面的程序。但是当我们输入一个负数时,这个方法就会出现问题。比如0x80000000,把负数0x80000000右移一位时并不是简单的把最高位的1移到第二位变成0x40000000,而是0xC0000000。这是因为移位前是个负数,仍然要保证移位后是个负数,因此移位后最高位仍然是1。如果一直做右移运算,最终这个数字就会变成0xFFFFFFFF而陷入死循环。
代码二
class Solution {
public:
int NumberOf1(int n){
int count = 0;
while(n){
if(n & 1){
++count;
}
n = n >> 1;
}
return count;
}
};
思路三
为了避免死循环,我们可以不右移输入的数字n。首先把n和1做与运算,判断n的最低位是不是为1。接着把1左移一位得到2,再和n做与运算,就能判断n的次低位是不是1…….这样反复左移,每次都能判断n的其中一位是不是1。
代码三
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
using namespace std;
class Solution {
public:
int NumberOf1(int n){
int count = 0;
int base = 1;
while(base){
if(n & base){
++count;
}
base = base << 1;
}
return count;
}
};
int main(){
Solution s;
int n;
while(cin>>n){
int result = s.NumberOf1(n);
cout<<result<<endl;
}
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
剑指 Offer 15. 二进制中1的个数方法一:位运算* @param {number} n - a positive integervar hammingW
请实现一个函数,输入一个整数,输出该数二进制表示中 1 的个数。例如,把 9 表示成二进制是 1001,有 2 位是 1。因此,如果输入 9,则该函数输出 2。 思路 详见链接 代码 class Solution: def hammingWeight(self...
《剑指Offer》 1. 赋值运算函数 2. 单例设计模式 3. 二维数组中查找目标值 4. 替换字符串中的空格 5. 从尾到头打印链表 6. 由前序和中序遍历重建二叉树 7. 用两个栈实现队列 8. 求旋转数组的最小数字 9. ...
1.正数(包括边界值1、0x7FFFFFFF) 2.负数(包括边界值0x80000000、0xFFFFFFFF) 1.与二进制有关的题目要往位运算方面想,复习一
# Python实现《剑指offer》 部分代码自己添加了一些测试用例, 或者自己添加了一些功能 1. 初级程序员注重算法和数据结构 2. 事先做好准备,对工作有热情 3. 面试过程放松。不要急于写代码,了解清楚所要解决的问题,...
leetcode中国 LeetCode ...二进制中1的个数 Y Y Y 剑指 Offer 17. 打印从1到最大的n位数 Y Y Y 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 Y Y Y 剑指 Offer 24. 反转链表 Y Y Y 剑指 Offer 25. 合并
11.二进制中1的个数 12.数值的整数次方 13.调整数组顺序使奇数位于偶数前面 14.单链表:链表中倒数第k个结点 15.单链表:反转链表 16.单链表:合并两个排序的链表 17.二叉树:树的子结构 18.二叉树:二叉树的镜像 19....
2. 位运算将出现三次的元素换成二进制形式放在一起,其二进制对应位置上,出现 1 的个数一定是 3 的倍数(包括 0)。此时,如果在放进来只出现一次的元素,则某
调整数组顺序使奇数位于偶数前面,对称的二叉树,二叉树的镜像,二叉树的深度,二叉树的下一个节点,二叉树中和为某一值的路径,二叉搜索树的第k个节点,二叉搜索树的后序遍历序列,二叉搜索树和双向链表,二进制中1的个数,二...
2. 位运算将出现三次的元素换成二进制形式放在一起,其二进制对应位置上,出现 1 的个数一定是 3 的倍数(包括 0)。此时,如果在放进来只出现一次的元素,则某
面试题10:二进制中1的个数 面试题14:调整数组顺序使奇数位于偶数前面 面试题18:树的子结构 面试题20:顺时针打印矩阵 面试题21:最小栈 面试题26:复杂链表的复制 面试题31:连续字数组的最大和 面试题32:从1到n...
剑指offer 15. 二进制1的个数 class Solution: def hammingWeight(self, n: int) -> int: res = 0 while n: res += 1 n &= n - 1 return res 巧用n&(-n)运算 其中 -n是 n 的相反数,是一个负数。该位运算技巧可以...
面试题10 二进制中1的个数 第3章 高质量代码 3.3 代码的完整性 面试题11 数值的整数次方 面试题12 打印1到最大的n位数 面试题13 O(1)时间删除链表结点 面试题14 调整数组顺序使寄数位于偶数前面 3.4 代码的鲁棒性 ...
二进制中1的个数 简单 剑指offer16 数值的整数次方 中等 剑指offer17 打印从1到最大的n位数 简单 剑指offer18 删除链表的节点 简单 剑指offer19 正则表达式匹配 困难 剑指offer20 表示数值的字符串 中等 剑指offe
使用Python3用pythonic的方式实现《剑指Offer 第二版》中的题目。拒绝直接“翻译”java等实现。代码有些并非原创,搬运了一些LeetCode中大神的优秀解法,比如:如何用一行代码实现顺时针打印矩阵。 基本所有题都包含...
√二进制中1的个数 -> ->(升级版) √数值的整数次方(溢出) -> 打印从1到最大的n位数(溢出) -> 没找到 √删除链表的节点 ->(简单版) ->(升级版) ×正则表达式匹配 -> ×表示数值的字符串 -> √调整数组顺序...
二进制中1的个数 16. 数值的整数次方 17. 打印从1到最大的n位数 第一大类--二叉树 解题密码如下: void traverse(TreeNode* root) { // 前序遍历 traverse(root->left) // 中序遍历 traverse(root->right) // 后序...
第十题 二进制中1的个数 测试10 第十一题 数值的整数次方 测试11 第十二题 打印1到最大的n晚数 测试12 第十三题 O(1)时间删除链表节点 测试13 第十四题 使数据库中的奇数位于偶数前面 测试14 第十五题 找链表中倒数...