位运算

& 与运算 遇0则0
| 或运算 遇1则1
^ 异或 不进位加 相同为0 相异为1
~ 取反 1-0 0-1
>> 右移（逻辑位移） 补符号位 符号为1补1 符号为0补0
<< 左移（算数位移） 永远补0
>>> 无符号右移  永远补0

and(bits) – 位与 (Java 的 &)
or(bits) – 位或 (Java 的 |)
inv() – 位非 (Java 的 ~)
xor(bits) – 位异或 (Java 的 ^)
shl(bits) – 有符号左移 (Java 的 <<)
shr(bits) – 有符号右移 (Java 的 >>)
ushr(bits) – 无符号右移 (Java 的 >>>)

a & a = a
a | a = a
a ^ a = 0

a & ~a == 0;
a | ~a == -1;   
a ^ ~a == -1;

a & 0 = 0
a | 0 = a
a ^ 0 = a

a & -1 = a
a | -1 = -1
a ^ -1 = -(a+1)

a | ( a & b ) = a
a & ( a | b ) = a

// 当且仅当 a 是偶数（即 a 能被 2 整除，数学表示为 (a = $2k$, k \in \mathbb{Z}\)）时，等式成立
a | 1 = a + 1

// 如果a是奇数,(a + 1)如果a是偶数
a ^ 1 = (a - 1)

// 删除整数 a 二进制最后一个 1 
// a-1 会翻转 a 最后一个 1 及右侧所有位，与 a 按位与后仅保留左侧不变的位
a & (a-1)

### 统计二进制中 1 的个数（汉明重量）
原理：每执行一次 a & (a - 1)，就会删除一个 1，直到 a 变为 0（所有 1 都被删除），执行次数即为 1 的个数。
示例（统计 a=13 二进制中 1 的个数，13=1101，共 3 个 1）：
1. a = 13 (1101) → a & (a-1) = 12 (1100) → 次数1；
2. a = 12 (1100) → a & (a-1) = 8 (1000)  → 次数2；
3. a = 8 (1000)  → a & (a-1) = 0 (0000)  → 次数3；
a=0，停止，结果为3。

// 判断一个数是否为 2 的幂
原理：2 的幂（如 2、4、8、16）的二进制有且只有一个 1（如 8=1000）。若 a 是 2 的幂，则 a & (a - 1) = 0（唯一的 1 被删除后变为 0）；反之则不为 0。
示例：
a=8（2³）：8 & 7 = 0 → 是 2 的幂；
a=9（1001）：9 & 8 = 8 ≠ 0 → 不是 2 的幂。
2.2
a & (-a) = a（保留自身）
示例：8 & (-8) = 8 → 是 2 的幂；6 & (-6) = 2 ≠ 6 → 不是 2 的幂。


// 清除二进制末尾的连续 0
结合其他操作，可先通过 a & -a 找到最后一个 1 的位置（如 a=12=1100，a&-a=4=100），再用 a & (a - 1) 删除该 1，间接清除末尾的连续 0。

// 负数
-a = ~a + 1

// 仅保留最后一个1;
a & (-a)

a & -a 或者 a & (~a + 1) 获取最右侧1表示的值
比如: 
4 二进制是 100  4 & -4 等于0 4最右侧的1后面的值就是4的本身100   
5 二进制是 101  5 & -5 等于1 5最右侧的1后面的值就是1, 如果 5 - (5 & -5) 就相当于直接去掉最右侧的1  
6 二进制是 110  6 & -6 等于2 6最右侧的1后面的值就是2, 如果 6 - (6 & -6) 就相当于直接去掉最右侧的1  

// 比较两值是否相等
a ^ b == 0

// i+1位 置1
a |= 1<<i

// i+1位 置0
a &=~(1<<i)

// 取出i+1位(联系第5点)
a & (1<<i)

// 在对应i+1位，插入b的对应位；
a |=1<<i; （a的bit位置1）
a & (b & 1<<i) （与b的bit位相与）

// 得到全1
~0

// 保留最后i-1位；
a & ((1<<i)-1)

// 清零最后i-1位；
a & ~((1<<i)-1)

// 判断最高位是否为1
a<0

// 得到最高位的1；
a = a |(a>>1);
a = a |(a>>2);
a = a |(a>>4);
a = a |(a>>8);
a = a |(a>>16);
return (a+1)>>1;

a & 1 = 0 或 1  a为奇数返回1、a为偶数返回0

// 判断奇偶(取出最后一位)
a & 1 等价于 a % 2(结果等于,位运算效率高)

public void isOddOrEven(int n){
    if ((n & 1) == 1) { //n是奇数
        System.out.println("Odd");
    }else { //n是偶数
        System.out.println("Even");
    }
}

a = a ^ b
b = a ^ b
a = a ^ b

方式一：通过临时变了存放交换 效率最高

int temp = a;
a = b;
b = temp;

方式二：通过加减计算交换
a = a + b;
b = a - b;
a = a - b;

方式三：通过异或运算交换

a = a ^ b;
b = a ^ b;
a = a ^ b;

a ^= b;
b ^= a;
a ^= b;

方式四：非常不推荐，代码的简洁性是很重要的，但是也许面试题会考到

a = (a + b) - (b = a);
//用到的知识点:
//赋值运算符在连续赋值的时候会使用初始值代替中间变量

方式四：不推荐，理由同上
a = (a ^ b) ^ (b = a);

首先需要知道关于异或运算的一些性质：

异或满足交换律和结合律
x ^ x == 0
x ^ 0 == x

方式一是最常见的，可读性高，但是需要在内存中存放临时变量，但是对于现在来说，需要的内存空间很小，而且存放临时变量的内存很快就会释放，不存在问题。

方式二有缺陷，当两个数相加之后，可能其结果超出了变量类型能表达的最大范围，这个时候结果就会出问题，不推荐使用。

方式三效率是最高的，但是可读性不是很好。

在程序中我们应该尽可能的使用方式一，提高程序的可读性。但是需要了解方式三，以及方式三的原理。

public void negate(){
    int a = -10, b = 10;
    System.out.println(~a + 1);//10
    System.out.println(~b + 1);//-10
}

public int abs(int a){
    int i = a >> 31;//得到符号位，0 为正数，-1 为负数
    return i == 0 ? a : (~a + 1);//符号位为 0 直接返回，否则返回 ~a + 1
}

public int abs(int a){
    return (a ^ (a >> 31)) - (a >> 31);
}

 n > 0 && n & (n-1) == 0 && n % 3 == 1