获取数字的第二个最重要的位

Question

你是一个给定整数的 C 程序员i > 1。你能写一个函数msb2来返回它的第二个最重要的位，换句话说：给定一个数字，最左边的 1 位右边的位是什么？即在1011111它是0，在1100000它是1。

不允许：

• 任何循环（例如分别检查 64 位中的每一个）
• 浮动算术

允许的有：

• 所有 C 整数运算符

是否有一个常数时间（位数常数，假设所有 C 整数运算符都占用常数时间，并假设位数不是常数）函数msb2？

我头脑中的一个想法是：鉴于i，我们知道i & (i >> 1) >= (1<<((int)log2(i)-1)) <=> msb2(i)=1，但是log2(i)不能轻易计算。也许这仍然可以以某种方式使用？

Answer 1

你可以简单地使用

x > (x ^ (x >> 1))

该值(x ^ (x >> 1))将以11ifx开头10，而 with 10ifx以 开头11。因此，比较准确地给出了所需要的。