c - 位切片 : finding minimum value

Question

精简版

我需要找到编码为位片的 64 个 uint8_t 变量的最小值。

即变量的每一位都被编码成八个独立的uint64_t:

//Normal layout:
uint8_t values[64]; // This is what you normally use. 
                    // Finding minimum would be a simple 
                    // matter of a for loop

/***********************/

// BITSLICE layout:
uint64_t slices[8]; // This is what I have, due to performance 
                    // reasons in other parts of the code (not shown here)

slice[0]; //LSB: Least signignificant bit (for all 64 values)
slice[7]; //MSB: Most significant bit (for all 64 values)

现在，我如何找出这些的最小值？(我不关心它的位置，只关心它的值)

更多背景信息:

实际上，出于性能原因，我在一个已经使用位切片的算法中有一个更长的数组(超过 64 个)值。

所以我得到的实际上更像是(上面的问题被简化了):

uint64_t slices[8][100];

所以我真正需要的是所有 100*64 值中的最小值。但我认为这可以通过应用上述简化问题的答案在常规 for 循环中完成。

编辑:显然我的问题没有我想的那么清楚所以它已经更新了

Answer 1

我至少可以想到两种方法。最简单的方法就是对其进行暴力破解:通过适当的按位算法一次重构 64 个整数中的每一个，并跟踪最小结果。沿着这些线的东西:

uint8_t min = 0xff;

// iterate over the collection of values
for (uint64_t which = 1; which; which <<= 1) {
    // reconstitute one value in 'test'
    uint8_t test = 0;

    for (int bit = 0; bit < 8; bit++) {
        // verify this decoding -- your bit order may be different:
        test += (!!(slices[bit] & which)) << bit;
    }

    // track the minimum
    if (test < min) {
        min = test;
    }
}

另一方面，也可以通过仅扫描一次切片并直接累加最小值来更快地完成此操作。我没有时间对此进行测试，但它应该传达了总体思路:

uint8_t min = 0xff;
uint64_t mask = ~(uint64_t)0;  // a mask of candidate positions; all bits initially set

for (int i = 7; i >= 0; i--) {  // assumes slice 7 is most significant
    // which of the remaining candidates have this bit set:
    uint64_t bits_set = slice[i] & mask;

    // If at least one of the remaining candidates does not have this bit set
    if (bits_set != mask) {
        min ^= (1 << i);   // turn off this bit in the result
        mask ^= bits_set;  // remove the candidates that do have this bit set
    }
}

后者类似于基数排序。