算法技巧收集

按位操作

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

异或的图例

异或其实就是找不同。（英文：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的值相同，仍然可行

如果a和b指同一个内存空间，则此方法不行

交换数值

找出数组中，只有一个数出现过奇次，其他数出现过偶次，找出这个出现奇数次的数。

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

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

找出最右边的1

找到x^y

将数组中的数，依据2中找到的位，而分成两部分。(其中一部分在某位为1，另一部分在某位为0）对其中一部分异或找出其中一个数x

子主题

y = x^y^x

int eor = 0;for (int i = 0; i < arr.length; i++){    eor ^= a[i];} //得到 eor = x ^ yint rightOne = eor & ((~eor) + 1);int eorRight = 0;for (int i = 0; i < a.length; i++) {   if (a[i] & rightOne != 0) {       eorRight ^= a[i];   }}x = eorRighty = eor ^ eorRight

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

去除刚才计过数的1

public static int bit1Count(int N) {    int count = 0;       while(N != 0) {       int rightOne = N & ((~N) + 1);       count++;       N ^= rightOne;    }   return count;}

二进制1的个数统计

应用

异或

(num & (num - 1)) == 0 是2的某次幂

(num & (num -1)) != 0 不是2的某次幂

判断num是否是2 的某次幂的方法：(num & (num - 1)) != 0

并

N << 1

N x 2

(N << 1) | 1

N x 2 + 1

(L + R)可能溢出

“>>\" 操作比”/\"快

mid = L + ((R - L) >> 1) <=> mid = (L + R) / 2

计算中点

移位操作

计算数的位数

取第几位的值

if (data[c] > 128) sum += data[c]

int t = (data[c] - 128) >> 31;sum += ~t & data[c];

建表： int lookup[DATA_STRIDE]; for (unsigned c = 0; c < DATA_STRIDE; ++c) { lookup[c] = (c >= 128) ? c : 0; }查表： sum += lookup[data[c]];

判断大小

算法技巧收集