检查是否设置了1到n之间的k中的所有位

Question

我正在博客上阅读一个问题,问题的解决方案是检查"k"中是否设置了1到n位.

对于前者

• k = 3且n = 2; 然后是"真",因为第1和第2位设置为k

• k = 3且n = 3; 然后"假",因为k中的第3位未设置

作者提供的解决方案是:

    if (((1 << (n-1)) ^ (k & ((1 << n)-1))) == ((1 << (n-1))-1))
        std::cout<<"true"<<std::endl; 
    else 
        std::cout<<"false"<<std::endl; 

我不确定这里发生了什么.有人可以帮我理解这个吗？

Answer 1

如果您在笔和纸上绘制二进制表示,您将看到(1 << (n-1))始终将单个位设置为1(n第 - 位),而(1 << n) - 1设置第一位n.

这些是位掩码 ; 它们被用来k通过按位运算(&,|和^)来操作input()的某些部分.

注意

我认为这个例子是不必要的复杂.这应该足够了:

if ((k & ((1 << n) - 1)) == ((1 << n) - 1))
    ...

或者使它更清洁:

unsigned int mask = (1 << n) - 1;
if ((k & mask) == mask)
   ...

(假设k是类型unsigned int).