位运算使用手册 位运算奇技淫巧小结

前言

对位运算做个小结

1、位运算基础

• &：按位与
  如果两个相应的二进制位都为1，则该位的结果值为1，否则为0

• |：按位或
  两个相应的二进制位中只要有一个为1，该位的结果值为1

• ^：按位异或
  若参加运算的两个二进制位值相同则为0，否则为1
  任意数和自身异或结果为0；0和任意数异或结果还是其本身

• ~：取反
  ~是一元运算符，用来对一个二进制数按位取反，即将0变1，将1变0

• <<：左移
  用来将一个数的各二进制位全部左移N位，右补0

• >>：右移
  将一个数的各二进制位右移N位，移到右端的低位被舍弃，对于无符号数， 高位补0

2、位运算技巧

• x >> 1：去掉最后一位，即除以2

• x << 1：最后加个0，即乘以2

• x & 1：判断奇偶，True为奇数，False为偶数

• x | 1：最后一位变成1

• x | (1 << (i - 1))：右数第i位变为1

• x | ((1 << i) - 1)：末i位变为1

• (x | 1) - 1：最后一位变成0

• x & ~(1 << (i - 1))：右数第i位变为0

• x ^ 1：最后一位取反

• x ^ (1 << (i - 1))：右数第i位取反

• x ^ ((1 <<(i) - 1)：末i位取反

• x & ((1 << i) - 1)：取末i位

• x >> (i - 1) & 1：取右数第i位

• x & (x - 1)：最右的第一个1变0

• x & (x + 1)：最右的连续的1变0

• x | (x + 1)：最右的第一个0变1

• x | (x - 1)：最右的连续的0变1

• (x ^ (x + 1)) >> 1：取右边连续的1

• x & (-x)：取右边第一个1到最右

3、例子

1、交换两个数值

a ^= bb ^= aa ^= b

2、找到只出现一次的数
有一个数据列表（2N+1个整数），只有一个数出现了1次，其余N个数都出现了2次
对整个列表进行^运算，空间复杂度为O(1)

3、计算一个数值的二进制数中有多少个1

# 朴素def number1Bit(x):    count = 0    while x:        count += (x & 1)        x = x >> 1    return count# 优化def number1Bit(x):    count = 0    while x:        count = count + 1        x = x & (x-1)    return count

4、判断整数n是否是2的幂次

return N & (N - 1) == 0

5、m的n次幂

def pow(m, n):    res= 1    tmp = m    while n:        if n & 1:            res *= tmp        tmp *= tmp        n = n >> 1    return res

结语

对位运算做了个小结

   红客突击队于2019年由队长k龙牵头，联合国内多位顶尖高校研究生成立。团队从成立至今多次参加国际网络安全竞赛并取得良好成绩，积累了丰富的竞赛经验。红客突击队始终秉承先做人后技术的宗旨，旨在打造国际顶尖网络安全团队。其核心团队于2022年转型于信息安全研究院，并为政企提供安全服务与技术支持。

原文始发于微信公众号（中龙 红客突击队）：位运算使用手册 位运算奇技淫巧小结