位操作的魔法.md

位操作的魔法

原标题：Bit Twiddling Hacks 来自：http://graphics.stanford.edu/~seander/bithacks.html 作者：Sean Eron Anderson

0. 基本操作

与（&）
或（|）
非（~）
异或（^）
左移（<<）
无符号右移位（>>>）
带符号右移（>>）

1. 整数的符号位

boolean isNegative(int v) {
    // 无符号右移
    return (v >>> 31) == 1;
}

2. 两个整数是否异号

boolean oppositeSign(int x, int y) {

    return ((x ^ y) < 0);
}

3. 整数的绝对值

int abs(int v) {
    // 带符号右移
    int mask = v >> 31;
    return (v + mask) ^ mask;// 或者：(v ^ mask) - mask;
}

4. 求整数的最值（要求 x-y 不能越界）

int min(int x, int y) {
    return y + ((x - y) & ((x - y) >> 31));
}

int max(int x, int y) {
    return x - ((x - y) & ((x - y) >> 31));
}

5. 整数是否是 2 的整数次幂

boolean isPowerOfTwo(int v) {
    return v > 0 && (v & (v - 1)) == 0;
}

6. 整数的二进制序列有多少个 1

int countOne(int v) {
    int count = 0;
    while (v != 0) {
        v = v & (v - 1);
        count++;
    }
    return count;
}

7. 交换 2 个整数（两个数的地址不能相同）

void swap(int x, int y) {
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;
    //因为java是call by value，栈上x与y已经交换，但是堆中x与y不变
}

8. 刚好不小于整数的 2 的整数次幂（HashMap 中计算初始容量）

int morePowerOfTwo(int cap) {
    final int MAXIMUM_CAPACITY = 1 << 30;
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

9. 获得最右侧（低位）的 1

int getRightOne(int v) {
    return v & (~v + 1);
}

10. 移除最右侧（低位）的 1

int removeRightOne(int v) {
    return v & (v - 1);// 或v - (v & (~v + 1));
}

11. 将最右侧（低位）的 0 变为 1

int changeRightZero(int v) {
    return v | (v + 1);
}