【位运算总结】 之 左移运算

左移运算的概念：左移运算符

应用：

1、优化代码

       因为左移运算比乘法快，因此x = x*2可优化为x = x << 1。

2、计算一个数的二进制的某位

       如题：给定一个含不同整数的集合，返回其所有的子集。

       解题思路：
       假设该数组为a[n]，有n个元素。对每个元素标记为1或0表示某子集内有或没有该元素，如此排列下来，000…00，000…01，000…10， …… ，至111…1，共有2^n-1中排列方式。若将区间[0，2^n-1]中的每个整数表示为一个子集，遍历每个集合可表示为

for (int i = 0; i < (1<<n), ++i)

       如何可以从这个整数中得到子集中的元素呢？

       这就用到了左移运算，如 1 << 0 = 1，1 << 2 = 10，1 << 3 = 100…… 那么，我们将每个整数相与& (1 << j)，就可以得到该整数的二进制表示中，第 j 位是0还是1！

       所以，本题完整的代码可以表示为：

       (第一行是空行，因为数字0表示没有任何一个数在集合中，即空集)

#include <iostream>

using namespace std;

int main()
{
    int arr[5] = {1, 2, 3, 4, 5};

    int n = 5;

    for (int i = 0; i < (1<<n); i++) //从0～2^n-1个状态
    {
        for (int j = 0; j < n; j++) //遍历二进制的每一位
        {
            if (i & (1 << j))//判断二进制第j位是否存在
            {
                cout << arr[j] << ' ';//如果存在输出第j个元素
            }
        }
        cout << endl;
    }

    return 0;
}