Question:

Solution:

1
2
3
4

public int bitwiseComplement(int N) {
    if(N == 0) return 1;
    return (Integer.highestOneBit(N)<<1) - N -1;
}

eg:
N=10, ans = 5 = 16 - 10 - 1
N=7, ans = 0 = 8 - 7 -1
N=5, ans = 2 = 6 -5 -1

Analyze:

N = 10, binaryN 1010
ans = 5,binaryA 0101
binaryN + binaryA = 1111
binaryN + binaryA + 1= 10000
so, binaryA = 10000 - binaryN - 1

方案：

1. 代码中加开关控制

2. versionName/versionCode 加一些规则

3. ChannelID 控制

比较：

关于VersionName/VersionCode区分beta的实现方法：

1. 可以直接在VersionName中写上alpha/beta 字段区分
2. 可以利用VersionCode处理（比如奇偶/是否被n整除）

结论：

• 推荐方案1或2

题

输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数
例： 输入12，从1到12的这些整数中包含1的数字有 1，10，11，12， 一共出现5次

分析

暴力解法：就是遍历，处理每个数的位数，除10取余，判断整数的个位是否为1
显然不能用这样的办法来答题

思路一

暴力——遍历，除10取余看个位，不再展开介绍

思路二

能不能找到一些别的规律，来提高计算效率

我们举个例子：n = 21345
将1到n分为两段： 1~1345，1346~21345

先看第二段 1246~21345：
1分两种情况出现。首先分析最高位， 10000~19999这1万个数中，最高位全是1，一共记10^4个，所以对于12345这样的数字，最高位1出现的次数为：
2345+1= 2346 次
接下来分析1出现在除次高位的情况， 1346~21345这2w个数中，次高位上出现1的次数是2000次（1346~1999，21000~21345），由于最高位是2，我们可以再把1346~21345分成两段，1346~11345，11346~21345，每一段剩下的4位数字中，选择其中一位是1，其余三位为0~9的Any，根据排列组合，总共出现的次数是 2 * 10^3 = 2000次
对于1到1345之间的计数，就可以通过递归来求得了：
1~21345分成 1~1345， 1346~21345 ，接着，把21345的最高位去掉就变成1345了

分段时候其实有有意这样区分的，目的就是为了使用递归

SourceCode

先将数字转换成字符串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

int NumberOf1Between1AndN(int n){
  if(n <= 0) return 0;

  char strN[50];
  sprintf(strN, "%d", n);

  return NumberOf1(strN);
}

int NumberOf1(const char* strN){
  if(!strN || *strN < '0' || *strN > '9' || *strN == '\0') return 0;

  int first = *strN - '0';
  unsigned int length = static_cast<unsigned int>(strlen(strN));

  if(length == 1 && first == 0)
    return 0;

  if(length == 1 && first > 0)
    return 1;

  int numberFirstDigit = 0;
  if(first > 1)
    numberFirstDigit = PoserBase10(length - 1);
  else if(first = 1)
    numberFirstDigit = atoi(strN + 1) + 1;

  int numOtherDigits = first * (length - 1) * PoserBase10(length -2);

  int numRecursive = NumberOf1(strN + 1);

  return numberFirstDigit + numOtherDigits + numRecursive;
}

int PoserBase10(unsigned int n){
  int result = 1;
  for(unsigned int i = 0; i < n; ++i)
    result *= 10;

  return result;
}