建设部网站诚信平台,北京公司公示在哪个网站,seo排名优化代理,做学校网站素材图片素材记录来自《剑指offer》上的算法题。
题目如下#xff1a; 请实现一个函数#xff0c;输入一个整数#xff0c;输出该数二进制表示中1的个数。例如把9表示成二进制是1001#xff0c;有两位是1#xff0c;因此如果输入9#xff0c;函数输出是2。 这道题目的一个基本思路是…记录来自《剑指offer》上的算法题。
题目如下 请实现一个函数输入一个整数输出该数二进制表示中1的个数。例如把9表示成二进制是1001有两位是1因此如果输入9函数输出是2。 这道题目的一个基本思路是先判断整数二进制表示中最右边一位是否为1接着将整数右移一位再进行判断这样每次右移一位直到整数为0为止。其代码实现如下
int NumbersOf1(int n){int count 0;while(n){if (n 1)count;n n 1;}return count;
}
但这是一个容易引起死循环的解法当遇到负数的时候如0x80000000将其右移一位不是简单的将最左边的1移动到左边第二位变成0x40000000,而是要保持负数即移位后应该是0xC0000000最高位依然是1这样一直往右移动最后得到的会是0xFFFFFFFF从而陷入死循环。
为了避免这种情况我们可以不移动输入的数字。而是移动1每次将其左移一位这样就可以与输入的数字n的从右边开始每一位进行判断是否有1。实现代码如下
// 常规解法判断二进制数中1的个数
int NumbersOf1(int n){int count 0;unsigned int flag 1;while (flag){if (n flag)count;flag flag 1;}return count;
}
这种算法的循环次数等于整数二进制的位数。
下面介绍一种更好的改进方法其循环次数等于整数中1的个数。实现如下
// 改进算法
int NumbersOf1Optimiz(int n){int count 0;while (n){count;n (n - 1) n;}return count;
}
其接法思路是当一个整数减去1后会将最右边的1变为0而该位再往右的位都变为1如1100再减去1后得到的是1011原来最右边的1是第二位现在变成了1而原来是0的则变成了1此时将1011与原来的整数1100进行与操作后会得到1000也就是将原来整数中最右边的1变成了0那么一个整数的二进制中有多少个1就可以进行多少次这样的操作即整数减去1后与原整数进行与运算的操作。
更完整代码可以查看测试例子。
