数据结构与算法XS班-左程云第五节课笔记（位图、位运算实现加减乘除）第5节位图、位运算实现加减乘除

74 阅读 0 评论 49 点赞

我是靠谱客的博主美丽小天鹅，最近开发中收集的这篇文章主要介绍数据结构与算法XS班-左程云第五节课笔记（位图、位运算实现加减乘除）第5节位图、位运算实现加减乘除，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

第5节位图、位运算实现加减乘除

##这是数据结构与算法新手班-左程云第五节课的笔记##

位图

位图的功能？

位图就是用每一位的bit来作图。假设你有一个集合，这个集合可以帮你收集数字，这样的集合有很多，例如HashSet，但是有一个问题，只要进来一个数字，最起码都要占4字节（这还没有算指针啊这些）。我们有一个想法，你这个太浪费空间了。如果你这个集合只让有一个整数，而且这个整数在0-31之间，那么利用32位bit就可以表示这些数字哪些出现哪些没有出现。

扩展：准备32长度的int数组（3232=1024），就可以表示0-1023的数字，但是假如用set存储的话，就要浪费至少102432个bit。
位图的好处？

省空间。

位图的实现？

package class05;
import java.util.HashSet;
public class Code02_BitMap2 {
// 这个类的实现是正确的
public static class BitMap {
private long[] bits;
// 判断需要创建几个long类型
public BitMap(int max) {
// 如果是一个数字，这个数字是0，最起码要申请一个吧。
// >> 6 是除以64
bits = new long[(max + 64) >> 6];
}
public void add(int num) {
// 例如添加数字170，那么我们要看这是第几个long类型负责
// 第0个整数：0-63（第一位管0，第63位管64）
// 第1个整数：64-127
// 第2个整数：128-191（这个管数字170，也就是第三个）
// 怎么判断呢？ 给定的数字/64也就是>>6
// 那么是第几位管呢？0%64就是第0位管，1%64就是第1位管...
// 170%64 = 2....42，第42位表示（第0位是第一个数字）
// 还是看不懂这串吧！我们继续讲
// num % 64 就是 num & 63，也就是把小于64的数字都取出来，这就是余数
// 63 的二进制:(这里还有32位) 00000000 00000000 00000000 000111111
// 170的二进制:(这里还有32位) 00000000 00000000 00000000 010101010
// 结果：(这里还有32位) 00000000 00000000 00000000 000101010
// 为什么这么写？效率高，快10倍是挡不住的
// 1L就是64位的进制表示1，如果是第5位表示，那么就是100000，然后取或就表示出来了
// 必须写1L，要不然会出错！你想想，如果只有32位，你和人家都不等长，很容易出问题啊~
bits[num >> 6] |= (1L << (num & 63));
}
public void delete(int num) {
// 这个好理解，就是先非一下，然后和他与，这样可以保证其他位置不变，只变标志位
bits[num >> 6] &= ~(1L << (num & 63));
}
public boolean contains(int num) {
// 也很好理解！
return (bits[num >> 6] & (1L << (num & 63))) != 0;
}
}
public static void main(String[] args) {
System.out.println("测试开始！");
int max = 10000;
BitMap bitMap = new BitMap(max);
HashSet<Integer> set = new HashSet<>();
int testTime = 10000000;
for (int i = 0; i < testTime; i++) {
int num = (int) (Math.random() * (max + 1));
// 控制概率
double decide = Math.random();
if (decide < 0.333) {
bitMap.add(num);
set.add(num);
} else if (decide < 0.666) {
bitMap.delete(num);
set.remove(num);
} else {
if (bitMap.contains(num) != set.contains(num)) {
System.out.println("Oops!");
break;
}
}
}
for (int num = 0; num <= max; num++) {
if (bitMap.contains(num) != set.contains(num)) {
System.out.println("Oops!");
}
}
System.out.println("测试结束！");
}
}

位运算实现±*/

package class05;
// 测试链接：https://leetcode.com/problems/divide-two-integers
public class Code03_BitAddMinusMultiDiv {
public static int add(int a, int b) {
int sum = a;
while (b != 0) {
sum = a ^ b;
b = (a & b) << 1;
a = sum;
}
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;
b >>>= 1;
}
return res;
}
public static boolean isNeg(int n) {
return n < 0;
}
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 >= 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;
}
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.MAX_VALUE;
} else {
int c = div(add(a, 1), b);
return add(c, div(minus(a, multi(c, b)), b));
}
} else {
return div(a, b);
}
}
}