首页  思维导图  详情

算法技巧收集

2022-03-21 03:54:30   0  举报





AI智能生成

算法中的小技巧收集整理

计算机算法

算法技巧

作者其他创作

大纲/内容

异或

定义及特点

按位操作

定义：相同为0，不同为1

实质就是“无进位相加”

可以认为是“无退位的相减”吗？ 例: 当 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 也即是，结果与计算顺序无关！

应用

交换数值

int swap(int a, int 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 ==> 出现奇数次的数值

找出最右边的1

rightMostOne = N & ((~N) + 1)

例如：N = 1100101011000 期望得到：0000000001000

找出数组中，有两个数(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

找到x^y

已知x<>y, 则x和y一定在其中的一个位上不同， 一个为1，一个为0

将数组中的数，依据2中找到的位，而分成两部分。 (其中一部分在某位为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; }

找出最右边的1，然后计数

去除刚才计过数的1

并

判断num是否是2 的某次幂的方法： (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

(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; }

取第几位的值

public static getDigit(int x, int d) { 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];

1. 如果 data[c] - 128 >= 0, 则右移31位的结果是： 0000....000 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]];