在C++中,(n&(n-1))== 0和n&(n-1)== 0做什么？

Question

C++中做什么(n&(n-1))==0和n&(n-1)==0做什么(n是整数)？

if ((n&(n-1))==0)
{
    // do something
}

if (n&(n-1)==0)
{
    // do something
}

Answer 1

他们假设测试该数字n是2的幂(尽管第二个未能如评论中提到的那样).它基于一个简单的观察,即在二进制表示中,2的幂是仅有一位设置为的唯一数字1.如果1从这个数字中减去,你会得到一系列1s.

示例(正面):

n = 32

而不是二进制表示

n = 100000

那么n - 1 = 011111所以,如果你把n - 1 & n你弄0.

示例(否定):

n = 6

而不是二进制表示

n = 110

现在

n - 1 = 101

所以((n - 1) & n) == 100 > 0.

请注意,正如@harold在评论中提到的那样,0也将通过此测试.

Answer 2

(n & (n - 1)) == 0:

n & (n - 1)取消设置n
二进制的低位设置:XXX10000- >XXX00000

所以(n & (n - 1)) == 0对于0和所有的权力2.

n & (n - 1) == 0:

n & (n - 1) == 0相当于n & ((n - 1) == 0)(由于运算符的优先级)等等n == 1.