我有一个位数组的实现，其中第0个索引是数组中第一个字节的最高有效位，第8个索引是第二个字节的最高有效位，以此类推...
如何快速找到在这个位数组中设置的第一个位？我查阅了所有相关解决方案，但它们都只能找到第一个最不重要的位，而我需要第一个最重要的位。因此，对于0x00A1，我想要的结果是8（因为它是从左边数的第9个位）。
在一个位数组中找到最左边被设置的最高位
47
- Claudiu
7
1假设最低有效位是第0位，那么在0x00a1中，不是第7位是设置的最高有效位吗？ - Michael Burr
你的位数组长度是否任意，还是适合于机器字？ - Michael Burr
你对位数组有什么接口？你可以对它执行哪些操作？ - jemfinch
@jemfinch：这是一个C字符数组。 - Claudiu
1已经有另外一页提供了详细信息... https://dev59.com/DXRB5IYBdhLWcg3wSVcI - Josh
显示剩余2条评论
17个回答
1
这是一个代码片段，解释了__builtin_clz()函数。
////// 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;
}
- George
1
我来添加一个！
当然，这是在64位数字（unsigned long long）上运行，而不是数组。此外，很多人已经指出了我不知道的内置g++函数。多么有趣。
无论如何，这个函数在6次迭代中找到了最高有效位，并在将0传递给函数时给出了一个断言。如果您可以访问芯片组的指令，则不是使用的最佳函数。
我还使用|=而不是+=，因为它们总是2的幂，并且OR（经典上）比加法快。由于我只添加唯一的2的幂，所以我从来没有翻转。
这是一个二分查找，这意味着它总是在6次迭代中找到结果。
再次强调，这个更好：
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;
}
当然，这是在64位数字（unsigned long long）上运行，而不是数组。此外，很多人已经指出了我不知道的内置g++函数。多么有趣。
无论如何，这个函数在6次迭代中找到了最高有效位，并在将0传递给函数时给出了一个断言。如果您可以访问芯片组的指令，则不是使用的最佳函数。
我还使用|=而不是+=，因为它们总是2的幂，并且OR（经典上）比加法快。由于我只添加唯一的2的幂，所以我从来没有翻转。
这是一个二分查找，这意味着它总是在6次迭代中找到结果。
再次强调，这个更好：
u8 findMostSignificantBit2 (u64 u64Val)
{
assert (u64Val != 0ULL);
return (u8) (__builtin_ctzll(u64Val));
}
- Richard wicks
1
我知道的在纯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有一个很好的实现。
编辑：您实际上可以将上述二分搜索转换为无分支二分搜索，但我不确定在这种情况下是否更有效......
- R.. GitHub STOP HELPING ICE
0
这是一个针对任意大小的字节数组的简单暴力算法：
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大小的数据块上进行优化的练习留给读者。
- Michael Burr
0
嗯，你的标签显示为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;
}
- tikiboy
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];
}
- clankill3r
-3
#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; \
})
- Leslie Li
3
1这里应该将
t放在括号中，如果它是一个宏的话。最好将其放在本地变量中，这样它就不会一直被计算。 - Claudiu它只使用二分查找，我同意你的评论Claudiu，但我认为应该有一种更有效的方法来获得结果，而不使用clz bsr类似的指令。 - Leslie Li
1这是一个随机数生成器，而不是二分查找。 - johnwbyrd
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接