判断32位有符号整型是否为2的幂
我需要确定一个有符号的32位数是否是2的幂。到目前为止，我知道要做的第一件事是检查它是否为负，因为负数不能是2的幂。然后我需要看看下一个数字是否有效，等等。所以我可以这样写：
// Return 1 if x is a power of 2, and return 0 otherwise.
int func(int x)
{
return ((x != 0) && ((x & (~x + 1)) == x));
}但是对于我的赋值，我只能使用其中的20个运算符：
! ~ & ^ | + << >>并且没有相等语句、循环、强制转换或语言构造。
所以我正在尝试转换相等部分，我知道!(a^b)和== b是一样的，但我似乎不能完全弄明白它。关于如何将其转换为允许的操作符，有什么想法吗？
回答 6
Stack Overflow用户
发布于 2011-09-09 21:46:37
蒂姆的评论使我感到羞愧。让我试着帮你自己找到答案。
就位操作而言，x是2的幂是什么意思？这意味着只有一个位被设置为1，我们如何才能实现这样的技巧，将该位设置为0，并可能将其他一些位设置为1？那么&会给0吗？在单个表达式中？如果你发现了-你赢了。
Stack Overflow用户
发布于 2011-09-09 21:49:09
试试这些想法：
~!!x+1给出一个掩码:如果x==0，则为0；如果x至多设置了1位，则为-1；否则为非零值，除非~x为INT_MIN，在这种情况下，结果未定义...你也许可以用位移位将它分成多个部分来避免这种情况，但我认为你会超出运算限制。- 你还想检查符号位，因为负值不是2的幂...
顺便说一句，听起来你的老师没有意识到有符号的溢出在C中是UB的，他应该把这些问题写成无符号的整数。即使你想在语义上对待这个值，就像它是有符号的一样，你也需要无符号的算术来做像这样有意义的位运算。
Stack Overflow用户
发布于 2019-07-09 06:12:26
首先，在你的解决方案中，应该是
return ((x > 0) && ((x & (~x + 1)) == x));因为负数不能是2的幂。根据您的要求，我们需要将">"，"&&"，"==“转换为允许的运算符。
首先考虑">"，当integer>0的符号位是1而不是0时，我们考虑
~(x >> 31) & (x & ~0)如果x不是正数，上面的表达式将返回一个非零数。请注意~0 = -1，即0x11111111。我们使用x& ~0来检查这个整数在每个数字上是否都为0。
其次，我们考虑"&&“。非常简单--我们只需要得到0x01 & 0x01返回1。所以这里我们需要添加(!!)在我们的第一个答案前面，如果它返回一个非零数，则将其更改为0x01。
最后，我们考虑"==“。要测试A和B的公平性，我们只需要做
!(A ^ B)所以我们最终得到了
return (!!(~(x >> 31) & (x & ~0))) & (!((x&(~x+1)) ^ x))这似乎是一个家庭作业的问题。请不要简单地复制和粘贴。我的回答有点尴尬，可能会有所改进。
https://stackoverflow.com/questions/7362485
复制相似问题
腾讯云开发者
