如何在不使用循环的情况下找到小于一个数字的最大2的幂次方? 示例:
5 output = 4.
11 output = 8.
100 output = 64.
使用整数进行微调的一种方法是:
// 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。
假设您想要比x小的最大2的幂,您可以从以下内容中获得:
Ans=pow(2,floor(log(x)/log(2)));
log_n(x) = log_e(x)/log_e(n)
- Florisreturn int(math.log(n, 2));
math
对象。你是不是想说math::log
? - Thomas Matthews你可以对这个数字取以2为底的对数,这将给出它的幂次,或者,如果它是一个整数,获取最高位设置的位置(但这可能需要循环)。
我已经有一段时间没有写C++了,但在C#中,它应该是:
double val = 129;
int power = (int)(Math.Log10(val) / Math.Log10(2));
使用公式 logn(X) = logy(X) / logy(n)
// 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
只是在操纵位,因此甚至没有隐藏的循环(除非可能出现在微架构层)。
如果可用,您可以使用特殊的CPU指令,例如x86 BSR
。
如果您可以在不使用循环的情况下对数字进行位反转(例如使用查找表或其他特殊的CPU指令),那么您可以反转数字,找到最低有效位设置为1,重置其他位并将其反转回来。
unsigned IsolateLeastSignificantOne(unsigned n)
{
return n & -n;
}
n = BitRevert(IsolateLeastSignificantOne(BitRevert(n)));
有关位运算技巧和其他实用信息,请参考此文档。
2^floor(log2(number))
。 - Floris