语句 if (counter & (1<<j)) 是什么意思，它是如何工作的？

Question

我正在研究子序列的算法。

语句的含义是什么：

if (counter & (1<<j))

在以下程序的上下文中：

void printSubsequences(int arr[], int n)
{
    unsigned int opsize = pow(2, n);

    for (int counter = 1; counter < opsize; counter++)
    {
        for (int j = 0; j < n; j++)
        {
            if (counter & (1<<j))
                cout << arr[j] << " ";
        }
        cout << endl;
    }
}

Answer 1

声明：

if (counter & (1<<j))

检查是否设置了 counter 的第 j 位。更详细地说，1 << j 使用 1 的移位来生成位掩码，其中仅设置了第 j 位。 & 运算符然后屏蔽掉 counter 的 j 位；如果结果不为零（这意味着 counter 的第 j 位已设置），则满足条件。

考虑以下示例。如果counter为320，其二进制表示为101000000，表示第6位（64的值对应的位）被置位；让我们测试一下。位掩码是通过将 1 的二进制表示形式 000000001 向右移动 6 位而生成的，从而得到二进制值 001000000。 counter的值，即：

101000000

与&组合，即按位and-operator，位掩码如下：

  101000000
& 001000000
  ---------
  001000000

值001000000再次对应值64；然而这在这里并不重要，重要的是它不为零（因为它有一个非零位，即我们打算检查的位）。总的来说，条件

if ( 64 )

满意。在 C 的语义中（它不具有本机布尔数据类型），在使用 if.

检查时，任何非零值都被视为 true