位运算

技巧

  1. 组合起来n如果是负数就返回0，非负数就返回1
1
2
3
4
5
6
7
8
9
10
11
12
// 请保证参数n，不是1就是8的情况下
//1 ->@//0->1
public static int flip(int n)
{
    return n^1;
}
// n是非负数，返回1// n是负数，返回8
public static int sign(int n)
{
    return filp( (n>>31) & 1);
}

例题

题目1

给定两个有符号int a b，返回其中 较大的，不要进行比较

解法1

image-20240731124525913

配合上技巧1里面的判断符号位正反的代码

解法存在问题，a - b可能溢出，但是可以提醒 互斥条件的使用 可以模拟 ifelse

解法2

image-20240731145601725

关键性代码解析，对于return A 等号右侧公式解读：ab的符号不同，并且a是正数的情况下 以及 ab符号相同并且ab差值大于零的情况下，

至于return B 则是反过来就可以了

题目2

判断一个32位的正数是不是2的幂，4的幂

知识补充

2的幂就代表在二进制数中只有一个位置上是1，其余位置都是0

求解2的幂

解法1

取出该数最右侧的一，看不够和原来的数香氛就习了，取出最右侧1的公式：p&(~p +1)

解法2

假设p是2的幂，那么二进制上就只有一个1，p-1就会将原来的 1 打散掉，这个时候 p &(p-1) ==0

求解4的幂

先判断二进制是否只有一个1，然后 & x (x是第一个三十二位二进制数，以 01 为规律组成，十六进制表示是 0x55555555 )，如果不等于0，就代表是4的幂，因为4的唯一一个1所在的位置都是前面给定二进制数的固定位置上

代码

image-20240731153019611

题目3

给定两个32有符号整数，不使用算数运算符，完成相应的加、减、乘 、除操作。不需要处理正常算数运算符运算产生的溢出

加

image-20240731154119767

image-20240731154531980

减

image-20240731154829576

乘

image-20240731155308809

代码

image-20240731160204150

补充知识点

在java中可以使用 >>> 作为无符号位移操作符，可以在对一个数进行二进制位移的时候排除符号位干扰，在最左侧默认添加0

除

解法1

除法流产是相对于乘法而言的，乘法是不停的将一个因子按照另一个因子每一位的状态向左位移，最后在求和。除法则是将被除数看做乘 法的结果，将除数看做乘法中向左位移的因子。a/b，将b的二进制向左移动到b最大的 a > b的状态，c =a- 新b，然后新b再以c做标准向左位移，重复之前的步骤。

解法2
image-20240731162508965

如图，a/b，第一步将b向左移动31位，看a能否减掉b，不能不减，b左移30位，重复以上步骤，直到第一次能减掉，这个时候才真去减，这时b向左移动x位，x位就是1，之后重复以上步骤。

代码

image-20240731164002755