位運(yùn)算 Bitwise operation
前言
日常提出疑問，然后引出今天的下文：
- 如何在代碼里不用 “+” 、“-” 實(shí)現(xiàn)加減法的操作？
接下來我就介紹一項(xiàng)一招制敵的技能 —— 位運(yùn)算
正文
什么是位運(yùn)算
程序中的所有數(shù)在計(jì)算機(jī)內(nèi)存中都是以二進(jìn)制的形式存儲(chǔ)的。位運(yùn)算（Bitwise operation）就是直接對(duì)整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行操作，因此其執(zhí)行效率非常高。
在程序中使用位運(yùn)算進(jìn)行操作，會(huì)大大提高程序的性能。
位運(yùn)算的本質(zhì)
位運(yùn)算是在二進(jìn)制之間操作，粗略地說就是 0 和 1 之間的轉(zhuǎn)換
位運(yùn)算的基本操作
與運(yùn)算 &
兩個(gè)位都是 1 時(shí)，結(jié)果才為 1
1 & 1 = 1
1 & 0 = 0
100 & 001 = 0
100 & 101 = 100
或運(yùn)算 |
兩個(gè)位都是 0 時(shí)，結(jié)果才為 0，否則為 1
// 二進(jìn)制
1 | 0 = 1
100 | 001 = 101
異或運(yùn)算^
又稱不進(jìn)位加法，兩個(gè)位相同則為 0，不同則為 1
// 二進(jìn)制
1 ^ 1 = 0
1 ^ 0 = 1
100 ^ 001 = 101
101 ^ 001 = 100 // 如果這里是加法的話，末尾 1 + 1 應(yīng)該等于 0， 并向前進(jìn) 1
// 異或運(yùn)算中，這里只等于 0 ， 未向前進(jìn) 1， 所以叫不進(jìn)位加法
取反運(yùn)算 ~
又稱非操作，0 則變?yōu)?1，1 則變?yōu)?0（在 golang里, 可以用 ^1進(jìn)行取反操作）
// 二進(jìn)制
~1 = 0
~0 = 1
左移運(yùn)算 <<
向左進(jìn)行移位操作，高位丟棄，低位補(bǔ) 0； 左移 1 位相當(dāng)于乘 2， 左移 n 位相當(dāng)于乘 2 的 n 次方，
左移通常用作乘法操作
// 二進(jìn)制
101 << 1 = 1010
101 << 2 = 10100
// 整型
3 << 1 = 6
3 << 2 = 12
右移運(yùn)算 >>
向右進(jìn)行移位操作，對(duì)無符號(hào)數(shù)，高位補(bǔ) 0，對(duì)于有符號(hào)數(shù)，高位補(bǔ)符號(hào)位；右移 1 位相當(dāng)于除 2， 右移 n 位相當(dāng)于除 2 的 n 次方，
右移通常用作除法操作
// 二進(jìn)制
1000 >> 1 = 100
1000 >> 2 = 10
// 整型
8 >> 1 = 4
8 >> 2 = 2
實(shí)戰(zhàn)位運(yùn)算要點(diǎn)
下面介紹幾個(gè)常用的方法
判斷奇偶
奇：(x&1) == 1; 偶： (x&1) == 0
def and_example(x):
if x & 1 == 0:
print("偶數(shù)")
if x & 1 == 1:
print("奇數(shù)")
除二
x >> 1
def average(m, n):
return (m + n) >> 1
清零最低位的 1
x=x&(x-1)
// 二進(jìn)制
x = 1010
x&(x-1) = 1000
得到最低位的 1
x&-x
// 二進(jìn)制
x = 1010
-x = 0110 // 這里可以了解一下二進(jìn)制中負(fù)數(shù)表示方法
x&-x = 0010
歸零
x &~x
// 二進(jìn)制
x = 1010
x&~x = 0000
解答開篇問題
1. 位操作實(shí)現(xiàn)加法
- 二進(jìn)制加法中，可以使用
^進(jìn)行不進(jìn)位加法運(yùn)算 - 如果需要的話，將計(jì)算的數(shù)向前進(jìn) 1
整體流程如上圖，請(qǐng)參照下面代碼加以思考：
def add(m, n): # m + n
if m & n == 0: return n | m # return 非 0 的數(shù)
return add(m ^ n, (m & n)<< 1) # m & n 來確定相加的 1 的位置
2. 位操作實(shí)現(xiàn)減法
- 二進(jìn)制加法中，可以使用
^進(jìn)行減法 - 如果需要的話，將計(jì)算的數(shù)向前面數(shù)借 1
整體流程如上圖，請(qǐng)參照下面代碼加以思考：
def sub(m, n): # m - n
if n == 0: return m
return sub(m ^ n, (~m & n) << 1) # (~m & n) << 1 來找到借的 1 的位置
最后
文中如有表述不清之處，請(qǐng)?jiān)谙旅媪粞裕視?huì)第一時(shí)間進(jìn)行完善。
編者希望能給大家?guī)砀鄡?yōu)質(zhì)的文章；上述內(nèi)容你覺得還可以的話，請(qǐng)幫我點(diǎn)個(gè)贊，謝謝!
