C语言 如何使用按位运算符计算以2为底的对数?

hgc7kmma  于 2023-05-06  发布在  其他
关注(0)|答案(4)|浏览(302)

我需要用C语言计算一个数字的对数基数2,但我不能使用数学库。答案不需要是精确的,只要是最接近的整数即可。我已经考虑过了,我知道我可以使用一个while循环,并不断地将数字除以2,直到它〈2,并保持迭代次数,但这可能使用按位运算符吗?

6pp0gazn

6pp0gazn1#

abamert已经回答过了,但更具体地说,这是你如何编码的:

Log2(x) = result
while (x >>= 1) result++;
nimxete2

nimxete22#

如果将移位计算为按位运算符,则这很容易。
您已经知道如何通过连续除以2来实现。
x >> 1x / 2相同,对于C中的任何无符号整数。
如果需要更快,可以进行“分而治之”-每次移位4位,直到达到0,然后返回并查看最后4位。这意味着最多16次移位和19次比较,而不是每次63次。它是否真的在现代CPU上更快,我不能说没有测试。你可以更进一步,先做16组,然后是4组,然后是1组。在这里可能没有用,但是如果你有一些1024位的整数,它可能值得考虑。

js5cn81o

js5cn81o3#

__builtin_clz(x):此函数用于计算整数的前导零。注:clz =计数前导零(C/ C++)。考虑到32位整数,

log_2_x = 32 - __builtin_clz(x) - 1;
vnzz0bqm

vnzz0bqm4#

如果可以使用最新的C++编译器进行编译,则可以使用

#include <bit>
  int log2(auto i) { return 8*sizeof(i) - std::countl_zero(i) - 1; }

便携式。
对于g或clang,这将使用“-std=c20”或更高版本。这将使用x86上的“bsr”指令,比循环快得多。

相关问题