算法技巧收集
2022-03-21 03:54:30 0 举报AI智能生成
算法中的小技巧收集整理
作者其他创作
大纲/内容
异或
定义及特点
按位操作
定义：相同为0，不同为1
实质就是“无进位相加”
可以认为是“无退位的相减”吗？
例: 当 c = a ^ b （此时为无进位加）, 获取a = c ^ b 的过程
例: 当 c = a ^ b （此时为无进位加）, 获取a = c ^ b 的过程
异或其实就是找不同。（英文：Exclusive的意思）
人们利用异或的运算特性，在重复数据中去除冗余信息，实现信息增量和数据压缩。
人们利用异或的运算特性，在重复数据中去除冗余信息，实现信息增量和数据压缩。
异或的图例
实质是把两个数据中的相同数据删除，只留下不同数据的过程。
归零律
N ^ N = 0
恒等律
0 ^ N = N
自反律
a ^ b ^ a = b
1 ^ N = ~N 按位取反
满足交换律和结合律
连续异或所最终结果不变
例如：a ^ b ^ c ^ d == d ^ c ^ b ^ a == a ^ b ^ d ^ c
也即是，结果与计算顺序无关！
例如：a ^ b ^ c ^ d == d ^ c ^ b ^ a == a ^ b ^ d ^ c
也即是，结果与计算顺序无关！
应用
交换数值
int swap(int a, int b) {
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
a = a ^ b;
b = a ^ b;
a = a ^ b;
}
a和b的值相同，仍然可行
如果a和b指同一个内存空间，则此方法不行
找出数组中，只有一个数出现过奇次，
其他数出现过偶次，找出这个出现奇数次的数。
其他数出现过偶次，找出这个出现奇数次的数。
eor = 0;
for (int i = 0, i < a.length(); i++) {
eor ^= a[i];
}
eor ==> 出现奇数次的数值
for (int i = 0, i < a.length(); i++) {
eor ^= a[i];
}
eor ==> 出现奇数次的数值
找出最右边的1
rightMostOne = N & ((~N) + 1)
例如：N = 1100101011000
期望得到：0000000001000
期望得到：0000000001000
找出数组中，有两个数(x,y)出现过奇次，
其他数出现过偶次，找出x, y。
其他数出现过偶次，找出x, y。
int eor = 0;
for (int i = 0; i < arr.length; i++){
eor ^= a[i];
} //得到 eor = x ^ y
int rightOne = eor & ((~eor) + 1);
int eorRight = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] & rightOne != 0) {
eorRight ^= a[i];
}
}
x = eorRight
y = eor ^ eorRight
for (int i = 0; i < arr.length; i++){
eor ^= a[i];
} //得到 eor = x ^ y
int rightOne = eor & ((~eor) + 1);
int eorRight = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] & rightOne != 0) {
eorRight ^= a[i];
}
}
x = eorRight
y = eor ^ eorRight
找到x^y
已知x<>y, 则x和y一定在其中的一个位上不同，
一个为1，一个为0
一个为1，一个为0
将数组中的数，依据2中找到的位，而分成两部分。
(其中一部分在某位为1，另一部分在某位为0）
对其中一部分异或找出其中一个数x
(其中一部分在某位为1，另一部分在某位为0）
对其中一部分异或找出其中一个数x
子主题
y = x^y^x
二进制1的个数统计
public static int bit1Count(int N) {
int count = 0;
while(N != 0) {
int rightOne = N & ((~N) + 1);
count++;
N ^= rightOne;
}
return count;
}
int count = 0;
while(N != 0) {
int rightOne = N & ((~N) + 1);
count++;
N ^= rightOne;
}
return count;
}
找出最右边的1，然后计数
去除刚才计过数的1
并
判断num是否是2 的某次幂的方法：
(num & (num - 1)) != 0
(num & (num - 1)) != 0
(num & (num - 1)) == 0 是2的某次幂
(num & (num -1)) != 0 不是2的某次幂
移位操作
N x 2
N << 1
N x 2 + 1
(N << 1) | 1
计算中点
mid = L + ((R - L) >> 1)
<=>
mid = (L + R) / 2
<=>
mid = (L + R) / 2
(L + R)可能溢出
“>>" 操作比”/"快
计算数的位数
public int getMaxbit(int[] arr) {
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
int maxbit = 0;
while (max != 0) {
maxbit++;
max /= 10;
}
return maxbit;
}
int max = Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++) {
max = Math.max(arr[i], max);
}
int maxbit = 0;
while (max != 0) {
maxbit++;
max /= 10;
}
return maxbit;
}
取第几位的值
public static getDigit(int x, int d) {
return ((x/((int)(Math.power(10,d-1)) % 10);
}
return ((x/((int)(Math.power(10,d-1)) % 10);
}
判断大小
if (data[c] > 128) sum += data[c]
int t = (data[c] - 128) >> 31;
sum += ~t & data[c];
sum += ~t & data[c];
1. 如果 data[c] - 128 >= 0, 则右移31位的结果是： 0000....000
2. 如果 data[c] - 128 < 0， 则右移31位的结果是： 1111....111
2. 如果 data[c] - 128 < 0， 则右移31位的结果是： 1111....111
建表：
int lookup[DATA_STRIDE];
for (unsigned c = 0; c < DATA_STRIDE; ++c) {
lookup[c] = (c >= 128) ? c : 0;
}
查表：
sum += lookup[data[c]];
int lookup[DATA_STRIDE];
for (unsigned c = 0; c < DATA_STRIDE; ++c) {
lookup[c] = (c >= 128) ? c : 0;
}
查表：
sum += lookup[data[c]];
0 条评论
下一页
