如果我有一个整数n,并且我想知道最高位的位置(也就是说,如果最低有效位在右边,我想知道最左边位的位置是1),找出最快捷/最有效的方法是什么？
我知道POSIX支持ffs()strings.h中的一个方法来查找第一个设置位,但似乎没有相应的fls()方法.
是否有一些非常明显的方法可以解决这个问题？
如果你不能使用POSIX功能来实现可移植性呢？
编辑:如何在32位和64位架构上运行的解决方案(许多代码清单似乎只能在32位整数上运行).
有没有办法写log(base 2)函数？
C语言有2个内置函数 - >>
1. log基础e.
2. log10基数10;
但我需要基数2的日志功能.如何计算这个.
在玩这个问题时,我注意到一些我无法解释的关于相对表现的事情np.log2,np.log并且np.log10:
In [1]: %%timeit x = np.random.rand(100000)
....: np.log2(x)
....:
1000 loops, best of 3: 1.31 ms per loop
In [2]: %%timeit x = np.random.rand(100000)
np.log(x)
....:
100 loops, best of 3: 3.64 ms per loop
In [3]: %%timeit x = np.random.rand(100000)
np.log10(x)
....:
100 loops, best of 3: 3.93 ms per loop
np.log2比np.log和和快约3倍np.log10.或许甚至更直观地np.log1p(x)计算ln(x + 1),与以下内容相同np.log2:
In [4]: %%timeit x = …我需要计算熵，并且由于我的系统的限制，我需要使用受限的 C 功能（无循环，无浮点支持），并且我需要尽可能高的精度。从这里我弄清楚如何使用按位运算来估计整数的下限 log2。尽管如此，我需要提高结果的精度。由于不允许浮点运算，有没有什么方法可以进行计算，log2(x/y)使x < y结果类似于log2(x/y)*10000，旨在通过算术整数获得我需要的精度？
我要寻找一个在满二叉树一定的时间实现最低的共同祖先给出了两个节点(父X小于子2*x和2*X + 1).
我的问题是树中有大量节点和许多查询.是否有一个算法,它预处理,以便可以在恒定的时间内回答查询.
我使用RMQ查看了LCA,但我不能使用该技术,因为我不能在树中使用这个节点的数组.
有人可以给我快速回答许多查询的算法的有效实现,知道它是完整的二叉树,并且节点之间的关系如上所述.
我所做的是从两个给定节点开始,并连续找到它们的父节点(节点/ 2)保持被访问节点的哈希列表.当我们到达已经在哈希列表中的节点时,该节点将是最低的共同祖先.
但是当存在许多查询时,这种算法非常耗时,因为在最坏的情况下,我可能必须遍历高度30(树的最大高度)才能到达根(最坏的情况).
我现在正在解决一个问题，如下所示：
有两个数 x1 和 x2，且 x2 > x1。
例如 x1 = 5；x2 = 10；
我必须找到二进制表示中 x1 和 x2 之间的总和。
5 = 101 => 2 ones
6 = 110 => 2 ones
7 = 111 => 3 ones
8 = 1000 => 1 one
9 = 1001 => 2 ones
10= 1010 => 2 ones
so the sum will be
sum = 2 + 2 + 3 + 1 + 2 + 2 = 12 ones;
所以我成功地编写了一个代码，甚至没有将数字转换为二进制并浪费执行时间。
2^n我注意到每个with中的个数n >= …
我有一小组正整数(大约10个数字),每个都是2的幂.
如何尽快将每个号码映射到其他号码？
这里有两个可行的解决方案但是,考虑到问题的简单性(以及我有多少键),它们看起来都是不必要的迟缓(我错了吗？):
std::map完全避免映射问题,例如,用一个携带对的结构替换我的整数可能是最快的解决方案,但它会使我的大部分代码复杂化,所以我不愿意这样做.
我坚持这个问题:假设我们有32位整数,写一个C函数来计算从左边开始的连续1位的数量.例如:
leftCount(0xFF000000) = 8
leftCount(0x0FFFFFFF) = 0 (because the number starts with 0)
leftCount(-1) = 32
在函数中,我被允许使用逻辑运算符,如!〜&^ | + << >>
不允许循环和条件结构.
谢谢