0

假设 的长度array是动态的，并且元素遵循相同的模式，其中下一个元素是前一个元素的一半。例如 1024、512、256、128...

我想直接确定一个元素的索引。例如，如果我有，512我会输出index 1而不循环遍历元素并将它们与 512 进行比较，然后输出 1。即不是这样：

for (int i = 0;  i < length;  ++i) {
    if (array[i] == 512) { 
        printf("%d\n", i);
        break;
    }
}

我一直在考虑使用模数或位操作，如移位，但我无法让它工作。如何做到这一点？

4

3 回答 3

3

你的数组的元素是：1024 512 256 128. 它们都是 2 的幂，因此取log2每个元素将给出：

10, 9, 8, 7

因此，您可以执行以下操作：

if array[i]==n
        print 10-log2(n)

此解决方案仅对您给定的预定义数组有效。

#include <stdio.h>
#include <math.h>

int main(void) {
    int a[4] = {1024, 512, 256, 128};
    for(size_t i=0;i<4;i++)
        printf("%d %d\n",a[i],10-(int)log2(a[i]));
    return 0;
}

输出：

1024 0
512 1
256 2
128 3
于 2018-04-24T15:26:16.090 回答
0

解决方案10-log2(n)，其中 n 是需要确定其索引的数组元素，给了我一个洞察力。我一直在努力弄清楚 10 在10-log2(n). 我意识到一般的解决方案是数组中最大的已知元素在log2(X)-log(n)哪里。数组应按降序排序，使第 0 个元素最大X

例子：

Array[5]={2048, 1024, 512, 256, 128};

查找数组元素的索引256将是log2(2048)-log2(256)=11-8=3因此一般的解决方案是log2(largest array element)-log2(base2 value you are looking for) ，您必须知道最大的数组元素，并且假设数组按降序排序 Live example here

最佳选择：index=log2(array[0]/value)value确定其索引的数组元素 在哪里index=log2(array[0]/value) 现场示例在这里

于 2018-04-24T19:00:25.920 回答
0

如果您确定给定的值是正确的（即您不需要验证），这应该有效：

3 - ( n >> 8 ) + ( n >> 10 )

活生生的例子

另一种选择是使用 3 个条件（但始终只执行 2 个），但由于分支预测，这很可能会更慢：

n > 512 ? ( n < 1024 ? 1 : 0 ) : ( n > 128 ? 2 : 3 )

如果您的数组可以是任意大小，请使用此问题中的方法Find the highest order bit in C

int hibit(unsigned int n) {
    n |= (n >>  1);
    n |= (n >>  2);
    n |= (n >>  4);
    n |= (n >>  8);
    n |= (n >> 16);
    return n - (n >> 1);
}

只需从正确的数字中减去结果。

于 2018-04-24T15:31:43.647 回答