位运算系列

位操作符

& 与运算 两个位都是 1 时，结果才为 1，否则为 0，如

1 0 0 1 1   
1 1 0 0 1
------------------------------
1 0 0 0 1

| 或运算 两个位都是 0 时，结果才为 0，否则为 1，如

1 0 0 1 1  
1 1 0 0 1
------------------------------
1 1 0 1 1

^ 异或运算，两个位相同则为 0，不同则为 1，如（可以理解为不进位的加法操作）

1 0 0 1 1  
1 1 0 0 1
-----------------------------
0 1 0 1 0

~ 取反运算，0 则变为 1，1 则变为 0，如

1 0 0 1 1
-----------------------------
0 1 1 0 0

左移运算>>，向左进行移位操作，高位丢弃，低位补 0，如

int a = 8;
a << 3;  
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0100 0000

右移运算<<，向右进行移位操作，对无符号数，高位补 0，对于有符号数，高位补符号位，如

unsigned int a = 8;
a >> 3;
移位前：0000 0000 0000 0000 0000 0000 0000 1000
移位后：0000 0000 0000 0000 0000 0000 0000 0001
​
int a = -8;
a >> 3;
移位前：1111 1111 1111 1111 1111 1111 1111 1000
移位前：1111 1111 1111 1111 1111 1111 1111 1111

常见位运算问题

1.位操作实现乘除法

• 数 a 向右移一位，相当于将 a 除以 2；数 a 向左移一位，相当于将 a 乘以 2

int a = 2;  
a >> 1; ---> 1  
a << 1; ---> 4  

2.位操作交换两数

• 位操作交换两数可以不需要第三个临时变量，虽然普通操作也可以做到，但是没有其效率高

  一个数异或另一个数两次等于没有异或

//普通操作
void swap(int &a, int &b) {
  a = a + b;
  b = a - b;
  a = a - b;
}

//位与操作
void swap(int &a, int &b) {
  a ^= b;
  b ^= a;
  a ^= b;
}

3.位操作判断奇偶数

• 只要根据数的最后一位是 0 还是 1 来决定即可，为 0 就是偶数，为 1 就是奇数

if(0 == (a & 1)) {
 //偶数
}

4.位操作交换符号

• 交换符号将正数变成负数，负数变成正数

int reversal(int a) {
  return ~a + 1;
}  

整数取反加1，正好变成其对应的负数(补码表示)；负数取反加一，则变为其原码，即正数

5.位操作求绝对值

• 整数的绝对值是其本身，负数的绝对值正好可以对其进行取反加一求得，即我们首先判断其符号位（
  整数右移 31 位得到 0，负数右移 31 位得到 -1,即 0xffffffff），然后根据符号进行相应的操作

int abs(int a) {
  int i = a >> 31;
  return i == 0 ? a : (~a + 1);
}

位运算实战技巧系列(Golang实现)

1.技巧1

x & (x - 1) 用于消去x最后一位的1
x = 1100
x - 1 = 1011
x & (x - 1) = 1000

• 用 O(1) 时间检测整数 n 是否是 2 的幂次。
  2的幂
  思路：
  n如果是2的幂次，则n应该满足两个条件
  • n>0
  • n的二进制表示中只有1个1
    代码实现:

func isPowerOfTwo(n int) bool {
        return n > 0 && n&(n-1) == 0
}

• 计算在一个 32 位的整数的二进制表式中有多少个 1。
  二进制表示中质数个计算置位
  思路解析：由n&(n-1)消去最后一位1可知，不断使用 x & (x - 1) 消去x最后一位的1，计算总共消去了多少次即可
  代码实现：

func countPrimeSetBits(L int, R int) int {
    primes := []int{2, 3, 5, 7, 11, 13, 17, 19}
    var res int
    for i := L; i <= R; i++ {
        k := i
        count := 0
        for k != 0 {
            k &= k - 1
            count++
        }
        for __, v := range primes {
            if v == count {
                res++
            }
        }
    }
    return res
} 

• 如果要将整数A转换为B，需要改变多少个bit位？
  思路解析：如果A转化为B，首先获取A和B中二进制表示的bit位不相同的部分(采用异或实现)，然后计算不相同的个数(即1的个数)即为结果

2.技巧2

a ^ b ^ b = a
a ^ a = 0
a ^ 0 = a
异或运算满足交换律和结合律

• 数组中，只有一个数出现一次，剩下都出现两次，找出出现一次的数
  求数组中只出现一次的数字
  思路解析：因为只有一个数恰好出现一个，剩下的都出现过两次，所以只要将所有的数异或起来，就可以得到唯一的那个数。
  代码实现：

func singleNumber(nums []int) int {
    res := 0
    for _, v := range nums {
        res ^= v
    }
    return res
}

• 数组中，只有一个数出现一次，剩下都出现三次，找出出现一次的数
  只出现一次的数字 II
  思路解析：
  (1)采用HashMap做
  (2)采用位运算做
  代码实现:

//采用HashMap
func singleNumber(nums []int) int {
    m := make(map[int]int)
    for _, v := range nums {
        m[v]++
    }
    for k, v := range m {
        if v == 1 {
            return k
        }
    }
    return 0
}

//采用位运算
func singleNumber(nums []int) int {
    res, count := 0, 0
    for i := 0; i < 64; i++ {
        count = 0
        for j := 0; j < len(nums); j++ {
            count += (nums[j] >> i) & 1
        }
        res |= (count) % 3 << i
    }
    return res
}

//采用位运算
func singleNumber(nums []int) int {
    a,b := 0,0
    for _,v := range nums {
        a = (a^v) & ^b
        b = (b^v) & ^a
    }
    return a
}

• 两整数之和
  两整数之和
  思路解析：
  (1)首先计算a^b
  (2)计算a+b产生的进位
  代码实现：

func getSum(a int, b int) int {

    if b == 0 {
        return a
    } else {
        sum := a ^ b
        sum += (a & b) << 1
        return sum
    }
}