算法很美(蓝桥) | 位运算的奇技淫巧

我有话说

前阵子跑去面试,有家公司是做电商广告数据分析的,很有意思,上来先做了三道算法题(答得不好),然后面试官花了很长时间为我解答了三道题目,一度让我以为已经是这家公司的员工了。临了,征求了下面试官对我的建议,“不是科班出身(我本科学的物理),计算机基础和算法是偏弱些,这两块要好好打磨打磨。”

前言

在学习算法很美课程的时候,学习到了一些位运算的奇技淫巧,收录在此

判断奇偶数

判断奇数1 & x == 1

1
System.out.println((1991 & 1) == 1);

判断偶数1 & x == 0

1
System.out.println((1990 & 1) == 0);

获取二进制数x位y是1还是0

将x右移y - 1位,与1

1
2
3
4
int x = 0b010110010;
int y = 5;
int res = (x >> (y - 1)) & 1;
System.out.println(res);

交换两个整数变量的值

不用判断语句,求整数的绝对值

异或,可以理解为不进位加法,1 + 1 = 0,0 + 0 = 0,1 + 0 = 1

异或的性质

  • 交换律:可任意交换运算因子的位置,结果不变
  • 结合律:即(a ^ b)^ c == a ^ ( b ^ c )
  • 对于任何数x,都有x ^ x = 0, x ^ 0 = x,同自己求异或为0,同0求异或为自己
  • 自反性:A ^ B ^ B = A ^ 0 = A,连续和同一个因子做异或运算,最终结果为自己
1
2
3
4
int a = -100;
// a为正数,a >> 31 = 00000000 00000000 00000000 00000000,求绝对值就是自己
// a为负数,a >> 31 = 11111111 11111111 11111111 11111111,求绝对值就是自己 * -1(00000000 00000000 00000000 00000001)
System.out.println((a + (a >> 31) ^ (a >> 31)));

这边课程讲的不是很明白,可以参考下位运算求整数的绝对值,写的很好。