我想写一个函数,返回最接近的2的次幂数。例如,如果我的输入是789,输出应该是1024。有没有办法不使用任何循环,而只是使用一些位运算符?
当前回答
还有一个,虽然我用的是循环,但这比数学操作数要快得多
功率两“地板”选项:
int power = 1;
while (x >>= 1) power <<= 1;
两个“ceil”选项的力量:
int power = 2;
x--; // <<-- UPDATED
while (x >>= 1) power <<= 1;
更新
正如在评论中提到的,在cell中有错误,它的结果是错误的。
以下是全部功能:
unsigned power_floor(unsigned x) {
int power = 1;
while (x >>= 1) power <<= 1;
return power;
}
unsigned power_ceil(unsigned x) {
if (x <= 1) return 1;
int power = 2;
x--;
while (x >>= 1) power <<= 1;
return power;
}
其他回答
在标准c++20中,这包含在<bit>中。 答案很简单
#include <bit>
unsigned long upper_power_of_two(unsigned long v)
{
return std::bit_ceil(v);
}
注意: 我给出的解决方案是针对c++,而不是c,我会给出这个问题的答案,但它是这个问题的副本!
from math import ceil, log2
pot_ceil = lambda N: 0x1 << ceil(log2(N))
测试:
for i in range(10):
print(i, pot_ceil(i))
输出:
1 1
2 2
3 4
4 4
5 8
6 8
7 8
8 8
9 16
10 16
如果您正在使用GCC,您可能想要看看Lockless Inc.优化next_pow2()函数。本页描述了一种使用内置函数builtin_clz()(计数前导零)的方法,然后直接使用x86 (ia32)汇编指令bsr(位扫描反向),就像它在另一个答案的游戏开发站点链接中所描述的那样。此代码可能比前面的回答中描述的更快。
顺便说一下,如果你不打算使用汇编指令和64位数据类型,你可以使用这个
/**
* return the smallest power of two value
* greater than x
*
* Input range: [2..2147483648]
* Output range: [2..2147483648]
*
*/
__attribute__ ((const))
static inline uint32_t p2(uint32_t x)
{
#if 0
assert(x > 1);
assert(x <= ((UINT32_MAX/2) + 1));
#endif
return 1 << (32 - __builtin_clz (x - 1));
}
/*
** http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog
*/
#define __LOG2A(s) ((s &0xffffffff00000000) ? (32 +__LOG2B(s >>32)): (__LOG2B(s)))
#define __LOG2B(s) ((s &0xffff0000) ? (16 +__LOG2C(s >>16)): (__LOG2C(s)))
#define __LOG2C(s) ((s &0xff00) ? (8 +__LOG2D(s >>8)) : (__LOG2D(s)))
#define __LOG2D(s) ((s &0xf0) ? (4 +__LOG2E(s >>4)) : (__LOG2E(s)))
#define __LOG2E(s) ((s &0xc) ? (2 +__LOG2F(s >>2)) : (__LOG2F(s)))
#define __LOG2F(s) ((s &0x2) ? (1) : (0))
#define LOG2_UINT64 __LOG2A
#define LOG2_UINT32 __LOG2B
#define LOG2_UINT16 __LOG2C
#define LOG2_UINT8 __LOG2D
static inline uint64_t
next_power_of_2(uint64_t i)
{
#if defined(__GNUC__)
return 1UL <<(1 +(63 -__builtin_clzl(i -1)));
#else
i =i -1;
i =LOG2_UINT64(i);
return 1UL <<(1 +i);
#endif
}
如果你不想冒险进入未定义行为的领域,输入值必须在1到2^63之间。宏在编译时设置常量也很有用。
import sys
def is_power2(x):
return x > 0 and ((x & (x - 1)) == 0)
def find_nearest_power2(x):
if x <= 0:
raise ValueError("invalid input")
if is_power2(x):
return x
else:
bits = get_bits(x)
upper = 1 << (bits)
lower = 1 << (bits - 1)
mid = (upper + lower) // 2
if (x - mid) > 0:
return upper
else:
return lower
def get_bits(x):
"""return number of bits in binary representation"""
if x < 0:
raise ValueError("invalid input: input should be positive integer")
count = 0
while (x != 0):
try:
x = x >> 1
except TypeError as error:
print(error, "input should be of type integer")
sys.exit(1)
count += 1
return count