剑指offer-位运算

秋招,来了!

二进制中 1 的个数

题目描述

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

题解 1

  在计算机系统中,数值都是用补码来表示和存储的。而原码就是数值的二进制数表示,最高位1表示负数。补码:正数的补码是其原码本身;负数的补码是其绝对值的原码最高位符号位不变,其它位取反,再加1。例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
3的原码:
00000000000000000000000000000011(32位)
-1的原码:
10000000000000000000000000000001(32位)
3的补码(正数的补码是其原码本身):
00000000000000000000000000000011
-1的补码(原码最高位符号位不变,其它位取反):
11111111111111111111111111111110
再加1:
11111111111111111111111111111110 + 1
得:
11111111111111111111111111111111
使用补码的好处在于,可以将符号位和数值位统一处理,加法与减法也可以统一处理。例如,3-1等价于3+(-1) ,对于计算机来说将3和-1的补码直接相加就可以:
3 + (-1) =
00000000000000000000000000000011 +
11111111111111111111111111111111
00000000000000000000000000000010 = 2 (最高位的1溢出了,直接丢弃)

  这个题目可以通过将 n 不断右移,然后和1相与判断最低位是否是1,从而实现求 1 的个数。

1
2
3
4
5
6
7
8
9
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
cnt = 0
while n:
if n & 1:
cnt = cnt + 1
n = n >> 1
return cnt

  但是,要注意,由于负数的最高位总要设为 1,右移操作最终会变为 0xffffffff 而陷入死循环。因此,利用 n & 0xffffffff 将负数 n 转化为正数,而它们的二进制形式是相同的,而对正数的二进制进行操作非常简单清晰,统计到这个正数二进制形式中1的个数就是原来负数的二进制形式中1的个数,这样就可以消除负数的影响。

1
2
3
4
5
6
7
8
9
10
11
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
cnt = 0;
if n < 0: # 得到负数的补码
n = n & 0xffffffff
while n:
if n & 1:
cnt = cnt + 1
n = n >> 1
return cnt
题解 2

  如果一个整数不为 0,那么这个整数至少有一位是 1。如果我们把这个整数减 1,那么原来处在整数最右边的1 就会变为 0,原来在 1 后面的所有的 0 都会变成 1 (如果最右边的 1 后面还有 0 的话)。其余所有位将不会受到影响。例如,二进制数1100,从右边数起第三位是处于最右边的1。减去 1 后,第三位变成 0,它后面的两位 0 变成了 1,而前面的 1 保持不变,因此得到的结果是 1011。

  我们发现减 1 的结果是把最右边的一个 1 开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算,从原来整数最右边一个 1 那一位开始所有位都会变成 0。如 1100&1011=1000。也就是说,把一个整数减去 1,再和原整数做与运算,会把该整数最右边一个 1 变成0。那么一个整数的二进制有多少个1,就可以进行多少次这样的操作。

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
cnt = 0
while n != 0:
cnt += 1
n = n & (n-1)
return cnt

  同样,需要考虑负数的情况:

1
2
3
4
5
6
7
8
9
10
# -*- coding:utf-8 -*-
class Solution:
def NumberOf1(self, n):
cnt = 0
if n < 0: # 得到负数的补码
n = n & 0xffffffff
while n:
n = n & (n - 1)
cnt += 1
return cnt

数值的整数次方

题目描述

  给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

题解 1

  直接

1
2
3
4
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
return base ** exponent

  当指数为负数的时候:可以先对指数求绝对值,然后算出次方的结果之后再取倒数。

1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
n = abs(exponent)
result = 1
for i in range(n):
result = result*base
if exponent < 0:
result = 1.0/result
return result
题解 2

  快速幂,使用位运算:

  • &运算:通常用于二进制取位操作,例如一个数x & 1 的结果就是取二进制的最末位的值。还可以判断这个数的奇偶性,如果x&1==0,则x为偶数;如果x&1==1,则x为奇数。
  • >>运算:在这里是作为除法来使用,例如一个数x,x >> 1就表示x右移一位,即x=x/2。
1
2
3
4
5
6
例如,求2^11:
11的二进制表示1011,因此,10可以转化为:1*2^0 + 1*2^1 + 0*2^2 + 1*2^3
2^11可以转化为:
2^(1*2^0 + 1*2^1 + 0*2^2 + 1*2^3)
得到:
2^(2^0) * 2^(2^1) * 2^(2^3)

  代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# -*- coding:utf-8 -*-
class Solution:
def Power(self, base, exponent):
n = abs(exponent)
ans = 1
while n:
if n & 1:
ans = ans * base
base = base * base
n = n >> 1
if exponent < 0:
return 1.0 / ans
else:
return ans

  分析:

1
2
3
4
5
6
7
8
9
10
1011:
ans=2, base=2^2, 右移1位:0101
0101:
ans=2*2^2, base=2^4, 右移1位:0010
0010:
base=2^8, 右移1位:0001
0001:
ans=2*2^2*2^8, base=2^16, 右移1位:0000
最终:
ans=2*2^2*2^8

数组中只出现一次的数字

题目描述

  一个整型数组里除了两个数字之外,其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

题解 1

  遍历数组,用哈希表来进行计数,最后从哈希表中找出计数为 1 的数即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
dic = {}
for i in array:
if i in dic:
dic[i] += 1
else:
dic[i] = 1
result = []
for k, v in dic.items():
if v == 1:
result.append(k)
return result
题解 2

  利用异或的特性:异或运算中,任何一个数字和自己本身异或都是 0,任何一个数字和 0 异或都是本身。这个特性能够找出只有一个数出现一次的情况。而现在的问题是,除了有两个数字只出现了一次,其他数字都出现了两次。

  因此,如果尝试把原数组分成两个子数组,且刚好每个子数组中各自包含一个只出现一次的数字。则在该前提下,每个子数组中,只有一个数字出现了一次,其他数字都出现了两次。针对每个子数组,从头到尾依次异或每个数字,则最后留下来的就是只出现了一次的数字。因为出现两次的都抵消掉了。

  那么,怎样实现子数组的划分呢?若对原数组从头到尾的进行异或,则最后得到的结果就是两个只出现一次的数字的异或运算结果。这个结果的二进制表示中,至少有一位为1,因为这两个数不相同。该位记为从最低位开始计数的第 n 位。那么,分组的标准定为从最低位开始计数的第 n 位是否为 1。因为出现两次的同一个数字,各个位数上都是相同的,所以一定被分到同一个子数组中,且每个子数组中只包含一个出现一次的数字。

  举个例子:数组元素为 [2, 4, 3, 6, 3, 2, 5, 5],异或的结果为 0010,也就是倒数第二位为 1,也就是倒数第二位为标记位来进行拆分,那么第一个子数组就为 [2, 3, 6, 3, 2],他们的倒数第二位为 1,第二个子数组为 [4, 5, 5] 倒数第二位为 0,对这两个子数组分别再异或,最终找到 6 和 4。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# -*- coding:utf-8 -*-
class Solution:
# 返回[a,b] 其中ab是出现一次的两个数字
def FindNumsAppearOnce(self, array):
tmp = array[0]
for i in range(1, len(array)):
tmp ^= array[i]
index = 0
while tmp & 1 == 0:
tmp >>= 1
index += 1
a = 0
b = 0
for j in array:
if (j >> index) & 1 == 1:
a ^= j
else:
b ^= j
return a, b
坚持原创技术分享,您的支持将鼓励我继续创作!