如何在给定的无符号整数 X
找到最小的n,即 2的n次方
≥ X
在O(1)?换句话说,我想找到一个更高的设定位指数在二进制格式X
(加1,如果 X
是没有权力2)O(1)(不依赖于整数和字节大小)的大小。
How for given unsigned integer x
find the smallest n, that 2 ^ n
≥ x
in O(1)? in other words I want to find the index of higher set bit in binary format of x
(plus 1 if x
is not power of 2) in O(1) (not depended on size of integer and size of byte).
如果你没有内存限制,那么你可以使用一个查找表(适用 X )来实现的 O(1)的时间。
If you have no memory constraints, then you can use a lookup table (one entry for each possible value of x
) to achieve O(1) time.
如果你想有一个实用的解决方案,大多数处理器将拥有某种找到最高位的OP code。在x86上,例如,它的 BSR
。大多数编译器将有一个机制来编写原始汇编。
If you want a practical solution, most processors will have some kind of "find highest bit set" opcode. On x86, for instance, it's BSR
. Most compilers will have a mechanism to write raw assembler.