第 6 章 基本数字运算计算机软件技术与数学是不可切割的有机整体很多企业在招聘求职者的时候往往非常在意求职者的数学能力站在企业的角度来看编程语言是很简单的东西只要熟悉一种语言其他语言也很容易学会而数学素养的高低却不然需要长时间的学习与积累直接决定了未来求职者的职业生涯的发展。所以面试官在考察求职者时也比较喜欢出此类题目。6.1 如何判断一个自然数是否是某个数的平方【出自 GG 面试题】难度系数★★★☆☆ 被考察系数★★★★☆题目描述设计一个算法判断给定的一个数 n 是否是某个数的平方不能使用开方运算。例如 16就满足条件 因为它是 4 的平方 而 15 则不满足条件 因为不存在一个数使得其平方值为 15。分析与解答方法一直接计算法由于不能使用开方运算因此最直接的方法就是计算平方。主要思路对 1 到 n 的每个数 i计算它的平方 m如果 mn则继续遍历下一个值 i1如果 mn那么说明 n 是m 的平方如果 mn那么说明 n 不能表示成某个数的平方。实现代码如下/* 判断一个自然数是否是某个数的平方 */ fun isPowern Int Boolean { var i 1 var m Int if n 0 { println${n}不是自然数 return false } while i n { m i * i if m n return true else if m n return false i } return false } fun mainargs ArrayString { val n1 15 val n2 16 if isPowern1 println${n1}是某个自然数的平方 else println${n1}不是某个自然数的平方 if isPowern2 println${n2}是某个自然数的平方 else println${n2}不是某个自然数的平方 } 程序的运行结果如下 15 不是某个自然数的平方 16 是某个自然数的平方算法性能分析由于这种方法只需要从 1 遍历到 n^0.5 就可以得出结果因此算法的时间复杂度为On^0.5。方法二二分查找法与方法一类似这种方法的主要思路还是查找从 1n 的数字中是否存在一个数 m使得 m 的平方为 n。只不过在查找的过程中使用的是二分查找的方法。具体思路是首先判断mid1n/2 的平方 power 与 m 的大小如果 powerm那么说明在[1 mid-1]区间继续查找否则在[mid1 n]区间继续查找。实现代码如下fun isPowern Int Boolean { var low 1 var high n var mid Int var power Int while low high { mid low high / 2 power mid * mid when { power n - high mid - 1//接着在 1mid-1 区间查找 power n - low mid 1 //接着在 mid1 到 n 区间内查找 else -return true } } return false }算法性能分析由于这种方法使用了二分查找的方法因此时间复杂度为 Olog2n其中 n 为数的大小。方法三减法运算法通过对平方数进行分析发现有如下规律n1^2 n^2 2n 1n-1^2 2*n-11 2*n1…1 2*1 1 2*2 1 … 2*n 1。通过上述公式可以发现这些项构成了一个公差为 2 的等差数列的和。由此可以得到如下的解决方法对 n 依次减 1357…如果相减后的值大于 0则继续减下一项如果相减后的值等于 0则说明 n 是某个数的平方如果相减的值小于 0则说明 n 不是某个数的平方。根据这个思路代码实现如下fun isPowernumber Int Boolean { var n number var minus 1 while n 0 { n - minus minus when { n 0 -return true //n 是某个数的平方 n 0 -return false //n 不是某个数的平方 else -2 //每次减数都加 2 } } return false }算法性能分析这种方法的时间复杂度仍然为 On^0.5。由于方法一使用的是乘法操作这种方法采用的是减法操作因此这种方法的执行效率比方法一更高。6.2 如何判断一个数是否为 2 的 n 次方【出自 ALBB 面试题】难度系数★★★☆☆ 分析与解答被考察系数★★★★★方法一构造法2 的 n 次方可以表示为 2^0 2^1 2^2〓 2^n如果一个数是 2 的 n 次方那么最直观的的想法是对 1 执行了移位操作每次左移一位 即通过移位得到的值必定是 2 的 n 次方针对 n 的所有取值构造出所有可能的值。所以要想判断一个数是否为 2 的 n 次方只需要判断该数移位后的值是否与给定的数相等实现代码如下/* 判断 n 能否表示成 2 的 n 次方 */ fun isPowern Int Boolean { if n 1 return false var i 1 while i n { if i n return true i i shl 1 } return false } fun mainargs ArrayString { if isPower8 println8 能表示成 2 的 n 次方 else println8 不能表示成 2 的 n 次方 if isPower9 println9 能表示成 2 的 n 次方 else println9 不能表示成 2 的 n 次方 } 程序的运行结果如下 8 能表示成 2 的 n 次方 9 不能表示成 2 的 n 次方算法性能分析上述算法的时间复杂度为 Olog2n 。方法二与操作法那么是否存在效率更高的算法呢通过对 2^0 2^1 2^2… 2^n 进行分析发现这些数字的二进制形式分别为 1 10 100…。从二进制的表示可以看出如果一个数是 2 的 n次方那么这个数对应的二进制表示中有且只有一位是 1其余位都为 0。因此判断一个数是否为 2 的 n 次方可以转换为这个数对应的二进制表示中是否只有一位为 1。 如果一个数的二进制表示中只有一位是 1 例如 num00010000 那么 num-1 的二进制表示为 num-100001111由于 num 与 num-1 二进制表示中每一位都不相同因此 numnum-1的运算结果为 0。可以利用这种方法来判断一个数是否为 2 的 n 次方。实现代码如下fun isPowern Int Boolean { if n 1 return false val m n and n - 1 return m 0 }算法性能分析这种方法的时间复杂度为 O1。6.3 如何不使用除法操作符实现两个正整数的除法【出自 WR 面试题】难度系数★★★★☆ 被考察系数★★★☆☆分析与解答方法一减法主要思路是使被除数不断减去除数直到相减的结果小于除数为止此时商就为相减的次数 余数为最后相减的差。 例如在计算 14 除以 4 的时候 首先计算 14-410 由于 104继续做减法运算 10-46 6-42此时 24。由于总共进行了 3 次减法操作最终相减的结果为 2因此 15 除以 4 的商为 3余数为 2。如果被除数比除数都小那么商为 0余数为被除数。根据这个思路的实现代码如下/* 计算两个自然数的除法 */ fun dividemolecular Int denominator Int { var m molecular println${m}除以$denominator var res 0 var remain m //被除数减除数直到相减结果小于除数为止 while m denominator { m - denominator res 1 } remain m println商为 $res 余数 $remain } fun mainargs ArrayString { val m 14 val n 4 dividem n } 程序的运行结果如下 14 除以 4 商为 3 余数为 2算法性能分析这种方法循环的次数为 m/n因此算法的时间复杂度为 Om/n。需要注意的是这种方法也实现了不用%操作符实现%运算的目的。方法二移位法方法一所采用的减法操作还可以用等价的加法操作来实现。例如在计算 17 除以 4 的时候可以尝试 4*1 4*2 44 4*3 444依次进行计算直到计算的结果大于 14 的时候就可以很容易地求出商与余数。但是这种方法每次都递增 4效率较低。下面给出另外一种增加递增速度的方法以 2 的指数进行递增取 2 的指数的原因是 2 的指数操作可以通过移位操作来实现有更高的效率计算 4*1 4*2 4*4 4*8由于 4*817然后接着对 17-4*41进入下一次循环用相同的方法进行计算。实现代码如下fun dividemolecular Int n Int { var m molecular println${m}除以$n var multi Int var result 0 while m n { multi 1 // multi * nm/2即 2* multi * n m时结束循环 while multi * n m shr 1 { multi multi shl 1 } result multi // 相减的结果进入下次循环 m - multi * n } println商为 $result 余数 $m }算法性能分析由于这种方法采用指数级的增长方式不断逼近 m/n因此算法的时间复杂度为Ologm/n。引申一如何不用加减乘除运算实现加法分析与解答由于不能使用加减乘除运算因此只能使用位运算了。首先通过分析十进制加法的规律来找出二进制加法的规律从而把加法操作转换为二进制的操作来完成。十进制的加法运算过程可以分为以下 3 个步骤 1各个位相加而不考虑进位计算相加的结果 sum。 2只计算各个位相加时进位的值 carry。 3将 sum 与 carry 相加就可以得到这两个数相加的结果。例如 1529 的计算方法为 sum34不考虑进位 carry10只计算进位因此 1529sumcarry341044。同理二进制加法与十进制加法有着相似的原理唯一不同的是在二进制加法中 sum与 carry 的和可能还有进位因此在二进制加法中会不停地执行 sumcarry 操作直到没有进位为止。具体实现方法如下 1二进制各个位相加而不考虑进位。由于在不考虑进位的时候加法操作可以用异或操作代替因此不考虑进位的加法可以用异或运算来代替。 2计算进位由于只有 11 才会产生进位因此进位的计算可以用与操作代替。进位的计算方法为先做与运算再把运算结果左移一位。 3不断对 1、 2两步得到的结果相加直到进位为 0 的时候为止。根据这个思路实现代码如下fun addnumber1 Int number2 Int Int { var n1 number1 var n2 number2 var sum Int //保存不进位相加结果 var carry Int //保存进位值 do { sum n1 xor n2 //异或代替不进位相加 carry n1 and n2 shl 1 //与操作代替计算进位值 n1 sum n2 carry } while carry 0 //判断进位值是否为 0 return sum } fun mainargs ArrayString { printlnadd2 4 } 程序的运行结果为 6引申二如何不用加减乘除运算实现减法分析与解答由于减去一个数等于加上这个数的相反数即-nn-1n1因此 a-ba-b ab1可以利用上面已经实现的加法操作来实现减法操作实现代码如下fun suba Int b Int Int { return adda addb.inv 1}引申三如何不用加减乘除运算实现乘法分析与解答以 11*14 为例介绍乘法运算的规律 11 的二进制可以表示为 1011 14 的二进制可以表示为 1110二进制相乘的运算过程如下1011 * 1110 ---------- 10110 左移 1 位乘以 0010 101100 左移 2 位乘以 0100 1011000 左移 3 位乘以 1000 ---------- 10011010二进制数 10011010 的十进制表示为 15411*14从这个例子可以看出乘法运算可以转换为加法运算。计算 a*b 的主要思路是 1初始化运算结果为 0 sum0。 2找到 b 对应二进制中最后一个 1 的位置 i位置编号从右到左依次为 0123…并去掉这个 1。 3执行加法操作 sumai。 4循环执行 1、 2和 3步直到 b 对应的二进制数中没有更多的 1 为止。从 6.2 节中可知对 n 执行 nn-1操作可以去掉 n 的二进制数表示中的最后一位 1因此 nn-1的结果为只保留 n 的二进制数中的最后一位 1。因此可以通过 nn-1找出 n中最后一个 1 的位置然后通过 nn-1去掉最后一个 1。在上述的第 2步中首先执行lastBitnn-1得到的值 lastBit 只包含 n 对应的二进制表示中最后一位 1要想确定 1 的位置需要通过对 1 不断进行左移操作直到移位的结果等于 lastBit 时移位的次数就是位置编号。在实现的时候为了提高程序的运行效率可以把 1 向左移动的位数 0123…31先计算好并保存起来。实现代码如下fun multinumber1 Int number2 Int Int { var a number1 var b number2 val neg a 0 xor b 0//结果的正负数标识 //首先计算两个正数相乘的结果最后根据 neg 确定结果的正负 if b 0 b addb.inv 1//-b if a 0 a adda.inv 1//-a var result 0 //key1 向左移位后的值 value移位的次数即位置编号 val bitPosition hashMapOfInt Int //计算出 1 向左移动 012...31位的值 for i in 0..31 bitPosition.put1 shl i i while b 0 { //计算出最后一位 1 的位置编号 val position bitPosition[b and b - 1.inv] result a shl position b b and b - 1 //去掉最后一位 1 } if neg result addresult.inv 1 return result } fun mainargs ArrayString { println3 乘以 4 等于${multi3 4} println3 乘以 7 等于${multi3 7} println3 乘以 9 等于${multi3 9} }引申四另外一种除法的实现方式分析与解答由于除法是乘法的逆运算因此可以很容易地将除法运算转换为乘法运算实现代码如下fun dividenumber1 Int number2 Int Int { var a number1 var b number2 val neg a 0 xor b 0 //结果的是否为负数 //首先计算它们绝对值的除法 if a 0 a -a if b 0 b -b var tmpMulti Int var result 1 while true { tmpMulti multib result if tmpMulti a { result } else { break } } return if neg addresult - 1.inv 1 else result - 1 } fun mainargs ArrayString { println14 除以 4 等于${divide14 4} }