之前在 基础 - 异或运算 和 哈希表与哈希函数 - 布隆过滤器 中已经介绍过一些。
比较大小
给定两个有符号 32 位整数 a 和 b，返回 a 和 b 中较大的。
【要求】
不用做任何比较判断。
public class GetMax {/*** 参数只能是 0 或者 1* 0 -> 1* 1 -> 0*/static int flip(int n) {return n ^ 1;}/*** 返回 1 —— n 是非负数* 返回 0 —— n 是负数*/static int sign(int n) {return flip((n >> 31) & 1);}static int getMax1(int a, int b) {/*** 这里有可能会出问题：* a 是一个很大的正数，b 是一个负数 可能会溢出，* 或者 a 是一个很大的负数，b 是一个正数*/int c = a - b;int scA = sign(c); // a > b 返回 1 否则 0int scB = flip(scA);// 如果 a > b 返回 a 否则返回 b，因为 a > b 必有 scA = 1，scB = 0return a * scA + b * scB;}static int getMax2(int a, int b) {int c = a - b;int sa = sign(a);int sb = sign(b);int sc = sign(c);int difSab = sa ^ sb; // a b 的符号不一样为 1，一样为 0int sameSab = flip(difSab); // a b 的符号一样为 1，不一样为 0/*** 返回 a 的条件* a b 符号不同，a 非负返回 1；* a b 符号相同，c 非负返回 1*/int returnA = difSab * sa + sameSab * sc;int returnB = flip(returnA);return a * returnA + b * returnB;}public static void main(String[] args) {int a = -1;int b = 1;System.out.println("a : " + a);System.out.println("b : " + b);System.out.println("较大的是：" + getMax1(a, b));System.out.println("较大的是：" + getMax2(a, b));a = 1;b = Integer.MIN_VALUE;System.out.println("a : " + a);System.out.println("b : " + b);System.out.println("较大的是：" + getMax1(a, b) + "\t 这里是由于溢出导致的错误");System.out.println("较大的是：" + getMax2(a, b));}}
结果
a : -1
b : 1
较大的是：1
较大的是：1
a : 1
b : -2147483648
较大的是：-2147483648 这里是由于溢出导致的错误
较大的是：1
2 的幂
判断一个32位正数是不是 2 的幂、4 的幂
2 的幂：二进制中只有一个 1。可以用如下方法判断：
- 方法一：取最右侧的 1 后是否和原数相同，如果相同就说明只有一个 1
- 方法二：假设 该数为 X，判断 (X - 1) & X 是否为 0，如果为 0 就说明是只有一个 1
4 的幂，步骤：
- 是 4 的幂就必须是 2 的幂，先判断是不是 2 的幂
如果是 2 的幂，就和
...01010101做 与 操作，如果是 0 就说明是 4 的幂。因为 4 的幂必须是1，100，10000…… 1 的位置都是在下标为 0、2、4 位置上public class Power { static boolean is2Power1(int n) { return (n & (~n + 1)) == n; } static boolean is2Power2(int n) { return ((n - 1) & n) == 0; } static boolean is4Power(int n) { return is2Power1(n) && (n & 0x55555555) != 0; } public static void main(String[] args) { int a = 4; int b = 8; int c = 3; System.out.println(a + " 是 2 的幂 " + is2Power1(a)); System.out.println(b + " 是 2 的幂 " + is2Power1(b)); System.out.println(c + " 是 2 的幂 " + is2Power1(c)); System.out.println(a + " 是 2 的幂 " + is2Power2(a)); System.out.println(b + " 是 2 的幂 " + is2Power2(b)); System.out.println(c + " 是 2 的幂 " + is2Power2(c)); System.out.println(a + " 是 4 的幂 " + is4Power(a)); System.out.println(b + " 是 4 的幂 " + is4Power(b)); System.out.println(c + " 是 4 的幂 " + is4Power(c)); } }结果
4 是 2 的幂 true 8 是 2 的幂 true 3 是 2 的幂 false 4 是 2 的幂 true 8 是 2 的幂 true 3 是 2 的幂 false 4 是 4 的幂 true 8 是 4 的幂 false 3 是 4 的幂 false
加减乘除
给定两个有符号 32 位整数 a 和 b，不能使用算术运算符，分别实现 a 和 b 的加、减、乘、除运算
【要求】
如果给定 a、b 执行加减乘除的运算结果就会导致数据的溢出，那么你实现的函数不必对此负责，除此之外请保证计算过程不发生溢出
思路：
首先明确两个运算：
- 异或运算：
a^b的结果是 a、b 两数无进位相交。 - 与运算：
(a&b) << 1的结果是 a、b 两数相交后需要的进位
加运算其实就是 无进位相加结果 + 进位 = a^b + ((a&b)<<1)，如十进制中，13+8 = 无进位结果 11 + 进位 10 = 21。在二进制中也是一样
那么加运算就可以这样执行，如 13+8 ：
01101 + 01000= 无进位结果01001+ 进位1000001001 + 10000= 无进位结果11001+ 进位00000，此时，进位为0，无进位结果就是相加的结果 21
代码实现如下：
static int add(int a, int b) {
while (b != 0) {
int c = a;
a = a ^ b;
b = (c & b) << 1;
}
return a;
}
减法思路：
13-8 = 13 + (-8)，减一个数就是加上这个数的相反数。
X 的相反数：~X + 1
相反数的意义都是指：该数+该数的相反数=0。比如 0000 0011 + 它的相反数 = 0000 0000 ，那么 0000 0011的相反数=0000 0000 - 0000 0011 = 1111 1101，直观上理解就是一个数的相反数=对该数按位取反再加1。
从理论推导一下：对于某个不为 0 的二进制数来说，该数+它的相反数=0000 0000，那么该结果一定是由于进位溢出造成的（用二进制相加看，不要用十进制看），相当于1111 1111 + 0000 0001 = 0000 0000，用未溢出的值代替0000 0000，即 该数 + 它的相反数 = 1111 1111 + 0000 0001，—> 它的相反数 = 1111 1111 - 该数 + 0000 0001，1111 1111 - 该数 就相当于对该数按位取反，所以二进制数的相反数就是对其按位取反加1。
代码实现如下：
// 获取相反数、 负数补码
public static int negNum(int n) {
return add(~n, 1);
}
// 减法
static int minus(int a, int b) {
return add(a, negNum(b));
}
乘法思路：
二进制乘法和十进制一样，将 a 的每一位和 b 的每一位数相乘后相加。
可以发现，在二进制中，每次都是乘 1 或者是乘 0，这样就更加简单了，只需要将 b 每次都向右移一位、a 左移一位，末位如果是 0 就不做处理，如果是 1 就将 a 累加
代码实现：
static int multi(int a, int b) {
if (a == 0 || b == 0) return 0;
int res = 0;
while (b != 0) {
if ((b & 1) != 0) { // 末位为 1
res = add(res, a);
}
a <<= 1;
b >>>= 1;
}
return res;
}
除法思路：
我们常用的竖式除法，如下：123 ÷ 2
步骤：
- 被除数最高位百位 1 < 2 略过
- 十位 12 > 2，可以计算 12 ÷ 2 = 6，商的十位上是 6
- 个位 3 > 2，可以计算 3 ÷ 2 = 1，商的个位上是 1
- 个位计算完成，得出结果为 61
上面的步骤可以总结为：
被除数从高位到低位遍历，如果该位置上的数为 num
- num < 除数 —— 略过
- num >= 除数 —— 进行计算，计算的逻辑为
num - 除数 * n = 余数这里的 n 就位该位置的商- 将上一步得到的余数和被除数的下一位合并为新的 num
这些逻辑也可以用到二进制计算中：
每次都除数向左位移 n 位，得到结果 结果_1（就相当于上面十进制的 除数*n），让被除数减去 结果_1 得到新的被除数
代码实现
public class AddMinusMultiDivideByBit {
// 负数补码
public static int negNum(int n) {
return add(~n, 1);
}
static int add(int a, int b) {
while (b != 0) {
int c = a;
a = a ^ b;
b = (c & b) << 1;
}
return a;
}
static boolean isNeg(int n) {
return n < 0;
}
// 减法
public static int minus(int a, int b) {
return add(a, negNum(b));
}
static int multi(int a, int b) {
if (a == 0 || b == 0) return 0;
int res = 0;
while (b != 0) {
if ((b & 1) != 0) { // 末位为 1
res = add(res, a);
}
a <<= 1;
b >>>= 1;
}
return res;
}
// 除法运算
static int div(int a, int b) {
int x = isNeg(a) ? negNum(a) : a;
int y = isNeg(b) ? negNum(b) : b;
int res = 0;
for (int i = 31; i >= 0; i = minus(i, 1)) {
if ((x >> i) >= y) {
res |= (1 << i);
x = minus(x, y << i);
}
}
return isNeg(a) ^ isNeg(b) ? negNum(res) : res;
}
static int divide(int a, int b) throws Exception {
if (b == 0) {
throw new Exception("除数不能为 0");
}
if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
return 1;
} else if (b == Integer.MIN_VALUE) {
return 0;
} else if (a == Integer.MIN_VALUE) {
// 这段没看懂
int res = div(add(a, 1), b);
return add(res, div(minus(a, multi(res, b)), b));
} else {
return div(a, b);
}
}
}
若有收获，就点个赞吧
0 人点赞
