剑指刷题8

发表于 | 分类于 ，

面试题15： 二进制中的1的个数

题目：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

解题思路：把一个整数减去1之后和原来的整数做位于运算。得到的结果相当于把整数的二进制表示中最右边的1变成0。然后注意python的负数补码是无限的···，所以要先和32位的1做与运算。

代码：

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def NumberOf1(self, n):
        # write code here

        count = 0
        if n < 0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = (n - 1) & n
        return count

代码思路：先处理掉负数死循环的情况（只对python来说），然后用解题思路的做法来计算1的数量。

还有一个要记住的：如果一个整数和1做与运算的结果是1，则表示该整数的最右边一位是1，否则是0。

面试题16: 数值的整数次方

题目：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0

解题思路：这种题目看似简单，但实际上主要考察的是代码的完整性，之所以觉得简单是因为题目的功能实现简单，但是完整的代码应该考虑到所有可能的输入情况，就是代码的完整性。（有一种情况是错的，底数为0，指数为负数），其他情况有：指数为负数。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def __init__(self):
        self.g_InvalidInput = False
    def Power(self, base, exponent):
        # write code here
        self.g_InvalidInput = False
        if base is 0.0 and exponent < 0:
            g_InvalidInput = True
            return 0.0
        absExponent = exponent
        if exponent < 0:
            absExponent = -exponent
        result = self.PowerWithUnsignedExponent(base, absExponent)
        if(exponent <0):
            result = 1.0/result
        return result
    def PowerWithUnsignedExponent(self, base, exponent):
        if exponent == 0:
            return 1
        if exponent == 1:
            return base
        result = self.PowerWithUnsignedExponent(base, exponent >> 1)
        result *= result
        if exponent & 0x1 == 1:
            result *= base
        return result

算法解析：算法考虑将指数先变成绝对值，在之后根据指数是否是负数来处理。然后主要的实现放到另一个函数中实现。用了递归来加快指数运算。依据如下：

用了右移来取代除以2，用位与运算符代替求余运算符（%）（这个用了如果一个整数和1做与运算的结果是1，则表示该整数的最右边一位是1，否则是0。）

请作者喝杯咖啡吧！