algorithm - 找到最高有效位的算法

Question

我的一个朋友在接受采访时被问到以下问题：“给定一个二进制数，找到最高有效位”。我立即想到了以下解决方案，但不确定它是否正确。

即，将字符串分成两部分并将两部分转换为十进制。如果左子数组十进制为 0，则在右子数组中进行二进制搜索，寻找 1。

那是我的另一个问题。最高有效位是二进制数中最左边的 1 吗？当 0 是最重要的位时，你能给我举个例子和解释吗？

编辑：

下面的答案似乎有点混乱，所以我正在更新问题以使其更准确。面试官说“您有一个网站，您从该网站接收数据，直到最高有效位指示停止传输数据”您将如何告诉程序停止数据传输？

score 13 · Accepted Answer

您也可以使用位移。伪代码：

number = gets
bitpos = 0
while number != 0
  bitpos++             # increment the bit position
  number = number >> 1 # shift the whole thing to the right once
end
puts bitpos

如果数字为零，则 bitpos 为零。

score 12 · Accepted Answer

仅使用类 C 语言指令可以通过使用基于 De Bruijn 序列的广为人知的方法来找到单词中的最高有效位（即，通过向下舍入计算 log2）。例如，对于 32 位值

unsigned ulog2(uint32_t v)
{ /* Evaluates [log2 v] */
  static const unsigned MUL_DE_BRUIJN_BIT[] = 
  {
     0,  9,  1, 10, 13, 21,  2, 29, 11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7, 19, 27, 23,  6, 26,  5,  4, 31
  };

  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;

  return MUL_DE_BRUIJN_BIT[(v * 0x07C4ACDDu) >> 27];
}

然而，在实践中，更简单的方法（如展开的二进制搜索）通常工作得一样好或更好。

score 2 · Accepted Answer

编辑后的问题确实非常不同，尽管不是很清楚。你是谁”？网站或从网站读取数据的程序的程序员？如果您是网站，您可以通过发送一个设置了最高有效位的值（但什么，可能是一个字节？）来使程序停止。只是 OR 或 ADD 那个位。如果你是程序员，你测试你收到的值的最重要的位，并在它被设置时停止读取。对于无符号字节，您可以进行如下测试

bool stop = received_byte >= 128;
or
bool stop = received_byte & 128;

对于有符号字节，您可以使用

bool stop = received_byte < 0;
or
bool stop = received_byte & 128;

如果您不是读取字节，而是读取 32 位字，则 128 更改为(1 << 31).

score 1 · Accepted Answer

这是一种方法（但不一定是最有效的，特别是如果您的平台有一个单指令解决方案来查找第一个或计数前导零或类似的东西），假设二进制补码有符号整数和 32 位整数宽度。

int mask = (int)(1U<<31); // signed integer with only bit 32 set
while (! n & mask)        // n is the int we're testing against
  mask >>= 1;             // take advantage of sign fill on right shift of negative number
mask = mask ^ (mask << 1) // isolate first bit that matched with n

如果您想要第一个的位位置，只需添加一个从 31 开始并在每次循环迭代时递减的整数计数器。

这样做的一个缺点是 if n == 0，它是一个无限循环，所以事先测试为零。

score 0 · Accepted Answer

如果您对 C/C++ 解决方案感兴趣，可以查看Jörg Arndt 的“Matters Computational”一书，其中您在“1.6.1 隔离最高的一个并找到它的索引”部分中定义了这些函数：

static inline ulong highest_one_idx(ulong x)
// Return index of highest bit set.
// Return 0 if no bit is set.
{
#if defined  BITS_USE_ASM
    return  asm_bsr(x);
#else  // BITS_USE_ASM

#if  BITS_PER_LONG == 64
#define MU0 0x5555555555555555UL  // MU0 == ((-1UL)/3UL) == ...01010101_2
#define MU1 0x3333333333333333UL  // MU1 == ((-1UL)/5UL)   == ...00110011_2
#define MU2 0x0f0f0f0f0f0f0f0fUL  // MU2 == ((-1UL)/17UL)  == ...00001111_2
#define MU3 0x00ff00ff00ff00ffUL  // MU3 == ((-1UL)/257UL)  == (8 ones)
#define MU4 0x0000ffff0000ffffUL  // MU4 == ((-1UL)/65537UL) == (16 ones)
#define MU5 0x00000000ffffffffUL  // MU5 == ((-1UL)/4294967297UL) == (32 ones)
#else
#define MU0 0x55555555UL  // MU0 == ((-1UL)/3UL) == ...01010101_2
#define MU1 0x33333333UL  // MU1 == ((-1UL)/5UL)   == ...00110011_2
#define MU2 0x0f0f0f0fUL  // MU2 == ((-1UL)/17UL)  == ...00001111_2
#define MU3 0x00ff00ffUL  // MU3 == ((-1UL)/257UL)  == (8 ones)
#define MU4 0x0000ffffUL  // MU4 == ((-1UL)/65537UL) == (16 ones)
#endif

    ulong r = (ulong)ld_neq(x, x & MU0)
        + ((ulong)ld_neq(x, x & MU1) << 1)
        + ((ulong)ld_neq(x, x & MU2) << 2)
        + ((ulong)ld_neq(x, x & MU3) << 3)
        + ((ulong)ld_neq(x, x & MU4) << 4);
#if  BITS_PER_LONG > 32
    r += ((ulong)ld_neq(x, x & MU5) << 5);
#endif
    return r;

#undef MU0
#undef MU1
#undef MU2
#undef MU3
#undef MU4
#undef MU5
#endif
}

asm_bsr根据您的处理器架构在哪里实现

// i386
static inline ulong asm_bsr(ulong x)
// Bit Scan Reverse: return index of highest one.
{
    asm ("bsrl %0, %0" : "=r" (x) : "0" (x));
    return x;
}

或者

// AMD64
static inline ulong asm_bsr(ulong x)
// Bit Scan Reverse
{
    asm ("bsrq %0, %0" : "=r" (x) : "0" (x));
    return x;
}

去这里获取代码：http: //jjj.de/bitwizardry/bitwizardrypage.html

编辑：

这是函数源代码中的定义ld_neq：

static inline bool ld_neq(ulong x, ulong y)
// Return whether floor(log2(x))!=floor(log2(y))
{ return ( (x^y) > (x&y) ); }

score -1 · Accepted Answer

我不知道这太棘手了:)

我会将二进制数转换为 dec，然后直接返回该数字的以 2 为底的对数（从浮点数转换为整数）。

解决方案是从右边开始的（返回的数字+ 1）位。

据我所知，你的答案是最左边的 1

score -2 · Accepted Answer

我认为这是一个棘手的问题。最重要的位总是 1 :-)。如果面试官喜欢横向思维，那么这个答案应该是赢家！

algorithm - 找到最高有效位的算法

编辑：

7 回答 7

Related

Reference