位运算
其实java底层jvm中是有一定的汇编语言 在java中用加减乘除比在java中用位运算拼出加减乘除更快
整数大小是4字节
字节也叫Byte，是计算机数据的基本存储单位，在电脑里一个中文字占两个字节。8bit(位) = 1Byte(字节)1024Byte(字节) = 1KB1024KB = 1MB1024MB = 1GB1024GB = 1TB其中：K是千,M是兆,G是吉咖,T是太拉。
1int = 4Byte = 32位
arr[32] = 1024位 表示: 一个长度为32的数组可以表示1024个数
1long = 8Byte = 64位
long[10] = 640位 可以表示640个数
位图操作
public class Code02_BitMap2 {
// 这个类的实现是正确的
public static class BitMap {
private long[] bits;
public BitMap(int max) {
bits = new long[(max + 64) >> 6];
}
//求该数属于第几个数组
//向右移动六位: (max + 64) >> 6 -> (max + 64) / 64 :表示第几个整数
public void add(int num) {
bits[num >> 6] |= (1L << (num & 63));
}
//在位图里添加一个数:
//num % 64 == num & 63: 表示该整数的第几位(从右往左数)
//1.把num所在的位数求出来
//2.把1左移以上位数
//3.或进去
//4.就可以标记第num的位置为1
public void delete(int num) {
bits[num >> 6] &= ~(1L << (num & 63));
}
//在位图中删除一个数:
//1.将1左移整数所对应位数
//2.取反
//3.与进去
//4.就可以将第num个数标记为0 :删除该数
public boolean contains(int num) {
return (bits[num >> 6] & (1L << (num & 63))) != 0;
}
//在位图中查询一个数
//1.将一个数所在位数和余数找出来
//2.和原数组与
//3.如果不为零则存在
}
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("测试结束！");
}
/*
* 三分之的几率加一个数 减一个数 或者判断是否相等
* 如果有不相等则错误
*/
}
注意: 必须要用1L,否则整形int只有32位不能左移超过32位,结果会出错
位运算实现加减
a+b
异或 : 相当于无进位相加
进位信息 : 与后左移一位 <<1
相加 : 无进位相加 + 进位信息
如果一直循环上述1~3的步骤,会发现总有一次进位信息为0,答案仅为无进位相加信息
public static int add(int a, int b) {
int sum = a;
while (b != 0) {
sum = a ^ b; //无进位相加信息 -> sum
b = (a & b) << 1; //进位信息 -> b -> b`(进位信息)
a = sum; //a -> a` 无进位相加信息
}
return sum; //直到进位信息变成 0,返回无进位相加信息,为最后答案
}
a-b
相当于 add (a,add(~b,1))
public static int add(int a, int b) { //a+b
int sum = a;
while (b != 0) {
sum = a ^ b; //无进位相加信息 -> sum
b = (a & b) << 1; //进位信息 -> b -> b`(进位信息)
a = sum; //a -> a` 无进位相加信息
}
return sum; //直到进位信息变成 0,返回无进位相加信息,为最后答案
}
public static int negNum(int n) {
return add(~n, 1);
} //n的相反数
public static int minus(int a, int b) {
return add(a, negNum(b));
} //a-b
位运算实现乘除
a*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;
}
- b每次向右移动一位
如果b的值不为0
- 同时如果b&1不为0 (b的末尾有1)
- 将a加到res里面
- 如果b的值为0
- a向左移动一位
注意:
如果是负数 带符号右移存新出来的位数用符号位补位
**不带符号右移新出来的位数用0补齐**
a/b
LeetCode例题: 29. 两数相除
思路:
a/b = c 假设c的值为01110
那么 a = b _ 2 + b _ 2 + b * 2 = b << 1 + b << 2
**推理 :**
**a - 2 _ b - 2 _ b ... 以此类推**
**那么所有的2相加就为 c => 可以推出c的值所有m位为1**
那么
需要先求出 小于等于 a 的2的 m 的最大值
a - a
重复上述 就可以得出c
public static boolean isNeg(int n) {
return n < 0;
}
public static int negNum(int n) {
return add(~n, 1);
} //n的相反数
public static int minus(int a, int b) {
return add(a, negNum(b));
} //a-b
public static int add(int a, int b) { //a+b
int sum = a;
while (b != 0) {
sum = a ^ b; //无进位相加信息 -> sum
b = (a & b) << 1; //进位信息 -> b -> b`(进位信息)
a = sum; //a -> a` 无进位相加信息
}
return sum; //直到进位信息变成 0,返回无进位相加信息,为最后答案
}
public static int div(int a, int b) {
int x = isNeg(a) ? negNum(a) : a;
int y = isNeg(b) ? negNum(b) : b; //将a和b都转成正数 得到x,y
int res = 0;
for (int i = 30; i >= 0; i = minus(i, 1)) { //从30开始遍历直到
if ((x >> i) >= y) { //如果x>=y
res |= (1 << i); //记录下结果: 从30位开始为0 直到第i位为1 => 2的i次方
x = minus(x, y << i); //x-y
}
}
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);
}
}
注意:
**边界: 不要让y向左移接近x 如果y多移一位移到符号位会变成负数,会发生错误**
**右移30位: 因为x肯定是非负的,所以不用考虑右移31位**
**缺陷:如果除不尽的话会向下取整**
被除数为系统最小问题
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));
}
}
如果被除数为系统最小怎么算出商呢?
例如 : 假设-10为系统最小 那么9为系统最大值:
当我们求-10/2的时候: 我们不能把-10 变成绝对值 10 进行计算 :这时我们需要绕过对10(系统最大值)进行计算
这时,我们应该把-10+1 = -9 用 -9 进行计算 -9/2 = -4 可见: -4*2 =-8 对 -10和 -8进行比较 差-2 / 2 = -1 所以-4+(-1)=(-5)
leecode刷题约定: Integer.MIN_VALUE/(-1) = Integer.MAX_VALUE
异或运算
异或运算: 相同为0 不同为1
同或运算: 相同为1 不同为0
异或运算: — 无符号相加
异或运算性质
- 0^N = N
- N^N = 0
- 异或运算满足交换律和结合律
位运算实现两数交换
public static void main(String[] args) {
int a = 16;
int b = 603;
System.out.println(a);
System.out.println(b);
a = a ^ b;
b = a ^ b;
a = a ^ b;
System.out.println(a);
System.out.println(b);
int[] arr = { 3, 1, 100 };
int i = 0;
int j = 0;
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
System.out.println(arr[i] + " , " + arr[j]);
System.out.println(arr[0]);
System.out.println(arr[2]);
swap(arr, 0, 0);
System.out.println(arr[0]);
System.out.println(arr[2]);
}
public static void swap(int[] arr, int i, int j) {
// arr[0] = arr[0] ^ arr[0];
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
一个数组中有一个数出现了奇数次,其他数都出现了偶数次,找到并打印这个数
eor ^= a
eor ^= b
...
ans = eor
// arr中，只有一种数，出现奇数次
public static void printOddTimesNum1(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
System.out.println(eor);
}
一个数组中有两个数出现了奇数次,其他数都出现了偶数次,找到并打印这个数
// arr中，有两种数，出现奇数次
public static void printOddTimesNum2(int[] arr) {
int eor = 0;
for (int i = 0; i < arr.length; i++) {
eor ^= arr[i];
}
// a 和 b是两种数
// eor != 0
// eor最右侧的1，提取出来
// eor : 00110010110111000
// rightOne :00000000000001000
int rightOne = eor & (-eor); // 提取出最右的1
int onlyOne = 0; // eor'
for (int i = 0; i < arr.length; i++) {
// arr[1] = 111100011110000
// rightOne= 000000000010000
if ((arr[i] & rightOne) != 0) {
onlyOne ^= arr[i];
}
}
System.out.println(onlyOne + " " + (eor ^ onlyOne));
}
找到二进制中1的个数
public static int bit1counts(int N) {
int count = 0;
// 011011010000
// 000000010000 1
// 011011000000
//
while (N != 0) {
int rightOne = N & ((~N) + 1);
count++;
N ^= rightOne;
// N -= rightOne
}
return count;
}
若有收获，就点个赞吧
0 人点赞
