济宁网站建设 企诺,外国老头做中文网站,vscode网页设计教程,wordpress 简洁文章主题位图
一个int类型32字节#xff0c;可以表示0-31这32个数出没出现过#xff0c;出现过1没出现0#xff0c;再扩大一点搞个数组#xff0c;就可以表示0-1023出没出现过#xff0c;一个long类型可储存64位
如何把10位组成的数#xff0c;第四位由1改成零 package class05…位图
一个int类型32字节可以表示0-31这32个数出没出现过出现过1没出现0再扩大一点搞个数组就可以表示0-1023出没出现过一个long类型可储存64位
如何把10位组成的数第四位由1改成零 package class05;import java.util.HashSet;public class Code01_BitMap1 {public static class BitMap {private long[] bits;public BitMap(int max) {bits new long[(max 64) 6];//右移6位就是÷64的意思} //要准备多少个long就是(max 64) 6个public void add(int num) {//num÷64定位到是第几个整数num%64定位到是第几个整数的第几位//而%64等价于63只保留n的后七位0-63前面的63后全为0bits[num 6] | (1L (num 63));//不能1左移32位1默认是整形32位必须是1L}//删除public void delete(int num) {bits[num 6] ~(1L (num 63));//1左移这么些位然后取反然后和n做与运算}//有没有某个数这一位不是0就存在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);//申请一个mapHashSetInteger set new HashSet();//申请一个哈希set然后这俩作比较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(测试结束);}}1.快速写出46的二进制形式46321432842101110
2^异或运算等价于二进制无进位相加
3.ab得到的结果1位得到进位信息
故a46,b20c两者无进位相加结果d等于进位信息
c0101110^0010100011101058
dab10000100100010008,cd66ab
但是违规了本能用加号所以要一直递归直到进位信息为零
那a-badd(a,add(~b1)),a(-b)
乘法
a*b从右往左看b的二进制位是1把a抄下来是0不抄下来a后面补一个零左移1位循环 除法
1.要用右移左移会导致数据符号位改变
2.x右移i位i30.29...5,xy说明第i位上要放0x4,xy停第四位 置1然后当前的x-y即x-y4
3.如何回避掉系统最小值无法转成绝对值问题举例假设系统最小值是-15我要计算-15/3
-151-14-14/3-4然后-15--4*3计算差值得-3然后-3/3得到-1把他和-4相加
a/b- (a1)/bc -a-(b*c)d - d/be -ce 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;//进位信息b-ba sum;//a-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) {//最末尾有1res add(res, a);//接受此时的a}a 1;//a后面补一个零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;//先把ab设置成正数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);}}//返回如果ab符号不一样加个负号再返回return isNeg(a) ^ isNeg(b) ? negNum(res) : res;}
//系统最小值无法转成绝对值负数比正数多一个比如最小是-10而最大是9分类讨论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);}}}
