计算汉明权重（Hamming Weight）

就是让你返回 n 的二进制表示中有几个 1。因为 n & (n - 1) 可以消除最后一个 1，所以可以用一个循环不停地消除 1 同时计数，直到 n 变成 0 为止。

int hammingWeight(uint32_t n) {
    int res = 0;
    while (n != 0) {
        n = n & (n - 1);
        res++;
    }
    return res;
}

或者用n&-n：

这个会变成一个掩码，n 的最低位为 1，其余都是 0

for(int res = 0; x-=x&-x; ++res)
	if(x== 0) return res;

---

同理

** x + 1  会将  x  最低位的连续  1  翻转（例如  0b0111 + 1 = 0b1000 ）。**

** x ^ (x + 1)  会生成一个掩码，其中原连续  1  的位全为  1 （如  0b0111 ^ 0b1000 = 0b1111 ）。**

---

判断一个数是不是 2 的指数

一个数如果是 2 的指数，那么它的二进制表示一定只含有一个 1：

2^0 = 1 = 0b0001
2^1 = 2 = 0b0010
2^2 = 4 = 0b0100

如果使用位运算技巧就很简单了（注意运算符优先级，括号不可以省略）：

bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    return (n & (n - 1)) == 0;
}

查找只出现一次的元素

这里就可以运用异或运算的性质：

一个数和它本身做异或运算结果为 0，即 a ^ a = 0；一个数和 0 做异或运算的结果为它本身，即 a ^ 0 = a。

对于这道题目，我们只要把所有数字进行异或，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身，所以最后异或的结果就是只出现一次的元素：

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}

剑指 Offer 65. 不用加减乘除做加法

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

示例:

输入: a = 1, b = 1
输出: 2

提示：

• a, b 均可能是负数或 0
• 结果不会溢出 32 位整数

解题思路：

本题考察对位运算的灵活使用，即使用位运算实现加法。

设两数字的二进制形式 \(a, b\)，其求和 \(s = a + b\) ，\(a(i)\)代表 \(a\) 的二进制第\(i\) 位，则分为以下四种情况：

a(i)	b(i)	无进位和 n(i)	进位 c(i+1)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

观察发现，无进位和 与 异或运算 规律相同，进位 和 与运算 规律相同（并需左移一位）。因此，无进位和 \(n\)与进位 \(c\)的计算公式如下；

\(\begin{align*} \begin{split} \left \{ \begin{array}{ll} n= a⊕b &非进位和：异或运算\\ c= a \& b<<1 &进位：与运算+左移一位 \end{array} \right. \end{split} \end{align*}\)

\(\text{和}s=\text{非进位和}n+\text{进位}c\)。即可将 \(s = a + b\) 转化为：

\(s=a+b⇒s=n+c\)

Q ： 若数字 a 和 b 中有负数，则变成了减法，如何处理？

A ： 在计算机系统中，数值一律用 补码 来表示和存储。补码的优势： 加法、减法可以统一处理（CPU只有加法器）。因此，以上方法 同时适用于正数和负数的加法 。

这里有个问题，当我们求出 n和c的时候需要使用s = n+c来求出最后结果，但是我们不能使用+。注意到，这里的+就是我们这里定义的函数呀！！！所以递归即可。

代码

class Solution {
    public int add(int a, int b) {
        if(b==0) return a;
        return add(a^b,(a&b)<<1);
    }
}

我们这里也可以将递归使用while循环展开。循环求 \(n\)和 \(c\) ，直至进位 \(c = 0\)；此时 \(s = n\)，返回 \(n\) 即可。

但是这时候有溢出问题。

在 \(\texttt{C++}\)的实现中，当我们赋给带符号类型一个超出它表示范围的值时，结果是 \(\text{undefined}\)；而当我们赋给无符号类型一个超出它表示范围的值时，结果是初始值对无符号类型表示数值总数取模的余数。因此，我们可以使用无符号类型来防止溢出。

class Solution {
public:
    int add(int a, int b) {
        while (b != 0) {
            unsigned int carry = (unsigned int)(a & b) << 1;
            a = a ^ b;
            b = carry;
        }
        return a;
    }
};

复杂度分析：

• 时间复杂度 \(O(1)\) ： 最差情况下（例如 a= 0x7fffffff\(,\) \(b = 1\) 时），需循环 32 次，使用 \(O(1)\) 时间；每轮中的常数次位操作使用 \(O(1)\) 时间。
• 空间复杂度 O(1)： 使用常数大小的额外空间。