先看一道面试题:
长度为n的数组,由数字1到n组成,其中数字a不出现,数字b出现两次,其它的数字恰好出现一次。怎样通过只读遍历一次数组,找出数字a和b。
由于只能遍历一次,在遍历数组arr时,算出a和b的差值,以及a和b的平方差,通过解方程,即可求得a和b。具体做法为:
设:
s1 = 1 + 2 + ... + n (= n * (n + 1) / 2)
s2 = arr[0] + arr[1] + ... + arr[n - 1]
r1 = 1 + 4 + ... + n^2 (= n * (n + 1) * (2 * n + 1) / 6)
r2 = arr[0]^2 + arr[1]^2 + ... + arr[n - 1]^2
c = a - b = s1 - s2
d = a^2 - b^2 = r1 - r2
显然:a + b = (r1 - r2) / (s1 - s2)
根据a+b的值和a-b的值,很容易就可算出a和b。
算法虽然简单,但实现起来,却有一个很大问题:计算s1、s2、r1、r2这4个数时,计算过程中可能出现溢出,造成结果不准。由于最终目的是为了计算出c和d,一个改进的方法是:
c = s1 - s2 = (1 - arr[0]) + (2 - arr[1]) + ... + (n - arr[n - 1])
d = (1 - arr[0]^2) + (4 - arr[1]^2) + ... + (n^2 - arr[n - 1]^2)
但这样的做法,并不能解决问题,n稍微大点,照样存在溢出问题。
那么怎样才能避免计算溢出呢?答案很简单,用模运算!每进行一次加减运算时,都取结果为原结果除以一个足够大的常数M的余数。这样加减运算中,就不会现现溢出问题。最后再由c % M、d % M,推测出c、d的具体值。比如说,计算s2改为计算:
s2 % M = ((((arr[0] % M) + arr[1]) % M + ...) % M + arr[n - 1]) %M
从表面上看,采用模运算后,计算量会增加很多。但实际上,若M取合适的值时,计算量并不会增加!!
先回顾下计算机基本知识:两个各N位(寄存器为N位)的二进制无符号整数a和b相加,若结果溢出了,CPU会怎么处理?当然是将溢出的那一位忽略掉(可能还要设置下溢出标志),得到的结果实际上是:(a + b) mod 2^N。无符号数间的算术运算,本质上就是模运算。现在的CPU都采用二补数来表示负整数,本质上也是运用模运算(教科书将二补数表示的负整数简单定义为:对正整数取反后加1),这与无符号数间的运算是一致的,在实现上,比用其它方法(比如说一补数)表示负整数,要优美易实现。
在32位平台下,-x mod 2^32 = 2^32 – x (x > 0),
因而-1的二进制表示就是:0xFFFFFFFF
了解了这些,就不会奇怪C/C++标准的规定:无符号数间的运算是模运算不会溢出;有符号数转为无符数,采用模运算后的值。(为了兼容没采用二补数的机器,无符号数转为有符号数时,若无符号数的数值超出了有符号数可表示的范围,结果是平台相关的。)
因而,在对32位CPU平台,可以先将有符号数转为无符号数,再取M = 2 ^32。需要特别注意的是,应该采用多少位的无符号数保存计算中用到的数值,如何避免模运算可能带来的问题:
① 无符号数类型的选择:
a、b的取值范围为:[1, n],
c % M = (a - b) % M的取值范围为:[1, n] (a > b时),[M - n, M - 1] (a < b时)
这两个范围不能重叠,而因n < M - n即2 * n < M
若M取2^32的话,且n < 2^31,可以采用32位无符号数表示c的值。
根据c % M值在哪一个范围,可以确定a > b还是a < b,
由于运算过程中都是采用无符号数计算,当a < b时,必须进行如下调整:
c % M调整为(-c) % M
d % M调整为(-d) % M
这样才能保证结果的正确性。
②用公式计算所有数字的和、平方和时,可能出现的问题:
模运算满足:(a * b) % M = ((a % M) *** (b % M)) % M
但不满足:(a/ b) % M = ((a % M) / (b % M)) % M
在计算(n * (n + 1) / 2) % M时,不能写成:
s = ((n * (n + 1)) % M / 2) % M,
而应该写成:
if (n % 2 == 0) s = ((n / 2) * (n + 1)) % M
else s = (((n + 1) / 2) * n) % M
或者:s = (INT((n + 1) / 2) * (n + (n + 1) % 2)) % M(其中INT(x)为取小数x的整数部份)。
完整代码:
#include
#include
#define SMALL_ARRAY 0
structPair{
intzero;
inttwice;
};
//32位CPU平台,长度n一定小于2^16次方时,表示一个数的平方值,可用32位无符号数类型,效率很高。
//长度n若在[2^16, 2^31]区间,就必须用到64位无符号数类型,效率较高。
//长度n若在[2^31, 2^32)时,表示 所有数的和sum,就必须改用64位无符号数类型,效率不高。
Pair find_number(constintarr[],unsignedlen)
{
constunsignedbits=CHAR_BIT sizeof(unsigned);*
#if SMALL_ARRAY
constunsignedmax_len=1u<< (bits/2u);
typedefunsignedintuint;
#else
constunsignedmax_len=1u<< (bits-1);
typedefunsignedlonglonguint;
#endif
assert(arr&&len>=2&&len<max_len);
constunsigned*constdata= (constunsigned*)arr;
unsignedsum=0;
uint square_sum=0;
for (unsignedi=0;i<len; ++i){
constunsignedvalue=data[i];
sum+=value;
square_sum+= (uint)value*value;//注意两个数的乘积是否会溢出
}
//1 + 2 + 3 + ... + len = len * (len + 1) / 2
constuint sum_all= (len+1) /2u* (uint)(len+ (len+1) %2u);
//1^2 + 2^2 + 3^2 + ... + len^2 = len * (len + 1) * (2 * len + 1) / 6
constunsignedlen2=2u*len+1;
constuint square_sum_all=len2%3u==0?len2/3u*sum_all:sum_all/3u*len2;
unsigneddifference= (unsigned)sum_all-sum;
uint square_difference=square_sum_all-square_sum;
constboolis_negative=difference>INT_MAX;
if (is_negative) {
difference= -difference;
square_difference= -square_difference;
}
assert(difference!=0&&square_difference%difference==0);
constunsignedsum_two=square_difference/difference;
assert((sum_two+difference) %2u==0);
constunsignedlarger= (sum_two+difference) /2u;
constunsignedsmaller= (sum_two-difference) /2u;
if (is_negative) {
constPair result= {smaller,larger};
returnresult;
}
constPair result= {larger,smaller};
returnresult;
}
intmain()
{
}
原文链接: https://www.cnblogs.com/flyinghearts/archive/2012/03/20/2408771.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/44703
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!