题目分析
最头痛的题目来了,实现减法,乘法,除法操作,其中不能使用位运算操作。这个题目简直是折磨,但是也挺锻炼人对于计算机数据存储的知识。
数学
这个问题太复杂了,我们先要实现取负数运算,因为减去一个数相当于加上这个数的相反数。这不仅在减法中用得到,在乘除法也可以用到,乘除一个负数等于乘这个数的相反数再取相反数。
其中难点不仅仅是正负的问题,还有INT32_MAX和INT32_MIN不相等的问题,因为负数是可以取到-2147483648,而正数只能取到2147483647。我看题解中很多人的方法都不周全,对于-1 - (-2147483648)这个例子,很多方法都不能通过。可能是官方的测试样例不够充分,所以都能够提交成功。
其中有一个人减法的方法是a + neg(b)。但是对于b=-2147483648这个情况,是不能直接取负数的。因此要进行特判。
下面我分成四个部分叙述我的方法。
neg取相反数
对于一个数217来说,我们如何得到-217呢?我们不可能每次都从0加(-1),先尝试-1,然后再尝试-2,直到-217为止。题目中说我们可以使用常数,可以模拟计算机二进制的存储方式。我们先看217 + (-512)是否小于0,如果小于0,说明加上负数太大了,我们换-256,看217 + (-256)是否小于0,还是小于0,我们继续看217 + (-128)是否小于0,发现大于0,说明负数小了,我们就保留-128,此时仍然剩余89,继续寻找-64,发现-64也可以,保留-64,此时剩余25,继续寻找-32,-16,-8,-4,-2,-1。最后的结果是(-128) + (-64) + (-16) + (-8) + (-1) = -217。
对于负数取相反数同理,对于-217取相反数,那就判断-217 + 512是否大于0,如果大于0,说明加上正数太大了,就换256。最后也能得到217。
因此我们要提前记录下-1,-2,-4,-8…常数,和1,2,4,8…常数,这样不用每次都推导。
至于-2147483648取相反数,我们只用在对应的操作中进行特判即可。如减法,我们在减法函数中进行特判,因此不会出现传入-2147483648数的情况。
minus减法
**对于b = INT32_MIN,我们可以返回a + INT32_MAX + 1即可。其他情况下返回a + neg(b)**。
multiply乘法
当b == 0时,return 0。当b == INT32_MIN,为了保证题目有意义,a一定是0或者1,a = 0时返回0,a = 1时返回b即可。当b < 0 时,return neg(multiply(a, neg(b)))。这用到了数学中的交换律。a x b = -1 x (a x (-1 x b))。因此我们只用考虑b是正数的情况即可。
如13 x 14,我们13相加14次,虽然可以,但是一定会TLE,因此我们仍然要用到二进制的知识。14的二进制最后四位是1110。(1110 = 8 + 4 + 2+ 0),因此我们可以使用乘法结合律,13 x 14 = 13 x (8 + 4 + 2 + 0) = 13 x 8 + 13 x 4 + 13 x 2 + 13 x 0。我们需要直到b的二进制表示,用一个bit数组和getBin函数,获取正数b的二进制表达,因为是正数,只需要31位。然后得到了二进制位以后,tmp = a,在这个例子中tmp = 13,每次移动一个tmp += tmp,等价于tmp翻倍。如果该位是1,则加上,该位是0继续下一位。
模拟计算的过程:最低为是0,因此res += 0,此时tmp = 26,第二位是1,因此res += 26,tmp = 52,第三位是1,因此res += 52,tmp = 104,第四位是1,因此res += 104。最后res = 0 + 26 + 52 + 104 = 182。当a为负数,计算过程是一样的。
其中注意tmp要用long long类型接收,否则可能会超出表达范围。
divide除法
除法是最复杂的过程。但原理都是类似的。当a == 0时,return 0。当b == INT32_MIN时,如果a == b时,return 1,其余情况都return 0。当b == 1时,return a。当b < 0 时,我们也和乘法做类似处理,这样b就一定为正数。
下面要分类讨论a的情况。如果a为正数
如180 / 13,和乘法一样,我们也要计算13的倍数表示,13, 26, 52, 104, 208…。因为180小于208,那么说明13的16倍是不够的,但是108大于104,说明13的8倍是超过的。这时要计算-13的倍数表示,-13,-26,-52,-104,-208。为什么还需要负数表示呢?因为要用180 + (-104),表示当前还剩余的数字。
最高位是$b \times 2^{30}$,因为b不能为0,b = 1时前面已经特判,b最小是2,因此最高位已经远远超过了所有的整型范围。因此要用long long类型保存。如果使用vector容器保存,当这个值大于a就可以停止了,为了小伙伴理解方便,就用数组保存。如本例中,我们只用保存到104和-104即可,要使用数组来保存,就需要设置一个停止位,或者用long long保存。这里为了简单,就使用long long类型。在104后面的数组都大于180,因此都是不够的,都会跳过比较。我们直接从104开始模拟。
模拟计算的过程:180大于等于104,说明180大于等于13的8倍,我们让res += 8,然后180 + (-104) = 76。继续比较,76大于等于52,说明76大于等于13的4倍,我们让res += 4,然后76 + (-52) = 24。继续比较,24小于26,说明24不够13的2倍,不做操作。继续比较,24 大于等于13,说明24大于等于13的1倍,我们让res += 1。比较完成,res = 8 + 4 + 1 = 13。
上面是a为正数的情况,a为负数类似
如-180 / 13,-180小于等于-104,说明-180小于等于13的-8倍,res += -8,然后-180 + 104 = -76。继续比较,后面的过程就不重复了,最后res = (-8) + (-4) + (-1) = 13。
有的小伙伴们就会问了,为什么a为负数时不能也利用交换律返回neg(divide(neg(a), b))呢?这个我是想过的,因为a可能等于-2147483648,那么取负数就会出现问题。因此还是分类讨论稳妥一些。
这就是上面所有的分析过程,小伙伴们也可以简单一些,全部转换为long long类型,然后都改成只看前32位。最后计算完再强制转换为int返回即可。但是核心思想全部都是一样的。
算法的**时间复杂度为$O(nlog(m))$,空间复杂度为$O(log(m))$**,其中n为操作次数,m为数据的范围,这里为int的数据大小。
1 | #include<iostream> |
刷题总结
这个题目真的是太复杂了,但是其中蕴含着二进制的奥秘,这个知识点是需要小伙伴们掌握的。