我有一个位数组的实现,其中第0个索引是数组中第一个字节的最高有效位,第8个索引是第二个字节的最高有效位,以此类推...
如何快速找到在这个位数组中设置的第一个位?我查阅了所有相关解决方案,但它们都只能找到第一个最不重要的位,而我需要第一个最重要的位。因此,对于0x00A1,我想要的结果是8(因为它是从左边数的第9个位)。
我有一个位数组的实现,其中第0个索引是数组中第一个字节的最高有效位,第8个索引是第二个字节的最高有效位,以此类推...
如何快速找到在这个位数组中设置的第一个位?我查阅了所有相关解决方案,但它们都只能找到第一个最不重要的位,而我需要第一个最重要的位。因此,对于0x00A1,我想要的结果是8(因为它是从左边数的第9个位)。
////// go.c ////////
#include <stdio.h>
unsigned NUM_BITS_U = ((sizeof(unsigned) << 3) - 1);
#define POS_OF_HIGHESTBITclz(a) (NUM_BITS_U - __builtin_clz(a)) /* only works for a != 0 */
#define NUM_OF_HIGHESTBITclz(a) ((a) \
? (1U << POS_OF_HIGHESTBITclz(a)) \
: 0)
int main()
{
unsigned ui;
for (ui = 0U; ui < 18U; ++ui)
printf("%i \t %i\n", ui, NUM_OF_HIGHESTBITclz(ui));
return 0;
}
typedef unsigned long long u64;
typedef unsigned int u32;
typedef unsigned char u8;
u8 findMostSignificantBit (u64 u64Val)
{
u8 u8Shift;
u8 u8Bit = 0;
assert (u64Val != 0ULL);
for (u8Shift = 32 ; u8Shift != 0 ; u8Shift >>= 1)
{
u64 u64Temp = u64Val >> u8Shift;
if (u64Temp)
{
u8Bit |= u8Shift; // notice not using +=
u64Val = u64Temp;
}
}
return u8Bit;
}
u8 findMostSignificantBit2 (u64 u64Val)
{
assert (u64Val != 0ULL);
return (u8) (__builtin_ctzll(u64Val));
}
我知道的在纯C中实现此操作的两种最佳方法:
首先,线性搜索字节/单词数组以查找第一个非零字节/单词,然后对找到的字节/单词进行展开的二分搜索。
if (b>=0x10)
if (b>=0x40)
if (b>=0x80) return 0;
else return 1;
else
if (b>=0x20) return 2;
else return 3;
else
if (b>=0x4)
if (b>=0x8) return 4;
else return 5;
else
if (b>=0x2) return 6;
else return 7;
需要进行3次条件跳转(BTW,即log2(8)),才能得到答案。在现代x86机器上,最后一步将被优化为条件mov。
或者,使用查找表将字节映射到第一个设置的位的索引。
一个相关的主题是整数log2函数。如果我没记错,FFmpeg有一个很好的实现。
编辑:您实际上可以将上述二分搜索转换为无分支二分搜索,但我不确定在这种情况下是否更有效......
这是一个针对任意大小的字节数组的简单暴力算法:
int msb( unsigned char x); // prototype for function that returns
// most significant bit set
unsigned char* p;
for (p = arr + num_elements; p != arr;) {
--p;
if (*p != 0) break;
}
// p is with pointing to the last byte that has a bit set, or
// it's pointing to the first byte in the array
if (*p) {
return ((p - arr) * 8) + msb( *p);
}
// what do you want to return if no bits are set?
return -1;
我将把适当的msb()
函数以及在int
或long long
大小的数据块上进行优化的练习留给读者。
嗯,你的标签显示为32位,但看起来你使用的值是16位。如果你确实是指32位,那么我认为0x00a1的答案应该是24而不是8。
假设你正在寻找左侧的MSB位索引,并且你知道你只会处理uint32_t,这里是显而易见的、简单的算法:
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
int main()
{
uint32_t test_value = 0x00a1;
int i;
for (i=0; i<32; ++i)
{
if (test_value & (0x80000000 >> i))
{
printf("i = %d\n", i);
exit(0);
}
}
return 0;
}
对于Java,我使用这个:
static public final int msb(int n) {
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
n >>>= 1;
n += 1;
return n;
}
并且:
static public final int msb_index(int n) {
final int[] multiply_de_bruijn_bit_position = {
0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
return multiply_de_bruijn_bit_position[(msb(n) * 0x077CB531) >>> 27];
}
#define FFS(t) \
({ \
register int n = 0; \
\
if (!(0xffff & t)) \
n += 16; \
\
if (!((0xff << n) & t)) \
n += 8; \
\
if (!((0xf << n) & t)) \
n += 4; \
\
if (!((0x3 << n) & t)) \
n += 2; \
\
if (!((0x1 << n) & t)) \
n += 1; \
\
n; \
})
t
放在括号中,如果它是一个宏的话。最好将其放在本地变量中,这样它就不会一直被计算。 - Claudiu