位运算 Bitwise operation
前言
日常提出疑问，然后引出今天的下文：
- 如何在代码里不用 “+” 、“-” 实现加减法的操作？
接下来我就介绍一项一招制敌的技能 —— 位运算
正文
什么是位运算
程序中的所有数在计算机内存中都是以二进制的形式存储的。位运算（Bitwise operation）就是直接对整数在内存中的二进制位进行操作，因此其执行效率非常高。
在程序中使用位运算进行操作，会大大提高程序的性能。
位运算的本质
位运算是在二进制之间操作，粗略地说就是 0 和 1 之间的转换
位运算的基本操作
与运算 &
两个位都是 1 时，结果才为 1
1 & 1 = 1
1 & 0 = 0
100 & 001 = 0
100 & 101 = 100
或运算 |
两个位都是 0 时，结果才为 0，否则为 1
// 二进制
1 | 0 = 1
100 | 001 = 101
异或运算^
又称不进位加法，两个位相同则为 0，不同则为 1
// 二进制
1 ^ 1 = 0
1 ^ 0 = 1
100 ^ 001 = 101
101 ^ 001 = 100 // 如果这里是加法的话，末尾 1 + 1 应该等于 0， 并向前进 1
// 异或运算中，这里只等于 0 ， 未向前进 1， 所以叫不进位加法
取反运算 ~
又称非操作，0 则变为 1，1 则变为 0（在 golang里, 可以用 ^1进行取反操作）
// 二进制
~1 = 0
~0 = 1
左移运算 <<
向左进行移位操作，高位丢弃，低位补 0； 左移 1 位相当于乘 2， 左移 n 位相当于乘 2 的 n 次方，
左移通常用作乘法操作
// 二进制
101 << 1 = 1010
101 << 2 = 10100
// 整型
3 << 1 = 6
3 << 2 = 12
右移运算 >>
向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位；右移 1 位相当于除 2， 右移 n 位相当于除 2 的 n 次方，
右移通常用作除法操作
// 二进制
1000 >> 1 = 100
1000 >> 2 = 10
// 整型
8 >> 1 = 4
8 >> 2 = 2
实战位运算要点
下面介绍几个常用的方法
判断奇偶
奇：(x&1) == 1; 偶： (x&1) == 0
def and_example(x):
if x & 1 == 0:
print("偶数")
if x & 1 == 1:
print("奇数")
除二
x >> 1
def average(m, n):
return (m + n) >> 1
清零最低位的 1
x=x&(x-1)
// 二进制
x = 1010
x&(x-1) = 1000
得到最低位的 1
x&-x
// 二进制
x = 1010
-x = 0110 // 这里可以了解一下二进制中负数表示方法
x&-x = 0010
归零
x &~x
// 二进制
x = 1010
x&~x = 0000
解答开篇问题
1. 位操作实现加法
- 二进制加法中，可以使用
^进行不进位加法运算 - 如果需要的话，将计算的数向前进 1
整体流程如上图，请参照下面代码加以思考：
def add(m, n): # m + n
if m & n == 0: return n | m # return 非 0 的数
return add(m ^ n, (m & n)<< 1) # m & n 来确定相加的 1 的位置
2. 位操作实现减法
- 二进制加法中，可以使用
^进行减法 - 如果需要的话，将计算的数向前面数借 1
二进制减法示意图.jpg
整体流程如上图，请参照下面代码加以思考：
def sub(m, n): # m - n
if n == 0: return m
return sub(m ^ n, (~m & n) << 1) # (~m & n) << 1 来找到借的 1 的位置
最后
文中如有表述不清之处，请在下面留言，我会第一时间进行完善。
编者希望能给大家带来更多优质的文章；上述内容你觉得还可以的话，请帮我点个赞，谢谢!
网友评论