Skip to content
The Chat Archive
gpt-3.5-turbo-0613· OpenAI WildChat-4.8M (AI2)

为什么若n是2的幂 那么n&(n-1)=0

  1. User

    为什么若n是2的幂 那么n&(n-1)=0

  2. Assistant

    若n是2的幂,则n可以表示为2的k次方,即n=2^k。其中k为非负整数。 考虑n-1,可以将n-1视为二进制数k位都是1的数字,即n-1=2^k-1=111...111(二进制表示,共k位都是1)。 那么n&(n-1)就是对n和n-1进行位与运算。由于二进制中任何数与1相与的结果都是该位的值,而任何数与0相与的结果都为0。 将n和n-1进行位与运算后的结果,可以看出它们在二进制表示中,从低到高的每一位都是0。 根据位与运算的特性,即只有两个相应的二进制位都是1时,运算结果才是1,否则为0。所以n&(n-1)结果为0,即位与运算结果全为0。 因此,若n是2的幂,则n&(n-1)=0。