左神算法新手班课程学习笔记05
纳西妲首席爹粉
2023-01-08 23:06
阅读1929
#算法#
//++++++++++++++++++++++++++++++++++++++++++++++
05 位图、位运算实现加减乘除
内容：
位图
好处：节省空间（整型4字节）例如：一个整数32位，可以通过标记第N位来表示N出现，所以一个整数最多可以表现0—31是否出现。利用int[32]可以表现最大1024的数是否出现过。
功能：如果最大值能够确定，可以收集数据并且返回是否出现的结果。
位运算使用的进一步学习：实现加减乘除
- 异或运算相当于无进位相加。与运算结果向左移动一位就是进位信息（都为1时结果才得一，然后左移一位为进位），所以加法的结果就等于异或运算加上进位信息。
题目：
现场写位图的code、讲解
public static class BitMap{
//改成long，每一位能够表示最大63
private long[] bits;
public BitMap(int max){
//右移6位 -> 除以64
//bits ->至少准备的个数
//本质是扣边界
bits = new long[(max + 64) >> 6]
}
public void add(int num){
//（位运算速度比加减乘除快得多）
// 通过右移6位（代替/64）来确定出现在第几个整数上
//只保留前七位，通过&63来实现，可以替代%64
//通过将1左移相应的位置再与其进行或的位运算，在num所对应的位置成功标上了1
bits[num >> 6] |= (1L << (num &63))
}
public void delete(int num){
//（位运算速度比加减乘除快得多）
// 通过右移6位（代替/64）来确定出现在第几个整数上
//只保留前七位，通过&63来实现，可以替代%64
//通过将1左移相应的位置然后将其取反，再与其进行与的位运算，在num所对应的位置成功标上了0
bits[num >> 6] &= ~(1L << (num &63))
}
public boolean contains(int num){
return (bits[num >> 6] & (1L << (num & 63))) != 0;
}
}
位运算的加减乘除
//加法
public static int add(int a, int b){
int sum = a;
while(b != 0 ){
sum = a ^ b;//无进位加法
b = (a & b) << 1;//b不断变成进位信息
a = sum;//a不断变成无进位相加信息
}
return sum;
}
//给一个数加上负号
public static int negNum(int n){
return add(~n,1);
}
//减法
public static int minus(int a, int b){
return add(a,negNum(b));
}
//乘法
public static int multi(int a, int b){
int res = 0;
while(b != 0){
if((b & 1) != 0){
res = add(res,a);
}
a <<= 1;//每次向左移位，即后面加0
b >>>= 1;//每次循环向右移位。即最后面的数被抹去
}
return res;
}
//除法
public 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 = 30; i >= 30; i = minus(i,1)){
if((x >> i) >= y){
res |= (1 << i);
x = minus(x,y << i);
}
}
return isNeg(a) != isNeg(b) ? negNum(res): res;
}
//考虑系统最小值
public static int divide(int a, int b){
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){
if(b == negNum(1)){
return Integer.MIN_VALUE;
}
else{
//因为系统最小值是没有相反数的，只能迂回。首先系统最小值a加一再除以b得到c。a再减去b与c的乘积得到d。d再除以b得到e。c和相加得到最终结果。
int ans = div(add(a,1),b);
return add(c,div(minus(a,mutil(c,b)),b));
}
}else{
return div(a,b);
}
}
评论
问答助学
相关内容
0个评论
全部评论
点击登录，快来和大家讨论吧～
表情
图片
暂无评论
