位运算系列
2020-04-17 本文已影响0人
普朗tong
位操作符
& 与运算 两个位都是 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
}
}
