算法入门——位运算（一）

神级运算——位运算 - 知乎 (zhihu.com)

位运算（&、|、^、~、>>、<<）

对二进制进行的运算（+、-、*、/）都叫 位运算

程序设计中对位模式或二进制数的一元和二元操作。

位运算的问题，很多都很有技巧性

2 的幂

n：二进制表示（大于0的数）

n为2的幂

• 必要性：恒有 n & (n - 1) == 0，这是因为：

  1. n 二进制最高位为 1，其余所有位为 0
  2. n−1 二进制最高位为 0，其余所有位为 1

• 充分性： n & n-1可以把n最低位的1变0，而当n & n-1 == 0时，则说明n只有一个1

class Solution {
    public boolean isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
}

2 的幂 （位运算，极简解法+图表解析）

Integer.bitCount()理解

位1的个数

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; ++i) {
            count += n & 1;//得到二进制末尾是否为 1
            n >>= 1;//算数右移，高位补1，低位丢弃
        }
        return count;
    }
}

【负雪明烛】详解位运算，附本题躲坑指南 - 位1的个数