如何在不使用循环的情况下找到小于一个数字的最大2的幂次方？ 示例：
5 output = 4.
11 output = 8.
100 output = 64.
6个回答
12
使用整数进行微调的一种方法是：
// given an int number (which would be the upper value of the range)
number |= number >> 1;
number |= number >> 2;
number |= number >> 4;
number |= number >> 8;
number |= number >> 16;
return (number >> 1) + 1;
这个想法是将类似于01010的东西变成01111，向右移一次得到00111，然后加1得到01000的结果。
要了解这是如何工作的，请考虑输入是否为0或非零。如果是0，则结果为0+1，因为所有的位移和或运算都会得到0（2的0次方是1，是2的最低幂，也是输入0的答案）。
对于非零数字，它们的比特位中必定存在该值的最高有效比特位。我们希望的答案是该比特位，但不包括其后面的所有比特位。因此，我们只需关注这个单独的比特位，因为这是我们真正关心的。当我们进行第一个向右移位运算的按位或运算时，我们确保最高有效比特位仍设置，并且比它小1的比特位也被设置，因为0100 | 0010 = 0110。接下来，我们将其与自身按位或运算，但这次向右移两次。这样可以确保我们有最高有效比特位以及3个以下比特位。我们继续重复这个过程，直到达到int类型的位数限制。以下是一个完整的32位值示例的逐步说明：
01000000110100111000000011010011
01000000000100000000000010000010 |
00100000000010000000000001000001 = 01100000000110000000000011000011 (num |= num >> 1)
01100000000110000000000011000011 |
00011000000001100000000000110000 = 01111000000111100000000011110011 (num |= num >> 2)
01111000000111100000000011110011 |
00000111100000011110000000001111 = 01111111100111111110000011111111 (num |= num >> 4)
01111111100111111110000011111111 |
00000000011111111001111111100000 = 01111111111111111111111111111111 (num |= num >> 8)
01111111111111111111111111111111 |
00000000000000000111111111111111 = 01111111111111111111111111111111 (num |= num >> 16)
现在只需要将最终值右移一位，再加上1，就可以将所有的1变成0，除了最高有效位的进位会将我们想要的答案位设为1。
- hatchet - done with SOverflow
7
这是一个“展开的循环”...我不认为这是OP想要的。 - Floris
但我很欣赏这种聪明才智... - Floris
我认为“没有显式循环”就是你所能要求的全部。这看起来有点像一道作业题... - Floris
那是 C (C++) ...??? - Floris
你能解释一下为什么这些操作可以保证将01010转换为01111吗？ - woryzower
显示剩余2条评论
10
假设您想要比x小的最大2的幂，您可以从以下内容中获得：
Ans=pow(2,floor(log(x)/log(2)));
- Floris
4
你为什么要除以log(2)？因为log(2)只是等于1吗？ - nirvanaswap
1@nirvanaswap 我正在使用自然对数函数，这是内置的函数。
log_n(x) = log_e(x)/log_e(n) - Floris为了编译器的完美，挑剔一下，需要一个额外的括号：Ans=pow(2,floor(log(x)/log(2))); - MASQ
@MASQ 谢谢，已完成！ - Floris
1
如果n是范围中的最大数
return int(math.log(n, 2));
- sr01853
2
1你需要计算2的你的表达式次方。 - Floris
这是C#还是C++？我记不得在C++中有一个
math对象。你是不是想说math::log？ - Thomas Matthews0
你可以对这个数字取以2为底的对数，这将给出它的幂次，或者，如果它是一个整数，获取最高位设置的位置（但这可能需要循环）。
我已经有一段时间没有写C++了，但在C#中，它应该是：
double val = 129;
int power = (int)(Math.Log10(val) / Math.Log10(2));
使用公式 logn(X) = logy(X) / logy(n)
- user1689571
0
// This only works if i >= 0, and it may overestimate by one power of 2
// if i is slightly less than a large power of 2. Fixing these issues is
// not difficult, so it's left as an exercise.
long largest_power_of_two(long i) {
int exp;
frexp(double(i), &exp);
return long(ldexp(0.5, exp));
}
frexp和ldexp只是在操纵位，因此甚至没有隐藏的循环（除非可能出现在微架构层）。
- rici
0
如果可用，您可以使用特殊的CPU指令，例如x86 BSR。
如果您可以在不使用循环的情况下对数字进行位反转（例如使用查找表或其他特殊的CPU指令），那么您可以反转数字，找到最低有效位设置为1，重置其他位并将其反转回来。
unsigned IsolateLeastSignificantOne(unsigned n)
{
return n & -n;
}
n = BitRevert(IsolateLeastSignificantOne(BitRevert(n)));
有关位运算技巧和其他实用信息，请参考此文档。
- Alexey Frunze
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
2^floor(log2(number))。 - Floris