4106人阅读
数据结构/算法（33）
输入一个整数n，求从1 到n 这n 个整数的十进制表示中1 出现的次数。
例如输入12，从1 到12 这些整数中包含1 的数字有1，10，11 和12，1 一共出现了5 次。
注：这是一道广为流传的google 面试题。
我们每次判断整数的个位数字是不是1。如果这个数字大于10，除以10 之后再判断个位数字是不是1。（对每一个数x，x先与10取余，然后判断x/10之后，是否为0，不为0则继续上述操作&复杂度为o(n) ）
代码如下：
/*--------------------------------
Copyright by yuucyf.
----------------------------------*/
#include &stdafx.h&
#include &iostream&
int ItemContain1Count(int nValue)
int nNum = 0;
while (nValue)
if ((nValue % 10) == 0x1)
nValue /= 10;
int Sum(int n)
if (n &= 0)
int nSum = 0;
for (int i32I = 1; i32I &= i32I++)
nSum += ItemContain1Count(i32I);
int _tmain(int argc, _TCHAR* argv[])
int i32N = 0, i32Num = 0;;
cout && &请输入整数N=&;
cin && i32N;
cout && &从1~& && i32N && &之间含有1的个数为：& && Sum(i32N) &&
思路一有一个非常明显的缺点就是每个数字都要计算1 在该数字中出现的次数，因此时间复杂度是O(n)。当输入的n 非常大的时候，需要大量的计算，运算效率很低。
我们用一个稍微大一点的数字21345作为例子来分析。我们把从1到21345的所有数字分成两段，即1--21345。先来看中1出现的次数。1的出现分为两种情况：一种情况是1出现在最高位（万位）。从1到21345的数字中，1出现在这10000个数字的万位中，一共出现了1次方）次；另外一种情况是1出现在除了最高位之外的其他位中。例子中，这20000个数字中后面四位中1出现的次数是2000次（2*1000，其中2的第一位的数值，1000是因为数字的后四位数字其中一位为1，其余的三位数字可以在0到9这10个数字任意选择，由排列组合可以得出总次数是2*1000）。
至于从1到1345的所有数字中1出现的次数，我们就可以用递归地求得了。这也是我们为什么要把1-21345分为1--21345两段的原因。因为把21345的最高位去掉就得到1345，便于我们采用递归的思路。
分析到这里还有一种特殊情况需要注意：前面我们举例子是最高位是一个比1大的数字，此时最高位1出现的次数10000（对五位数而言）。但如果最高位是1呢？比如输入12345，从1这些数字中，1在万位出现的次数就不是10000次，而是2346次了，也就是除去最高位数字之后剩下的数字再加上1。
使用递归21345&，则需要对21345的每一个10进制位，进行递归计算。对万位，千位，百位，十位，个位&
&&&&&& 即首位不为0，则可以分别计算 345 45 5&&&&&
&&&&& (1) 当首位最高位为1时，含有1的个数为 10000
&&&&&& 首位可以为0 ， 1 ，则后四位其中有1位为1的个数为 ，2* 10(3)*4 = 8000& 合计18000&&&&&&&
&&&& (2) 下面计算1345
&&&&&&& 首位为1，则为& 346
&&&&&&& 其余位为 （首位可以为0） 3 * 10(2) = 30& 合计376&&&
&&&& (3)下面计算345
&&&&&&&& 首位为1& 10的2次方
&&&&&&&& 首位可以为(0 1 2) 等于3的情况，& 3 * 2 *10& 合计160
&&&&&&&& 剩下的循环即求300- 345
&&&& (4)下面计算45&&&&
&&&&&&&& 首位为1， 10的1次方
&&&&&&&& 首位不计，首位可以取(0 1 2 3) 4 * 1& 合计 14
&&&&& （5）下面计算5
&&&&&&&& 判断长度小于1，直接返回
&求1到n中任意进制的数的个数，递归公式如下：&&&&&
&总结对于任意的1到n，求所给定的字符c的个数&&&
&&str = abcdefgh ,&len = strlen(abcdefgh)&&&&&
&&&&&&& (1)当首位等于*str = c时 ，Q(abcdefgh) = abcdefgh + 1 + (*str -'0')*(len -1)*10^(len -2) + Q(bcdefgh)
&&&&&&& (2)当首位为 *str & c 时 ，Q(abcdefgh) = 10^(m-1) + (*str - '0') * (len 1) *10^(len -2) + Q(bcdefgh)
&&&&&&& (3)当首位为 *str & c时，&& Q(abcdefgh) =& (*str - '0') * (len -1) *10^(len -2) + Q(bcdefgh)
代码如下：
int NumberOf1(char * pStr, char* c) //c表示查找pStr中含有c字符的数字的个数
return 0 ;
int nLen = strlen(pStr) ;
if (nLen == 1)
if(*pStr &= *c)
return 1 ;
return 0 ;
if (*pStr == *c)
//当首位为c的时候
return strtoul(pStr+1, NULL, 10) + 1 + (*pStr - '0') * (nLen - 1) * (int)pow(10.0, (double)(nLen - 2)) + NumberOf1(pStr + 1, c);
else if (*pStr & *c)
return (int)pow(10.0, (double)nLen-1) + (nLen - 1) * (*pStr - '0') * (int)pow(10.0, (double)(nLen - 2))
+ NumberOf1(pStr+1, c) ;
return (nLen - 1) * (*pStr - '0') * (int)pow(10.0, (double)(nLen - 2)) + NumberOf1(pStr+1, c) ;
第二种算法的时间复杂度为：O(k), 其中K为常数，是pstr的长度.
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：230485次
积分：2776
积分：2776
排名：第10308名
原创：50篇
转载：24篇
评论：83条
(2)(1)(2)(1)(1)(12)(2)(5)(14)(6)(8)(10)(1)(2)(2)(4)(1)算法（70）
整数的二进制表示中1的个数
题目：输入一个整数，求该整数的二进制表达中有多少个1。
例如输入10，由于其二进制表示为1010，有两个1，因此输出2
-----------------------------------------------------------
这道题其实不难，就是位操作的一个考察，恰好最近在研究这个东西，所以还是比较顺手的，
我们可以一位一位去找为1的可是==只能用来判断整数或者其他数据类型，貌似不能用来判断bit位是否相等，我们这里可以用是非运算
我们只用某一位为1，其余位为0，然后 与 整数相与，得到的要么是0，要么是1，这不就可以了么？？
//============================================================================
: CalcBitInInteger.cpp
// Version
// Copyright
: Your copyright notice
// Description : Hello World in C++, Ansi-style
//============================================================================
#include &iostream&
int CalcBit(int n);
int main() {
int input = 0;
cout&&CalcBit(input);
int CalcBit(int n){
int i = 0;
int result = 0;
for(i=0;i&32;i++){
if(n & (1&&i))
result++;
就贴个简单的结果校验下：
其实这种位操作在大运算里还是非常好的，它可以极大降低我们的存储量，把空间使用率提高，例如在搜索，大数据方面 有着很重要的作用，我希望尽其能给出一些关于搜索方面的知识，最近刚开始学，希望能借用次博客记录每一点！
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：107526次
积分：2381
积分：2381
排名：第12615名
原创：132篇
转载：20篇
(1)(1)(1)(1)(1)(2)(3)(2)(5)(3)(3)(5)(36)(89)100题（55）
28.整数的二进制表示中1的个数
题目：输入一个整数，求该整数的二进制表达中有多少个1。
例如输入10，由于其二进制表示为1010，有两个1，因此输出2。
这道题的另外一个变种是：求两个整数二进制表示形式中有多少个位上的数据不同。其实对这两个整数进行异或运算就可以转换成本题，最终还是求一个异或得到的整数二进制表示形式中1的个数。
这里提供两种思路
1：直接计数
考虑到输入的整数可能为负数，直接对其进行向右移位操作时，会将最高位符号位移入到低位，所以采用（1&&i)&number这种方法。
2.number&= number-1
这是一种很经典的位运算计较，可以将number中最低位的1变为0，重复执行该运算直到number为零，执行该运算的次数即为number中1的个数。
在整数中1个数较少的情况下，比思路1中循环计数的方法效率要很高。
#include &stdafx.h&
#include&iostream&
namespace MS100P_28
int countOnesOfIntiger1(int number)
int bits = 8*sizeof(int);
int count = 0;
for (int i = 0; i &i++)
if ((1 && i)&number)
int countOnesOfIntiger2(int number)
int count=0;
while (number != 0)
number = number&(number - 1);
void test()
int n = -6;
cout && countOnesOfIntiger1(n) &&
cout && countOnesOfIntiger2(n) &&
int _tmain(int argc, _TCHAR* argv[])
MS100P_28::test();
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：91161次
积分：2808
积分：2808
排名：第10147名
原创：199篇
文章：92篇
阅读：35110
(1)(71)(86)(40)(1)