codeforces 1406D
(ans+d[1]+1)>>1 和 (s+a[0]+1)>>1 产生了完全不同的结果(Ac & Wa)
对于正数,右移一位相当于除以2,但是负数却不同,
(-1>>1)==-1(-2>>1)==-1(-3>>1)==-2(-3>>1)==-2正数右移高位补0,负数右移高位补1.由于负数存为对应正数的补码.
一个数和它的相反数,的前面各位相反,最后一位相同(0除外),则移除最后一位,两个数各位相反,则 ( a > > 1 ) + ( − a > > 1 ) + 1 = = 0 (a>>1)+(-a>>1)+1==0 (a>>1)+(−a>>1)+1==0,即 ( − a > > 1 ) = = − ( a > > 1 ) − 1 ( a ≠ 0 ) (-a>>1)==-(a>>1)-1 (aneq0) (−a>>1)==−(a>>1)−1(a=0)
x除以2并向下取整可以写为 ( x + 1 ) > > 1 (x+1)>>1 (x+1)>>1
x除以2并向上取整可以写为 ( ( x − 1 ) > > 1 ) + 1 ((x-1)>>1)+1 ((x−1)>>1)+1