我需要用C语言计算一个数字的对数基数2,但我不能使用数学库。答案不需要是精确的,只要是最接近的整数即可。我已经考虑过了,我知道我可以使用一个while循环,并不断地将数字除以2,直到它〈2,并保持迭代次数,但这可能使用按位运算符吗?
6pp0gazn1#
abamert已经回答过了,但更具体地说,这是你如何编码的:
Log2(x) = result while (x >>= 1) result++;
nimxete22#
如果将移位计算为按位运算符,则这很容易。您已经知道如何通过连续除以2来实现。x >> 1与x / 2相同,对于C中的任何无符号整数。如果需要更快,可以进行“分而治之”-每次移位4位,直到达到0,然后返回并查看最后4位。这意味着最多16次移位和19次比较,而不是每次63次。它是否真的在现代CPU上更快,我不能说没有测试。你可以更进一步,先做16组,然后是4组,然后是1组。在这里可能没有用,但是如果你有一些1024位的整数,它可能值得考虑。
x >> 1
x / 2
js5cn81o3#
__builtin_clz(x):此函数用于计算整数的前导零。注:clz =计数前导零(C/ C++)。考虑到32位整数,
log_2_x = 32 - __builtin_clz(x) - 1;
vnzz0bqm4#
如果可以使用最新的C++编译器进行编译,则可以使用
#include <bit> int log2(auto i) { return 8*sizeof(i) - std::countl_zero(i) - 1; }
便携式。对于g或clang,这将使用“-std=c20”或更高版本。这将使用x86上的“bsr”指令,比循环快得多。
4条答案
按热度按时间6pp0gazn1#
abamert已经回答过了,但更具体地说,这是你如何编码的:
nimxete22#
如果将移位计算为按位运算符,则这很容易。
您已经知道如何通过连续除以2来实现。
x >> 1
与x / 2
相同,对于C中的任何无符号整数。如果需要更快,可以进行“分而治之”-每次移位4位,直到达到0,然后返回并查看最后4位。这意味着最多16次移位和19次比较,而不是每次63次。它是否真的在现代CPU上更快,我不能说没有测试。你可以更进一步,先做16组,然后是4组,然后是1组。在这里可能没有用,但是如果你有一些1024位的整数,它可能值得考虑。
js5cn81o3#
__builtin_clz(x):此函数用于计算整数的前导零。注:clz =计数前导零(C/ C++)。考虑到32位整数,
vnzz0bqm4#
如果可以使用最新的C++编译器进行编译,则可以使用
便携式。
对于g或clang,这将使用“-std=c20”或更高版本。这将使用x86上的“bsr”指令,比循环快得多。