C++中(n&1 << b)的含义

Question

在将CodeChef中的其他人编写的C++代码引用到特定问题时,我发现了一种新方法(至少对我来说)编写这样的条件语句: if (n & 1 << b).整个代码片段(一个函数)如下:

int Solve(int tim, int n)
{
    if (tim < 0) 
         return 1;

    int res = 0;
    for (int b = Maxb - 1; b >= 0; b--)
        if (n & 1 << b) 
        {
            int my = b - __builtin_popcount(tim & ((1 << b) - 1));
            res += 1 << my;

            if (tim & 1 << b) 
                 return res;
        }

    res++;
    return res;
}

我知道按位AND操作以及左移操作意味着我们单独使用时.但是,这里两个条件语句的组合让我混淆了阅读逻辑.当我搜索引用时,我找不到两个操作一起出现的情况.因此,任何人都可以告诉我这里的意义或究竟发生了什么？

Answer 1

检查n的二进制表示中位置'b'处的位是打开还是关闭.

if (n & 1 << b) 

本质上是

if (n & (1 << b)) 

因为运营商的优先权.

这些是1 << b得到的值(右侧是二进制):

对于b == 0, (1 << b) == ...000000001

对于b == 1, (1 << b) == ...000000010

对于b == 2, (1 << b) == ...000000100

对于b == 3, (1 << b) == ...000000100

对于b == 3, (1 << b) == ...000001000

对于b == 4, (1 << b) == ...000010000

等等.

当你&的价值1 << b与n你基本上是关闭所有的n"s位,除了对应的位置位1在二进制表示1 << b.

这意味着只有n & (1 << b)当该位n位于与该1位相对应的位置时,才会获得非零结果(1 << b).如果不是,那么所有的比特都会关闭,因为它已经存在0,它会停留0,最终的结果就是0.

该if语句接收到这个最终结果,如果它是正数(该位开启)它将进入if,否则(如果该位关闭),最终结果将为0并且if语句将认为该语句n & (1 << b)为false.