位运算是我们在编程中常会遇到的操作, 但仍然有很多开发者并不了解位运算, 这就导致在遇到位运算时会 "打退堂鼓". 实际上, 位运算并没有那么复杂, 只要我们了解其运算基础和运算符的运算规则, 就能够掌握位运算的知识. 接下来, 我们一起学习位运算的相关知识.
程序中的数在计算机内存中都是以二进制的形式存在的, 位运算就是直接对整数在内存中对应的二进制位进行操作.
注意: 本文只讨论整数运算, 小数运算不在本文研究之列
位运算的基础
我们常用的 3 , 5 等数字是十进制表示, 而位运算的基础是二进制. 即人类采用十进制, 机器采用的是二进制, 要深入了解位运算, 就需要了解十进制和二进制的转换方法和对应关系.
二进制
十进制转二进制时, 采用 "除 2 取余, 逆序排列" 法:
用 2 整除十进制数, 得到商和余数;
再用 2 整除商, 得到新的商和余数;
重复第 1 和第 2 步, 直到商为 0;
将先得到的余数作为二进制数的高位, 后得到的余数作为二进制数的低位, 依次排序;
排序结果就是该十进制数的二进制表示. 例如十进制数 101 转换为二进制数的计算过程如下:
101 % 2 = 50 余 1
50 % 2 = 25 余 0
25 % 2 = 12 余 1
12 % 2 = 6 余 0
6 % 2 = 3 余 0
3 % 2 = 1 余 1
1 % 2 = 0 余 1
逆序排列即二进制中的从高位到低位排序, 得到 7 位二进制数为 1100101 , 如果要转换为 8 位二进制数, 就需要在最高位补 0 . 即十进制数的 8 位二进制数为 01100101 .
其完整过程如下图所示:
有网友整理了常见的进制与 ASCII 码对照表, 表内容如下:
ASCII 控制字符
ASCII 可显示字符
补码
现在, 我们已经了解到二进制与十进制的换算方法, 并拥有了进制对照表. 但在开始学习位运算符之前, 我们还需要了解补码的知识.
数值有正负之分, 那么仅有 0 和 1 的二进制如何表示正负呢?
人们设定, 二进制中最高位为 0 代表正, 为 1 则代表负. 例如 0000 1100 对应的十进制为 12 , 而 1000 1100 对应的十进制为 -12 . 这种表示被称作原码. 但新的问题出现了, 原本二进制的最高位始终为 0 , 为了表示正负又多出了 1 , 在执行运算时就会出错. 举个例子, 1 + (-2) 的二进制运算如下:
- 0000 0001 + 1000 0010
- = 1000 0011
- = -3
这显然是有问题的, 问题就处在这个代表正负的最高位. 接着, 人们又弄出了反码 (二进制各位置的 0 与 1 互换, 例如 0000 1100 的反码为 1111 0011 ). 此时, 运算就会变成这样:
- 0000 0001 + 1111 1101
- = 1111 1110
- # 在转换成十进制前, 需要再次反码
- = 1000 0001
- = -1
这次好像正确了. 但它仍然有例外, 我们来看一下 1 + (-1) :
- 0000 0001 + 1111 + 1110
- = 1111 1111
- = 1000 0000
- = -0
零是没有正负之分的, 为了解决这个问题, 就搞出了补码的概念. 补码是为了让负数变成能够加的正数, 所以 负数的补码 = 负数的绝对值取反 + 1 , 例如 -1 的补码为:
-1 的绝对值 1
- = 0000 0001 # 1 的二进制原码
- = 1111 1110 # 原码取反
- = 1111 1111 # +1 后得到补码
-1 补码推导的完整过程如下图所示:
反过来, 由补码推导原码的过程为 原码 = 补码 - 1, 再求反 . 要注意的是, 反码过程中, 最高位的值不变, 这样才能够保证结果的正负不会出错. 例如 1 + (-6) 和 1 + (-9) 的运算过程如下:
- # 1 的补码 + -6 的补码
- 0000 0001 + 1111 1010
- = 1111 1011 # 补码运算结果
- = 1111 1010 # 对补码减 1, 得到反码
- = 1000 0101 # 反码取反, 得到原码
- = -5 # 对应的十进制
- # 1 的补码 + -9 的补码
- 0000 0001 + 1111 0111
- = 1111 1000 # 补码运算结果
- = 1111 0111 # 对补码减 1, 得到反码
- = 1000 1000 # 反码取反, 得到原码
- = -8 # 对应的十进制
要注意的是, 正数的补码与原码相同, 不需要额外运算. 也可以说, 补码的出现就是为了解决负数运算时的符号问题.
人生苦短 我用 Python.
- 0000 0101
- &
- 0000 1000
- 0000 0101
- &
- 0000 1000
- ---- ----
- 0000 0000
- 0000 0011
- |
- 0000 0111
- 0000 0011
- |
- 0000 0111
- ---- ----
- 0000 0111
- 0000 1100
- ^
- 0000 0111
- 0000 1100
- ^
- 0000 0111
- ---- ----
- 0000 1011
- = 0000 1001 # 补码, 正数补码即原码
- = 1111 1010 # 取反
- = -10
- = 1110 1100 # 补码
- = 0001 0011 # 取反
- = 19
- 5 << 4
- = 0000 0101 << 4
- = 0101 0000 # 高位丢弃, 低位补 0
- = 80
- 80>> 4
- = 0101 0000>> 4
- = 0000 0101 # 正数补 0, 负数补 1
- = 5
- $$
- 80 \div (2)^4
- $$
- $$
- x>> n = x \div (2) ^ n
- $$
- # python
- if 101 % 2:
- print('偶数')
- else:
- print('奇数')
- # python
- if 101 & 1:
- print('奇数')
- else:
- print('偶数')
- # 伪代码
- a = 3, b = 5
- c = a
- a = b
- b = a
- --------
- a = 5, b = 3
- # python
- a, b = 3, 5
- a, b = b, a
- print(a, b)
- # 伪代码
- a = 3, b = 5
- a = a ^ b
- b = a ^ b
- a = a ^ b
- # python
- a, b = 3, 5
- a = a ^ b
- b = a ^ b
- a = a ^ b
- print(a, b)
- #include<stdio.h>
- void main()
- {
- int a = 3, b = 5;
- printf("交换前: a=%d , b=%dn",a,b);
- a = a^b;
- b = a^b;
- a = a^b;
- printf("交换后: a=%d , b=%dn",a, b);
- }
- $$
- x * (2) ^ n
- $$
- # python
- x = 5 # 0000 0101
- for i in range(8):
- print(x>> i & 1)
- if a == x:
- x = b
- else:
- x = a
- # python
- a, b, x = 6, 9, 6
- if a == x:
- x = b
- else:
- x = a
- print(a, b, x)
- # python
- a, b, x = 6, 9, 6
- x = a ^ b ^ x
- print(a, b, x)
- # python
- def search(lis: list, x: int) -> int:
- """ 非递归二分查找
- 返回指定元素在列表中的索引
- -1 代表不存在 """
- mix_index = 0
- max_index = len(lis) - 1
- while mix_index <= max_index:
- midpoint = (mix_index + max_index) // 2
- if lis[midpoint] <x:
- mix_index = mix_index + 1
- elif lis[midpoint]> x:
- max_index = max_index - 1
- else:
- return midpoint
- return -1
- lists = [1, 3, 5, 6, 7, 8, 12, 22, 23, 43, 65, 76, 90, 543]
- res = search(lists, 76)
- print(res)
来源: http://www.tuicool.com/articles/NbIRvey