位运算

#algorithm/bitWise

基本操作

与   &   都为真为真
或   |   有一个为真就为真
非   !   真的变假，假的变真
异或  ^   如果相同为0，不同为1

按位与 a & b

都为1则为1，有0则为0
12 & 6 = 4
12：1 1 0 0
6： 0 1 1 0
4： 0 1 0 0

按位或 a | b

有一个为1则为1，都为0则为1
12 | 6 = 14
12：1 1 0 0
6： 0 1 1 0
14：1 1 1 0

按位异或 a ^ b

相同位的值不同则位1，相同则为0
12 ^ 6 = 10
12：1 1 0 0
6： 0 1 1 0
10：1 0 1 0

按位取反 ~a

0 -> 1, 1 -> 0

按位左移 a << b

n << m  ==  n * 2^m
默认左移补0
8 -> 4
1000 -> 100

按位右移 a >> b

n >> m == n / 2^m

是否是2的幂

n & (n-1);

2的幂的二进制都是100…000

e.g.

1:1
2:10
4:100
8:1000

二进制数 n 变成 n-1 后，如果最后一位是 0，将向前一位借 2，2-1=1。最后一位为1。如果前一位为0，将继续向前一位借2，加上本身少掉的1.则变为1。一直遇到1。减为0（和10进制很像），10进制是向前借10，10-1=9（就是小学学的加减乘除）

n & (n-1)
8:1000
7:0111
8 & 7 = 0000

所以 二进制 xxxx10000 - 1 = xxxx01111
 n&n-1

按照上述 
n   = xxxx10000
n-1 = xxxx01111

　　　 xxxx10000

　　 & xxxx01111

\-----------------------------------------

　　　　xxxx0000

可以看到将原来的最右边的1变为0了。重复这个操作，每一次 n 最右边的 1 少一个。从而统计 n 中的 1 的个数

只要是2的幂，那么n&(n-1)的值一定为0

//判断条件
(n > 0 && (n & (n - 1)) == 0)

Leetcode231 2的幂

给你一个整数 n，请你判断该整数是否是 2 的幂次方。如果是，返回 true ；否则，返回 false 。

如果存在一个整数 x 使得 n == 2x ，则认为 n 是 2 的幂次方。

示例 1：

输入：n = 1
输出：true
解释：20 = 1

示例 2：

输入：n = 16
输出：true
解释：24 = 16

示例 3：

输入：n = 3
输出：false

示例 4：

输入：n = 4
输出：true

示例 5：

输入：n = 5
输出：false

提示：

• $-2^{31} <= n <= 2^{31} - 1$

source code

/*
 * @lc app=leetcode.cn id=231 lang=cpp
 *
 * [231] 2 的幂
 */

// @lc code=start
class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & (n - 1)) == 0;
    }
};
// @lc code=end

ACwing801  二进制中1的个数

给定一个长度为 n的数列，请你求出数列中每个数的二进制表示中 1的个数。

输入格式

第一行包含整数 n

第二行包含 n个整数，表示整个数列

输出格式

共一行，包含 n个整数，其中的第 i个数表示数列中的第 i个数的二进制表示中 1的个数

数据范围

$1≤n≤100000$

$0≤数列中元素的值≤10^9$

输入样例：

5
1 2 3 4 5

输出样例：

1 1 2 1 2

source code

#include <iostream>
using namespace std;
#define out(x) for(int i=0;i<x;i++)
int main()
{
    int n, t;
    cin >> n;
    out(n)
    {
        int sum = 0;
        cin >> t;
        while (t)
            t &= (t - 1), sum++;
        cout << sum << ' ';
    }
    return 0;
}

面试题 16.01.交换数字

编写一个函数，不用临时变量，直接交换numbers = [a, b]中a与b的值。

示例：

输入: numbers = [1,2]
输出: [2,1]

提示：

• $numbers.length == 2$
• $-2147483647 <= numbers[i] <= 2147483647$

source code

class Solution {
public:
    vector<int> swapNumbers(vector<int>& numbers) {
        int a=numbers[0],b=numbers[1];
        a=a^b;
        b=a^b;
        a=a^b;
        return {a,b};
    }
};