淘先锋技术网

首页 1 2 3 4 5 6 7

2.1 求二进制数中 1 的个数

书上的解法一是最基本的做法,除以 2,求模。

而除以 2 求模,完全可以转换为更快的位运算。这就是解法二,也是我能想到的最好的解法。效率 log2(n)。

没想到,书上还提出了解法 3,我看了三遍,看不懂啥意思。

网上搜了一下,有人给出了容易理解的解释

这个解释总结一下,就是 v=v&(v-1) 这个表达式,每次都会消除二进制数中最右边的一个 1。所以用来数 1 的个数,要比解法 2 更快。

因为运算的次数只跟 1 的个数有关。比如 10000000,用解法 2 需要 8 次,而解法 3 只要 1 次。

要理解这个方法,可以把数字分三种情况:1 在最右,1 在中间,1 在最左。

  1. 如果 1 在最右,v&(v-1) 显然就是把右的 1 去掉了,即 xxxx1 & xxxx0 = xxxx0。
  2. 如果 1 在最左, v&(v-1) 就是 10…0 & 01…1,会把最左的 1,也是唯一的 1 去掉了。
  3. 如果 1 在中间,也就是最右边的 1 的右边全是0,v&(v-1) 可以看成两部分,1 左边的部分不受影响,1 右边的部分就是上面的第二种情况。xxx100 & xxx011 = xxx000,依然会把这个 1 给消除。

书上的解法四和解法五,思想就是:在数据量不大,而且需要频繁使用的时候,直接把每个输入对应的结果算出来,也就是打表。

解法五是我之前想的,在另一个程序里,把 8 位数的范围对应的 1 的个数算出来,在这个程序里写成数组,直接根据输入来输出结果,O(1) 的效率。

但解法四我没想过,思路虽然和解法五医院,但在有数据的情况下,不打表,而是每次都比较,太不合理。也就是他是这个意思:

if(a==) return ;
else if(a==)return ;
else if(a==) return ;
else if(a==) return ;
...
else if(a==) return ;

缺点就是,极端情况下要比 255 次。还不如前面的做法。

扩展问题:

1. 如果是 32 位,用哪个算法,或者改进哪个?

前三个解法都还行,最多 32 次。第四个解法不行了,极端情况要比较 2^32 次。解法五,如果还是打表,就要开个 2^32 大小的数组,也不好。

解法一用除法比解法二的位运算慢,解法二比解法三的次数一般要多。

所以还是解法三比较好。

至于改进哪个。我想不到前四个算法的改进余地。如果是解法五的话,我可以想到,32 位可以分成 4 个 8 位。然后对 4 个 8 位计数,最后的和就是结果。这个做法其实也可以用在第四个算法上,但我对解法四基本没有改进欲望。

2. 两个正整数 A 和 B,把 A 改为 B,需要改变多少位?

也就是问 A、B 有多少位不同。我觉得先对 A、B 异或吧,相同是 0,不同是 1。得到的结果再去数有多少个 1。C++ 的异或的运算符是,^

读者反馈:

这部分看不太懂了,下次再看。主要是三个内容:

  1. 读者博客
  2. hamming_weight 维基百科
  3. SSE 4.2 popcnt 指令

2.2 不要被阶乘吓到

这个问题有两个小问:

  1. N!末尾多少个 0
  2. N! 最低位 1 的位置

第一小问,我开始想的方法是,只看个位,如果乘积的结果个位是0,就计数加1,然后把十位作为个位继续乘下一个数。然而我发现,万一乘以 100,这个方法就不行了。

书上给的是另一个思路,因为 10 的组成是 2 和 5,也就是把 2 和 5 的个数数出来,较小的那个就是 10 的个数,也就是 0 的个数。而 2 要远多于 5,所以只要数 5 的个数。

这就是解法一。

而解法二更秀。直接用 Z = N/5 + N/5^2 + N/5^3… 的思路来做。

因为 n/5,1 到 n 的数里,就是含有 5 的因子的个数,然后 n/=5,继续做 n/5,这其实就是含有 25 的因子的个数,并且其中一个 5 已经算过了,这里是算另一个 5。

第二小问,我开始的想法是,如果要求一个数字最低位的 1,那可以用上一题的做法,先取到他最右的 1。然而对原来的数字异或。接着从右开始往左数,结束。

但这题问的是 N!,所以原来的数字基本得不到。甚至分段来移位都不行,因为数字不一定能存的下来。

书上又给了个我想不到的做法,因为数字最低位的1的位置,等于数字的质因数 2 的个数,加 1。其实也好理解。最低位的 1 右边全是 0,右移几次就是除以 2 几次。问题是这个 N! 要算出来么?不是。

这个题的解法跟第一小问一样,是用计数。依然是用 z = n/2 + n/4 + n/8 + … 的方法来做。z 个2的质因数,加 1 就是最右的 1 的位置。

解法二更厉害,直接理论化:n! 的质因数的 2 的个数,就等于 n - (n 的二进制中 1 的个数)。

例如 n = abcde(a~e 为 0 或者 1),那么

z = abcd + abc + ab + a
= a000+ b00 + c0 + d + a00 + b0 + c + a0 + b + a
= aaaa+ bbb + cc + d

如果 x 为 0 ,则直接消除,若 x 为 1,则 xxx = 1000 - 1。不妨设 a,b 为1,c ,d,e 为 0。也就是 n = 11000

则 z = 10000-1 + 1000 - 1
= 11000 - 2 (n = 11000 有 2 个 1)

若 e 为 1,也就是 n = 11001,

则 z = 10000 - 1+1000-1+1-1
= 11001 - 3(n=11001 有 3 个 1)

所以 n!的 2 的质因数的个数等于 n - ( n 的二进制中 1 的个数)。

相关题目:给定整数 n,判断他是否为 2 的方幂。(提示:n>0&&((n&(n-1))==0))

2 的方幂是啥意思,2,4,8,16 这样的数?那是不是只要看 n 有几个 1 就行?1 的个数直接用 v&(v-1) 来数。因为只有 1 个 1,必然在最左,因为更左的 0 已经不算了。

好像真的是这样做啊,那跟第二题没啥关系啊,用的还是第一题的思想。

2.3 寻找发帖“水王”

这题我能理解的是先排序,再计数。

如果发帖数大于 1/2,能么在 n/2 位置能找到(数组情况)。

后面的降低问题规模的方法没看懂,特别是代码部分。

扩展问题:3 个人发帖超过 1/4,怎么找 id,我也想不到啥办法。